Central European Olympiad in Informatics 2016

ICC

$N$개의 정점으로 이루어진 그래프가 있다. 그래프의 초기 상태에는 간선이 하나만 존재한다. 두 정점 집합 사이에 간선이 있는지 묻는 질문을 통해 간선이 무엇인지 알아낸다. 알아낸 이후에 새로운 간선이 또 추가된다. 항상 싸이클이 생기지 않도록 간선이 주어지며, 이 작업을 총 $N-1$번 수행하고 질문을 가능한 적게해야하는 문제다.

처음 상황, 즉, $N$개의 정점이 있고 그들 사이에 간선이 하나만 있는 상황에서 생각해보자. 우선 간선을 가지고 있는 임의의 두 정점 집합을 최대한 적은 질문안에 찾아야한다. 이는 최대 $\lceil\lg N\rceil - 1$번 질문만에 찾을 수 있다. 바로 각 정점 번호를 0번부터 N-1번까지 나타낼 때, 각 비트에 대해 비트값이 0인 집합과 비트값이 1인 집합 사이에 간선이 있는지 질문하면 항상 집합 사이에 간선이 있는 두 서로소 집합이 나온다. 이 때 비트 수 만큼 질문하지 않고, 한 번의 질문을 아낄 수 있다. LSB부터 MSB까지 각 비트에 대해 질문하다가 MSB까지 사이에 간선이 있는 두 집합이 안나오면 MSB에서 나누어지는 두 집합 사이에 항상 간선이 있기 때문이다.

위에서 구한 두 정점 집합을 $G_1$, $G_2$라 하자. 이제 $G_1$에 있는 어떤 정점과 $G_2$에 있는 어떤 정점 사이에 간선이 있다. 간선이 잇는 두 정점은 약 $\lg |G_1| + \lg |G_2|$번의 질문을 통해 찾을 수 있는데 한 번의 질문을 통해 두 정점 집합 중 한 집합의 크기를 절반으로 만들 수 있기 때문이다.

첫 간선을 찾은 이후 그 간선이 잇는 두 정점을 하나의 정점으로 보고 위 알고리즘을 총 $N-1$번 반복해주면 된다. 이 때, 최대로 걸리는 경우를 계산해보면 1625번 안에 나온다.

#include "icc.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define sz(v) ((int)(v).size()) int N; int par[101]; vector <int> member[101]; int cp(int n){ return par[n] == n ? n : (par[n] = cp(par[n])); } void _union(int a, int b) { a = cp(a), b = cp(b); if (a == b) return; if (sz(member[a]) < sz(member[b])) swap(a, b); par[b] = a; for (int t: member[b]) member[a].pb(t); member[b].clear(); } void find_edge(vector <int> cand, vector<int> target) { while (sz(cand) > 1 || sz(target) > 1){ if (sz(cand) > 1){ int m = sz(cand)>>1; vector <int> l, r; for (int i=0;i<m;i++) l.pb(cand[i]); for (int i=m;i<sz(cand);i++) r.pb(cand[i]); int res = query(sz(l), sz(target), l.data(), target.data()); if (res) cand = l; else cand = r; } if (sz(target) > 1){ int m = sz(target)>>1; vector <int> l, r; for (int i=0;i<m;i++) l.pb(target[i]); for (int i=m;i<sz(target);i++) r.pb(target[i]); int res = query(sz(l), sz(cand), l.data(), cand.data()); if (res) target = l; else target = r; } } setRoad(cand[0], target[0]); _union(cand[0], target[0]); } void find() { vector <int> arr; for (int i=1;i<=N;i++) if (cp(i) == i) arr.pb(i); for (int i=0;(1<<i)<sz(arr);i++){ vector <int> left, right; for (int j=0;j<sz(arr);j++){ if ((j>>i)&1) left.pb(arr[j]); else right.pb(arr[j]); } vector <int> larr, rarr; for (int p: left) for (int t: member[p]) larr.pb(t); for (int p: right) for (int t: member[p]) rarr.pb(t); int res = 0; if ((1<<(i+1)) < sz(arr)){ res = query(sz(larr), sz(rarr), larr.data(), rarr.data()); } else res = 1; if (res){ find_edge(larr, rarr); return; } } } void run(int n) { N = n; for (int i=1;i<=N;i++) par[i] = i, member[i] = {i}; for (int i=1;i<N;i++) find(); }

Kangaroo

N개의 칸으로 이루어진 공간에서 시작점과 도착점이 주어졌을 때, 왼쪽-오른쪽-... 아니면 오른쪽-왼쪽-... 번갈아가면서 여행하는 경우의 수를 구하는 문제다.

5개의 칸이 있고 3번 칸에서 시작해서 5번 칸으로 이동하는 수열 [3, 1, 4, 2, 5] 를 그림으로 그려보면 아래와 같이 위 아래로 지그재그함을 알 수 있다.

위와 같은 꼴의 모양 중 맨 왼쪽 점이 시작점이고, 맨 오른쪽이 도착점인 경우의 수를 구하는 문제로 바꿀 수 있다. 경우의 수는 동적계획법으로 해결할 수 있으며, 다이나믹 배열 정의는 아래와 같다.

D[i][j] = 1번부터 i번까지 점을 추가했고 지그재그한 그룹의 개수가 j일 때 경우의 수

위 그림에서 세 개의 네모 영역은 각각 그룹을 나타낸다. 시작점과 도착점을 포함한 그룹을 제외하면 위 그림처럼 그룹 안의 양 끝 점은 아래로 내려가있다. 만약 i번 점이 지그재그의 윗 점이 되는 경우 위 그림처럼 인접한 두 그룹을 합치는 꼴이고, i번 점이 지그재그의 아래 점이 되는 경우 새로운 그룹을 만드는 꼴이다. i번 점이 시작점이거나 도착점인 경우는 조금 다르게 점화식을 세워야한다.

1) i가 시작점, 도착점이 아닌 경우: D[i][j] = D[i-1][j+1] * j + D[i-1][j-1] * (j - 시작점이나 도착점을 포함한 그룹 개수)

2) i가 시작점이거나 도착점인 경우: D[i][j] = D[i-1][j] + D[i-1][j-1]

이처럼 동적계획법을 통해 문제를 $O(N^2)$ 시간안에 해결할 수 있다.

#include <bits/stdc++.h> using namespace std; typedef long long lld; const int MOD = 1e9 + 7; int N, S, T; int D[2002][2002]; int main() { scanf("%d%d%d", &N, &S, &T); D[0][0] = 1; int fixed = 0; for (int i=1;i<=N;i++){ for (int j=1;j<=N;j++){ if (i == S || i == T) D[i][j] = (D[i-1][j] + D[i-1][j-1]) % MOD; else D[i][j] = ((lld)D[i-1][j+1] * j + (lld)D[i-1][j-1] * (j-fixed)) % MOD; } if (i == S || i == T) fixed++; } printf("%d\n", D[N][1]); }

Match

길이가 N인 알파벳 소문자로만 이루어진 문자열이 주어진다. 이 문자열을 괄호문자열로 바꿀 수 있는데, 바꿀 수 있는 괄호문자열 중 사전순으로 제일 앞선 괄호문자열을 구하는 문제다.

현재 문자열의 가장 왼쪽 글자를 $l$이라 하자. 같은 두 글자를 괄호문자열에서 짝이 되는 올바른 괄호문자열이 존재한다는 것을 매칭된다고 표현하자. $[s, e]$는 문자열의 부분문자열을 나타낸다.

Lemma 1) $l$과 매칭되는 가장 오른쪽 글자를 $r$이라 하자. $r$과 $l$을 매칭시켜주는 것이 사전순으로 가장 앞선 괄호문자열을 만든다.

이제 작은 두 문제로 전체 문제를 분할할 수 있다. $[l+1, r-1]$에서 사전순으로 가장 빠른 괄호문자열을 구하고, $[r+1, L]$에서 가장 빠른 괄호문자열을 구하면 전체 문제가 해결된다. $r$을 $O(N)$에 구하면 전체 시간복잡도가 $O(N^2)$이 된다.

전체 문자열에서 첫 번째 글자부터 $i$번째 글자까지 그리디 알고리즘을 돌렸을 때, 스택의 상태를 문자열로 나타내고 이를 $K[i]$라 하자.

Lemma 2) $[s, e]$가 올바른 괄호 문자열을 만들기 위한 필요충분조건은 $K[s-1] = K[e]$이다.

Lemma 3) $l$과 $r$이 매칭되기 위한 필요충분조건은 $l$과 $r$이 같은 알파벳이면서 $[l+1, r-1]$이 올바른 괄호문자열을 만든다는 것이다.

위 두 명제를 통해 $r$을 Trie와 이분탐색을 통해 $O(\lg N)$ 시간안에 구할 수 있다.

#include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() int N, X; char S[MAXN], A[MAXN]; struct NODE{ char me; vector <int> pos[26]; NODE *nxt[26], *prv; } *root, container[MAXN], *lpos[MAXN]; NODE *new_node(char me=0, NODE *prv=0) { NODE *ret = &container[X++]; ret->me = me; ret->prv = prv; return ret; } void solve(int s, int e) { if (s > e) return; NODE *now = lpos[s-1]; auto it = upper_bound(all(now->pos[S[s]-'a']), e); int t = *--it; A[s] = '('; A[t] = ')'; solve(s+1, t-1); solve(t+1, e); } int main() { scanf("%s", S+1); N = strlen(S+1); { vector <int> stk; for (int i=1;i<=N;i++){ if (sz(stk) && stk.back() == S[i]) stk.pop_back(); else stk.pb(S[i]); } if (sz(stk)){ puts("-1"); return 0; } } root = new_node(); lpos[0] = root; NODE *now = root; for (int i=1;i<=N;i++){ if (now->me == S[i]){ now = now->prv; }else{ if (!now->nxt[S[i]-'a']) now->nxt[S[i]-'a'] = new_node(S[i], now); now = now->nxt[S[i]-'a']; } lpos[i] = now; now->pos[S[i]-'a'].pb(i); } solve(1, N); puts(A+1); }