algospot.com :: 과거 게시판: [editorial] TCO09 Round 2

[editorial] TCO09 Round 2

안녕하세요. 간만에 에디토리얼을 쓰게 되네요.
750명 중에서 300명을 뽑는 본격적인 빡세지기 시작하는 라운드 되겠습니다.
그나저나 언제나 타겟이 되볼지 ㅠ.ㅠ
Easy(250pt, PlaneFractal)
두 가지의 접근 방법이 있습니다.
(1) 1초부터 s초까지 시뮬레이션을 돌려봅니다. 즉 1초째에 검은색이 되었다면 그냥 거기서 끝이고, 아니면 2초째를 체크해봅니다. 이 때 체크하는 정사각형의 크기는 1/N으로 점점 작아지게 됩니다. (제가 사용한 방법 - 코드 자체로 설명이 될 것 같습니다.)
(2) s초부터 1초까지 역추적합니다. s초째에 검은 색이 될 부분이면 그냥 거기서 끝이고, 아니면 s-1초째를 체크해봅니다. 이 쪽이 구현은 조금 더 쉬운 것 같습니다.
실수하기 쉬운 것이라면 s=0일때 예외처리하는 부분? 정도였던 것 같습니다. 이걸로 xx된 레드들이 꽤 있었죠...

#include <vector>
#include <string>
#include <queue>
#include <map>
#include <math.h>
#include <cmath>
#include <algorithm>
using namespace std;
class PlaneFractal
{
  public:
  int isBlack(int s, int N, int K, int r, int c)
  {
    if (s==0)
      return 0;
    int div = 1;
    for (int i=0; i<s-1; i++) div *= N;
    int rr = r/div;
    int cc = c/div;
    int left = (N-K)/2;
    if (rr>=left && cc>=left && rr<=N-1-left && cc<=N-1-left) return 1;
    return isBlack(s-1, N, K, r%div, c%div);
  }
  vector <string> getPattern(int s, int N, int K, int r1, int r2, int c1, int c2)
  {
    vector<string> res(r2-r1+1);
    for (int i=r1; i<=r2; i++)
      for (int j=c1; j<=c2; j++)
        res[i-r1] += '0'+isBlack(s, N, K, i, j);
    return res;
  };
};

Medium(600pt, ExtendableTriangles)
여러 phase로 나누어서 처리를 해야 해서, 생각보다는 꽤나 힘든 문제였습니다 (1등이 370점대니 뭘 더 말하겠습니까...)
Problem reducing Phase(Line 29-34, 101-102) : 일단, 각각의 삼각형이 extendable한지 체크하는 것은 전체 점의 수가 최대 2500이므로 가능한 삼각형의 최대 수 (2500/3)^3마다 체크를 해야하므로 여의치 않습니다. 그보다 훨씬 수가 적은 not-extendable한 삼각형의 수를 구해서, 전체 가능한 삼각형의 수에서 빼야 합니다.
Phase 1(Line 36-59) : 그럼 not-extendable한 삼각형의 성질은 무엇이냐? 물론 삼각형을 extend할 수 없다는 것이죠. 문제에서의 정의에 의하면 세 점 중 하나를 잡아서 다른 어떤 점으로 바꿔도 넓이가 늘어나지 않는 점이라고 합니다. 그 말은 두 점이 정해지면, 이 두 점을 잇는 선에서 가장 거리가 먼 점들만 따지면 된다는 것입니다. 두 점이 변해도 두 점을 잇는 벡터만 변하지 않으면 이 선에서 가장 거리가 먼 점들이 될 수 있는 점들의 집합은 구하기 어렵지 않습니다. 벡터가 (a, b)라면, bx-ay를 최대로 만드는 점들과 최소로 만드는 점들을 구해놓으면 됩니다. 벡터가 (a, b)이든 (ca, cb)이든 같기 때문에 일단 gcd(a, b)로 나누는 과정도 거칩니다.
많은 사람들... 그리고 의도된 답안에서는, 이렇게 구하지 않고, R, G, B 점들로 각각 convex hull을 구해서, 여기에 속하는 점들을 체크하는 방식으로 합니다. 자세한 증명은 생략합니다 :)
Phase 2(Line 60-81) : 이제 Phase 1에서 구한 정보를 가지고, (a, b)와 (c, d)를 두 꼭지점으로 하는 beautiful triangle의 최대 넓이를 구합니다. (a, b)와 (c, d)의 색깔이 달라야 하고, 그럼 potential (e, f)의 색깔도 정해지겠죠. 벡터는 (c-a, d-b)으로 나오겠구요. 그냥 iteration 돌면서 구합니다. (integer operation을 위해서 /2 안한 채로 저장합니다)
Phase 3(Line 83-100) : (a, b)가 R, (c, d)가 B인 경우, Phase 1에서 구한 정보를 다시 한번 사용해서, 가능한 G 점들에 대해서 각각이 not-extendable triangle인지를 체크합니다. 삼각형의 넓이가, Phase 2에서 구해놓은 두 점이 고정되어 있을 때의 beautiful triangle의 최대 넓이와 같아야 합니다. 세 점중 어떻게 두 점을 선택하든지 간에 말이죠.
시간 복잡도는 대략 O(n^6) 정도 나오게 됩니다만, 상수는 작은 편입니다. 다만 실행 시간은 최대 1.4s대로 좀 빠듯한 편이었습니다.

#include <vector>
#include <string>
#include <queue>
#include <map>
#include <math.h>
#include <cmath>
#include <algorithm>
using namespace std;
map<pair<int, int>, vector<pair<int, int> > > S[3];
int hmax[50][50][50][50];
class ExtendableTriangles
{
    public:
    int gcd(int a, int b) {
        if (b==0) return a;
        return gcd(b, a%b);
    }
    int getCount(vector <string> grid)
    {
        int n = grid.size();
        int m = grid[0].size();
        int g[50][50] = {0};
        int pp1=0, pp2=0, pp0=0;
        for (int i=0; i<n; i++)
            for (int j=0; j<m; j++)
                if (grid[i][j]=='G') g[i][j] = 1, pp1++;
                else if (grid[i][j]=='B') g[i][j] = 2, pp2++;
                else pp0++;
        int total = pp0*pp1*pp2;
        for (int t1=0; t1<=2; t1++) {
            for (int i=-n+1; i<n; i++)
                for (int j=-m+1; j<m; j++) if (i!=0 || j!=0) {
                    int gcd2 = gcd(i, j);
                    if (gcd2==1) {
                        // map<pair<int, int>, vector<pair<int, int> > > S;
                        vector<pair<int, int> > V;
                        int mmax = -9999999, mmin = 9999999;
                        for (int k=0; k<n; k++)
                            for (int l=0; l<m; l++)
                                if (g[k][l] == t1) {
                                    mmax = max(mmax, j*k-i*l);
                                    mmin = min(mmin, j*k-i*l);
                                }
                        for (int k=0; k<n; k++)
                            for (int l=0; l<m; l++)
                                if (g[k][l] == t1)
                                    if (j*k-i*l==mmax || j*k-i*l==mmin)
                                        V.push_back(pair<int, int>(k, l));
                        S[t1][pair<int, int>(i, j)] = V;
            //            printf("%d, (%d %d) -> size %dn", t1, i, j, V.size());
                    }
                }
        }
        for (int a=0; a<n; a++)
            for (int b=0; b<m; b++)
                for (int c=0; c<n; c++)
                    for (int d=0; d<m; d++) {
                        if (c==a && d==b) continue;
                        if (g[a][b]==g[c][d]) continue;
                        pair<int, int> P(c-a, d-b);
                        int ggcd = gcd(P.first, P.second);
                        P.first /= ggcd; P.second /= ggcd;
                        int t1 = 3-g[a][b]-g[c][d];
                        vector<pair<int, int> >* V = &S[t1][P];
                        for (int i=V->size()-1; i>=0; i--) {
                            pair<int, int> Q = (*V)[i];
                            int e = Q.first;
                            int f = Q.second;
                            int area = (c-a)*(b+d)+(e-c)*(d+f)+(a-e)*(f+b);
                            if (area<0) area = -area;
                            hmax[a][b][c][d] = max(hmax[a][b][c][d], area);
            //                printf("check %d %dn", e, f);
                        }
            //            printf("hmax[%d][%d][%d][%d] = %dn", a, b, c, d, hmax[a][b][c][d]);
                    }
        int pretty = 0;
        for (int a=0; a<n; a++)
            for (int b=0; b<m; b++) if (g[a][b]==0)
                for (int c=0; c<n; c++)
                    for (int d=0; d<m; d++) if (g[c][d]==1) {
                        pair<int, int> P(c-a, d-b);
                        int ggcd = gcd(P.first, P.second);
                        P.first /= ggcd; P.second /= ggcd;
                        vector<pair<int, int> >* V = &S[2][P];
                        for (int i=V->size()-1; i>=0; i--) {
                            pair<int, int> Q = (*V)[i];
                            int e = Q.first;
                            int f = Q.second;
                            int area = (c-a)*(b+d)+(e-c)*(d+f)+(a-e)*(f+b);
                            if (area<0) area = -area;
                            if (hmax[a][b][c][d] == hmax[c][d][e][f] && hmax[c][d][e][f]==hmax[e][f][a][b] && hmax[e][f][a][b]==area) pretty ++;
                        }
                    }
        printf("total = %d, pretty = %dn", total, pretty);
        return total-pretty;
    };
};

Hard(900pt, ConnectingAirports)
굉장히 전형적인 형태의 network flow 여러번 돌려보기 문제입니다. 기본적인 접근은 다음과 같습니다.
우선 source - A지역의 airport들을 capacity가 각 airport의 capacity가 되게 해서 연결합니다.
A 지역의 airport들 - B 지역의 airport들 사이를 capacity 1로 연결합니다.
B 지역의 airport들 - sink 사이를 연결하고 capacity를 각 airport의 capacity가 되게 합니다.
그리고 나서...
A지역의 idx 0 airport와 B 지역의 idx 0 airport 사이의 선을 끊어본다. Flow를 돌려봐서 불가능하면, 끊었던 선을 다시 연결해준다.
A지역의 idx 0 airport와 B 지역의 idx 1 airport 사이의 선을 끊어본다. Flow를 돌려봐서 불가능하면, 끊었던 선을 다시 연결해준다.
...
A지역의 idx 0 airport와 B 지역의 idx m-1 airport 사이의 선을 끊어본다. Flow를 돌려봐서 불가능하면, 끊었던 선을 다시 연결해준다.
A지역의 idx 1 airport와 B 지역의 idx 0 airport 사이의 선을 끊어본다. Flow를 돌려봐서 불가능하면, 끊었던 선을 다시 연결해준다.
...
A지역의 idx n-1 airport와 B 지역의 idx m-1 airport 사이의 선을 끊어본다. Flow를 돌려봐서 불가능하면, 끊었던 선을 다시 연결해준다.
마지막으로 불가능한 경우인지 아닌지 체크해서 불가능하면 null을, 아니면 구해놓은 결과를 리턴한다.
인데요, 그냥 구현하면 n<=50임에도 불구하고 TLE가 납니다. 노드 수가 50*2+2 = 102개고, Flow가 O(n^3)이고 구해야 하는 횟수가 O(n^2)라서 O(n^5)는 100억을 훌쩍 넘어가죠. 실제로 아주 많은 수의 순진한 프로그래머들이 이렇게 짰다가 쓴맛을 많이 봤죠.
여기서는 Flow를 incremental하게 짜야 O(n^4)로 줄일 수 있습니다. 일단 Flow를 한번 돌리면, 그 결과를 계속 사용하는 것이죠. 여기에 대해서 생각해보신 분들은, "어라 그럼 끊는 것은 어떻게 처리하지?" 하고 생각하실 수 있는데, 이 경우에는 그래프가 단순하게 생겼기 때문에 곰의 힘(brute force 아님!)으로 끊어버릴 수 있습니다. 아래 소스코드의 revert 함수를 참조하세요. (저는 처음에 H[0][a] = H[a][b] = H[b][1] = 0; 라고 썼다가 디버깅하다 시간 다가서 못냈음 ㅠㅠ)
코드의 절반은 부족전쟁 공격마을-방어마을 매칭 프로그램에서 가져왔습니다. 이 문제는 "공격마을 a에서 방어마을 b까지 병력이 가는 데 걸리는 시간이 t1_i_j로 정해져 있고, 각 방어마을에는 c_i개의 공격마을로부터 공격병력이 도착하게 하고 싶다. 각 방어마을에 병력이 도착하는 시간은 t2_i 이다. 가장 먼저 떠나야 하는 병력의 시간과 가장 늦게 떠나야 하는 병력의 시간의 차이를 최소화하고 싶다." 입니다. 구현은 이 문제의 구현과 거의 같습니다.

#include <vector>
#include <string>
#include <queue>
#include <map>
#include <math.h>
#include <cmath>
#include <algorithm>
using namespace std;
int G[102][102], H[102][102];
int ret = 0;
class ConnectingAirports
{
  public:
void revert(int a, int b)
{
  ret --;
  H[0][a] --; H[a][b] --; H[b][1] --;
  H[a][0] ++; H[b][a] ++; H[a][b] ++;
}
void flow(int n)
{
  while (1) {
    int checked[1000] = {0};
    int from[1000] = {0};
    queue<int> Q;
    Q.push(0);
    checked[0] = 1;
    while (!Q.empty()) {
      int now = Q.front();
      Q.pop();
      for (int i=0; i<n; i++)
        if (!checked[i] && G[now][i]-H[now][i]>0) {
          checked[i] = 1;
          from[i] = now;
          Q.push(i);
        }
    }
    if (!checked[1]) break;
    ret ++;
    int now = 1;
    while (now>0) {
      int prev = from[now];
      H[prev][now] ++;
      H[now][prev] --;
      now = prev;
    }
  }
}
  vector <string> getSchedule(vector <int> A, vector <int> B)
  {
    int sz_a = A.size();
    int sz_b = B.size();
    vector<string> empty;
    vector<string> res(sz_a);
    int capa1 = 0, capa2 = 0;
    for (int i=0; i<sz_a; i++) G[0][i+2] = A[i], capa1 += A[i];
    for (int i=0; i<sz_b; i++) G[i+sz_a+2][1] = B[i], capa2 += B[i];
    if (capa1 != capa2) return empty;
    for (int i=0; i<sz_a; i++)
      for (int j=0; j<sz_b; j++)
        G[i+2][j+sz_a+2] = 1;
    for (int i=0; i<sz_a; i++)
      for (int j=0; j<sz_b; j++) {
        if (H[i+2][j+sz_a+2]) revert(i+2, j+sz_a+2);
        G[i+2][j+sz_a+2] = 0;
        flow(2+sz_a+sz_b);
        if (ret != capa1) G[i+2][j+sz_a+2] = 1;
        res[i] += '0'+G[i+2][j+sz_a+2];
      }
    flow(2+sz_a+sz_b);
    if (ret == capa1) return res;
    return empty;
  };
};

<img src="http://www.topcoder.com/i/clear.gif" alt="" border="0" height="5" width="1">

[이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

15년 전

0개의 댓글이 있습니다.

정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

SINCE 2007

다가오는 이벤트들

[editorial] TCO09 Round 2

0개의 댓글이 있습니다.