[IOI2013 Day1] Wombats 해법

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day1/wombats/Wombats ko (KOR).pdf

상당히 까다로운 문제다.
이 문제의 해법은 $C$ 값이 $R$ 값에 비해 상대적으로 작다는 사실에서부터 시작한다.

행 X와 행 Y가 있을 때 행 X의 어느 점에서 행 Y의 어느 점으로 가는 $C^2$가지 경우에 대해 사전계산(precompute) 할 수 있다. {X,Y} 를 사전계산 해놓은 것이라 하자. {X,Y}와 {Y,Z}를 합쳐 {X,Z}를 만들 수 있다. 간단하게 합치는 시간복잡도는 $O(C^3)$이지만, Knith-Optimization과 비슷한 방법으로 $O(C^2)$ 시간복잡도를 갖으며 합칠 수 있다. 이를 위해서는 한 가지 중요한 아이디어가 필요하다. 최적 경로가 (X,i)에서 (Z,j-1)로 (Y,p)를 거쳐가고, (X,i+1)에서 (Z,j)로 (Y,q)를 거쳐간다고 하자. 이 때 (X,i)에서 (Z,j)로 가는 최적경로가 (Y,r)을 거쳐간다면 $p \leq r \leq q$ 이다. 이 아이디어는 최적 경로들은 서로 교차하지 않다는데에서 나온다. 쉽게 증명가능하다. 이 사실을 이용하여 j-i 가 증가하는 순서로 $O(C^2)$만에 {X,Y}와 {Y,Z}를 {X,Z}로 합칠 수 있다.

위의 알고리즘과 segment tree를 사용하면 제한시간 내에 문제를 해결할 수 있다. Segment tree의 노드가 [s~e]라면 s번 행에서 e+1번 행까지 가는 $C^2$가지의 전처리된 값들이 있다. Segment tree 구성은 위에서 설명한 방법으로 두 자식 노드를 합치면 된다. 그리고 답을 구하는 것은 segment tree의 루트에 있는 정보를 활용하면 되므로, O(1) 시간복잡도를 갖는다. update 하는데 시간복잡도는 위에서 설명한 방법으로 $O(C^2 \lg R)$ 이 된다.

다만 트리의 정점 개수가 많아 메모리제한을 초과한다. 여기까지하면 76점을 받을 수 있다. 76점에서 100점으로 점수를 끌어올리는 방법은 간단하다. 시간제한이 20초로 매우 넉넉하기 때문에 segment tree의 단말 정점의 구간 크기를 늘려주면 된다. 기존 방법에서 단말 정점의 구간이 [x~x] 라면 [x~x+20] 정도로 늘려주면 된다. 이 때 시간은 기존보다 3배정도 더 걸리며, 시간복잡도에서 상수만 커질 뿐 차수는 변하지 않는다.

#include <bits/stdc++.h> #include "wombats.h" using namespace std; const int LEAF_SIZE = 20, MAXC = 201; static int R, C; static int H[5001][201], V[5001][201]; struct NODE{ NODE(): left(0) ,right(0){ memset(to, 0, sizeof(to)); } int to[MAXC][MAXC]; NODE *left, *right; } *root; void combine(int a[MAXC][MAXC], int b[MAXC][MAXC], int c[MAXC][MAXC]) { int opt[MAXC+1][MAXC+1]={0,}; for (int diff=-C+1;diff<C;diff++){ // diff = j-i for (int i=1;i<=C;i++){ int j = i+diff; if (j < 1 || j > C) continue; a[i][j] = 2e9; int l = opt[i][j-1] ? opt[i][j-1] : 1, r = opt[i+1][j] ? opt[i+1][j] : C; for (int k=l;k<=r;k++){ int v = b[i][k] + c[k][j]; if (a[i][j] > v) a[i][j] = v, opt[i][j] = k; } } } } void calc(int to[MAXC][MAXC], int s, int e) { int my_to[MAXC][MAXC] = {0,}, tmp[MAXC][MAXC] = {0,}, sum[MAXC] = {0,}; for (int i=1;i<=C;i++) for (int j=1;j<=C;j++) to[i][j] = i == j ? 0 : 1e9; for (int r=s;r<=e;r++){ for (int j=1;j<=C;j++) for (int k=1;k<=C;k++){ tmp[j][k] = to[j][k] + (r > s ? V[r-1][k] : 0); } for (int j=2;j<=C;j++) sum[j] = sum[j-1] + H[r][j-1]; for (int j=1;j<=C;j++) for (int k=j;k<=C;k++){ my_to[j][k] = my_to[k][j] = sum[k]-sum[j]; } combine(to, tmp, my_to); } } NODE* make_tree(int s, int e) { NODE *ret = new NODE(); if (e-s < LEAF_SIZE){ calc(ret->to, s, e+1); return ret; } int m = (s+e) >> 1; ret->left = make_tree(s, m); ret->right = make_tree(m+1, e); combine(ret->to, ret->left->to, ret->right->to); return ret; } void update(NODE *now, int s, int e, int l, int r) { if (r < s || e < l) return; if (e-s < LEAF_SIZE){ calc(now->to, s, e+1); return; } int m = (s+e)>>1; update(now->left, s, m, l, r); update(now->right, m+1, e, l, r); combine(now->to, now->left->to, now->right->to); } void init(int r, int c, int h[5000][200], int v[5000][200]) { R = r, C = c; for (int i=1;i<=R;i++) for (int j=1;j<C;j++) H[i][j] = h[i-1][j-1]; for (int i=1;i<R;i++) for (int j=1;j<=C;j++) V[i][j] = v[i-1][j-1]; root = make_tree(1, R-1); } void changeH(int y, int x, int v) { H[++y][++x] = v; update(root, 1, R-1, y-1, y); } void changeV(int y, int x, int v) { V[++y][++x] = v; update(root, 1, R-1, y, y); } int escape(int t1, int t2) { return root->to[++t1][++t2]; }