[IOI2011 Day1] Garden 해법

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/garden.pdf

대회 때, 문제가 너무 어려워 보여 별다른 도전을 하지 못한 채 49점을 받았다. 최근에 문제를 다시 풀어보았을 때, 노가다 문제임을 알 수 있었고, 까다로운 코딩 끝에 만점을 받을 수 있었다. 대회 때 문제를 풀지 못한 것에 대한 아쉬움이 커졌다.

이 문제는 69점을 받는 방법이 딱히 생각 나지 않는다. 다만, 코딩할 때 배열 대신 vector를 썼을 때 시간초과로 69점을 받게 됬다. vector를 배열로 고치니 넉넉하게 만점이 나왔다. 대회 때 69점 받은 사람이 상당히 많은데, 69점을 받기 위한 쉬운 방법이 있는지 잘 모르겠다.

문제의 해법에 접근하게 위해서 몇 가지 관찰이 필요하다.

• 어떤 노드 i에서 시작했을 때, 생기는 경로는 유일하다.
• 어떤 노드 i에서 시작했을 때, 생기는 경로의 꼬리 부분에 싸이클이 존재한다.
• 어떤 노드 i에서 발생할 수 있는 상황은 2가지이다.
  1. 가장 아름다운 산책로를 이용할 수 있는 경우
  2. 두번째로 아름다운 산책로를 선택할 수 밖에 없는 경우

이런 관찰들로 어떤 노드 i에서 1번 경우일 때와 2번 경우 일 때 경로가 어떻게 구성되는지를 DFS 로 구해 놓으면 된다. 각 경로에 도착지인 P가 어디에 위치하는지 저장해놓으면 된다. 다만 경로에서 P가 여러 곳에 위치할 수 있음을 간과해서는 안된다. 이를 간과하지 않으면 직관적이게 해결할 수 있다. 쿼리별로 시간복잡도 $O(N)$만에 해결할 수 있다.

총 시간복잡도는 $O(QN)$ 이다.

이 문제의 해법을 생각하기는 매우 쉽다. 다만 예외의 경우가 몇 가지 있어, 코딩할 때 실수하기 쉬워 어렵다.

#include "garden.h" #include "gardenlib.h" #include <stack> using namespace std; #define MAXN 150004 #define mp make_pair typedef pair<int,int> pii; static int N,M,P; static int out[MAXN][2],in_stk[MAXN][2]; static stack<pii> stk; static struct INFO{ int line_len,cycle_size; int p_type[2],p_pos[2]; bool visited; } D[MAXN][2]; void dfs(int n,int m,int dep) { if (D[n][m].visited) return; D[n][m].visited = 1; in_stk[n][m] = dep; stk.push(mp(n,m)); int p = out[n][m], q = (n==out[out[n][m]][0]&&out[out[n][m]][1]); if (in_stk[p][q]){ // find cycle int csize = dep-in_stk[p][q]+1; while (!stk.empty()){ int x = stk.top().first, y = stk.top().second; stk.pop(); if (x == P){ D[n][m].p_type[y] = 2; D[n][m].p_pos[y] = (in_stk[x][y]-in_stk[p][q]+1)%csize; } D[x][y].line_len = 0; D[x][y].cycle_size = csize; in_stk[x][y] = 0; if (x == p && y == q) break; } return; } int i; dfs(p,q,dep+1); if (D[n][m].cycle_size){ // (n,m) is in cycle for (i=0;i<2;i++) if (D[p][q].p_type[i] == 2){ D[n][m].p_type[i] = 2; D[n][m].p_pos[i] = (D[p][q].p_pos[i]+1)%D[p][q].cycle_size; } }else{ D[n][m].cycle_size = D[p][q].cycle_size; D[n][m].line_len = D[p][q].line_len+1; for (i=0;i<2;i++){ D[n][m].p_type[i] = D[p][q].p_type[i]; D[n][m].p_pos[i] = D[p][q].p_type[i]==1?D[p][q].p_pos[i]+1:D[p][q].p_pos[i]; } if (n == P){ D[n][m].p_type[m] = 1; D[n][m].p_pos[m] = 0; } } in_stk[n][m] = 0; } bool check(int n,int k) { int i; INFO &t = D[n][0]; for (i=0;i<2;i++){ if (t.p_type[i] == 1){ if (t.p_pos[i] == k) return 1; }else if (t.p_type[i] == 2){ if (k >= t.line_len && (k-t.line_len)%t.cycle_size == t.p_pos[i]) return 1; } } return 0; } void count_routes(int n,int m,int p,int R[][2],int Q,int G[]) { int i,j; N = n; M = m; P = ++p; for (i=M;i--;){ int a = R[i][0]+1, b = R[i][1]+1; out[a][1] = out[a][0]; out[a][0] = b; out[b][1] = out[b][0]; out[b][0] = a; } for (i=1;i<=N;i++) for (j=0;j<2;j++) dfs(i,j,1); for (i=0;i<Q;i++){ int ans = 0; for (j=1;j<=N;j++){ if (check(j,G[i])) ans++; } answer(ans); } }

---

댓글로 한 분이 69점 받을 수 있는 방법을 알려주셨다. 그 방법을 자세히 소개하겠다.

우선 쿼리별로 시간복잡도가 $O(N lg K)$ 이기 때문에 100점이 아닌 69점이 나온다. 각 노드 별로 1번 이동한 후, 2번 이동한 후, 4번 이동한 후, ..., $2^i$번 이동한 후 도착지를 계산해놓으면 된다. 미리 계산하는 시간복잡도 또한 $O(N lg K)$ 이다. 계산할 때 노드에 도착하고 다음 이동 할 때, 가장 아름다운 도로로 이동하게 될 수도 있고, 두 번째 아름다운 도로로 이동하게 될 수도 있음을 주의해야한다.

총 시간복잡도는 $O(Q\bullet N lg K)$ 이다.