IOI2015 개막 . 연습 세션 문제 설명

카자흐스탄 알마티에서 열리는 IOI 2015가 오늘 개막했다.

이전 IOI와 다르게 이번 IOI는 한국대표단에 조교로 소속되어 학생들과 같이 현장에 왔다.

출국 전 3주 동안 합숙 훈련을 마친 학생들에게 좋은 성적을 기대해본다.

원래 연습 세션 문제는 풀이를 적지 않지만, 문제가 상당히 괜찮아보여 처음으로 적어보려한다.

관련 자료들은 여기에서 다운받을 수 있다.

1. search

문제: search.pdf

정렬되어 있는 배열이 입력으로 들어오므로 이분 검색을 통해 위치를 구하면 되는 아주 쉬운 문제다. 배열의 크기가 최대 100번이므로 7번의 질문으로 위치를 구할 수 있다.

#include "graderlib.h" int find(int sub, int N, int X) { int s = 0, e = N-1, t; while (s <= e){ int m = (s+e)>>1; int v = compare(m, X); if (v > 0) s = m+1; else if (v) e = m-1; else return m; } return -1; }

2. divide

문제: divide.pdf

"S[i] = 1 번째 수 부터 i 번째 수 까지 XOR 한 값" 으로 배열 S를 정의하자.

j+1 번째 수 부터 i 번째 수 까지 XOR 한 값은 S[i] $\oplus$ S[j]가 된다.

"D[i] = 처음부터 i번째 수 까지만 있다고 가정했을 때 나눌 수 있는 구간의 최대 개수" 으로 DP배열을 정의하자.

점화식은 다음과 같다. D[i] = max(D[j] + 1) (단, 0 ≤ j < i이며 S[i] $\oplus$ S[j] ≤ M, D[0] = 0, S[0] = 0)

기본적으로 위 알고리즘은 $O(N^2)$의 시간복잡도를 갖는다.

문제에서 주어지는 수의 비트 수를 $X$라 하자. 

어떤 i에 대해 S[i] $\oplus$ S[j] ≤ M을 만족하는 j 들을 찾기 위해 우리는 수들을 이진수로 나타내고 가능한 S[j]의 binary prefix에 대해 최대값을 빠르게 탐색, 기록하기 위해 trie 구조를 사용한다.

예를 들어, S[i] = $110110_{(2)}$, M = $100010_{(2)}$라고 했을 때, 고려해야되는 prefix는 $1?????_{(2)}$, $01011?_{(2)}$, $010100_{(2)}$ 세 가지가 된다. 즉, '?' 자리에는 아무 수나 올 수 있고 저런 패턴을 가진 S[j]만이 S[i] $\oplus$ S[j] ≤ M가 된다. 이러한 패턴은 최대 X개 있을 수 있다.

총 시간복잡도는 $O(NX)$가 된다.

#include <bits/stdc++.h> using namespace std; #define MAXN 100005 static int S[MAXN], D[MAXN]; struct NODE{ NODE(): mx(0){ nxt[0] = nxt[1] = 0; } int mx; NODE *nxt[2]; } *root; int solve(int N, int M, int A[]) { for (int i=1;i<=N;i++) S[i] = S[i-1] ^ A[i-1]; root = new NODE(); { NODE *now = root; for (int i=0;i<30;i++){ now->nxt[0] = new NODE(); now = now->nxt[0]; } } for (int i=1;i<=N;i++){ D[i] = -1; NODE *now = root; for (int j=30;j--;){ int a = (S[i]>>j)&1, b = (M>>j)&1; int c = a^b; if (b && now->nxt[!c]) D[i] = max(D[i], now->nxt[!c]->mx + 1); now = now->nxt[c]; if (!now) break; } if (now) D[i] = max(D[i], now->mx+1); if (D[i] < 0) continue; now = root; for (int j=30;j--;){ int v = (S[i]>>j)&1; if (!now->nxt[v]) now->nxt[v] = new NODE(); now = now->nxt[v]; now->mx = max(now->mx, D[i]); } } return D[N]; }

3. graph

문제: graph.pdf

준비 중.