IOI 2017 Day 1 문제 및 해법

문제: 공식 홈페이지

채점: Yandex

1. nowruz

 

이 문제는 빈 칸과 장애물로 이루어진 직사각형 모양의 격자칸에서 빈 칸에 새로운 장애물을 적절히 넣어, 격자판의 빈 칸들을 트리 모양으로 만든다. 이 때, 만들어지는 트리에 포함된 리프 정점 수를 최대화하는 문제다.

 

IOI 2010 Maze 문제와 비슷한 감이 있는 문제다. 문제 세팅 자체도 2차원 격자판이라는 것도 비슷하지만, 최적해가 아니라 최적근접해를 구하는 output only 문제라는 사실이 비슷하다. 이런 류의 문제는 TopCoder Marathon Match 줄여서 MM에 주로 나오는 것으로 알고 있다.

 

예전에 maze 문제를 해결할 때, 공부에 도움이 됐던 일루님의 글을 소개하고, 이 문제에 맞는 자세한 풀이는 추후 시간이 나면 추가하겠다.

 

풀이 준비 중 입니다.

 

 

2. wiring

 

1차원 직선위에 빨간점 $N$개와 파란점 $M$개가 서로 다른 위치에 놓여있다. 이 때, 각 점은 하나 이상의 다른 색상의 점과 연결되어야하고, 연결할 때 필요한 전선 길이의 합을 최소화하는 문제다.

 

서로 다른 색의 두 점을 연결하는 것을 매칭이라고 하고, 매칭할 때 필요한 전선 길이를 매칭 비용이라고 하자. 각 점마다 적어도 한 개 이상의 매칭이 필요하므로 각 점마다 한 개씩 의무적으로 해주는 매칭이 있다. 점 $a$와 점 $b$를 연결하는 매칭이 있다라고 하면 이 매칭은 아래 세 가지 중 하나를 만족한다.

 

1) 매칭이 점 $a$ 입장에서만 의무적인 경우

2) 매칭이 점 $b$ 입장에서만 의무적인 경우

3) 매칭이 점 $a$와 점 $b$ 모두에게 의무적인 경우

 

처음에 입력으로 빨간점의 좌표와 파란점의 좌표가 각각 정렬되어 들어오는데, 이를 merge 하여 하나의 정렬된 배열로 만든다. 그리고 좌표 순서대로 번호를 매기고, 아래와 같은 DP를 생각하자.

 

D[i] = 점 $i$까지 의무적인 매칭이 완료되었을 때, 필요한 최소 매칭 비용

 

점 $i$ 입장에서 의무적으로 한 개의 매칭을 해줘야하는데, 이는 두 가지 경우 중 하나가 된다.

 

1) 점 $i$ 입장에서 의무적인 매칭이 상대방에게는 의무가 아닌 경우

이 경우 점 $i$는 양 옆 주변으로 가장 가까운 다른 색의 점과 매칭해주면 된다.

 

2) 점 $i$ 입장에서 의무적인 매칭이 상대방에게도 의무인 경우

이 경우 점 $i$는 왼쪽에 있는 점 $j$와 매칭이 된다고만 봐도 된다. 그리고 점 $j$와 점 $i$ 사이의 빨간점의 수와 파란점의 수가 같을 때만 고려해도 optimal 매칭을 구할 수 있다는 것도 알 수 있다. 마지막으로 앞의 조건을 만족하는 점 $j$가 여러 개일 때, 그 중 가장 오른쪽에 있는 점 $j$와 매칭하는 경우만 고려해도 모든 경우를 커버한다는 것도 알 수 있다. 따라서, 매칭되는 점 $j$는 존재하지 않거나 유일하다.

 

두 경우 각각에 대해 매칭 비용을 구하고 더 좋은 비용을 선택하면 D[i]를 구할 수 있다. 이러한 DP는 $O(N+M)$ 시간에 해결되며 최종적으로 답은 D[N+M]이 된다.

 

여담) 이 문제는 ACM ICPC Seoul Regional 2007 J번 문제와 완전히 동일한 문제고, 이 문제에 대한 풀이를 cubelover가 블로그에 작성한 적이 있다. cubelover 블로그에 작성된 풀이는 내 풀이와 같은 풀이지만 조금 다른 단어로 자세히 설명되어 있다.

 

#include <bits/stdc++.h> using namespace std; using lld = long long; lld min_total_length(std::vector<int> A, std::vector<int> B){ int N = size(A), M = size(B); int K; pair<int, bool> C[N+M+1]; for (int i=0,j=0;i<N||j<M;){ if (j == M || i < N && A[i] < B[j]) C[++K] = {A[i++], 0}; else C[++K] = {B[j++], 1}; } lld S[K+1]; int lvl = 0; int last[K+1]; fill(last, last+K+1, -1); last[N] = 0; lld D[K+1]; D[0] = 0; for (int i=1,p=0,q=0;i<=K;i++){ while (p+1 < N && A[p+1] <= C[i].first) p++; while (q+1 < M && B[q+1] <= C[i].first) q++; S[i] = S[i-1]; int d; if (C[i].second){ S[i] += C[i].first, lvl++; d = abs(C[i].first-A[p]); if (p+1 < N) d = min(d, abs(C[i].first-A[p+1])); } else{ S[i] -= C[i].first, lvl--; d = abs(C[i].first-B[q]); if (q+1 < M) d = min(d, abs(C[i].first-B[q+1])); } D[i] = D[i-1]+d; if (int j = last[lvl+N]; j != -1){ D[i] = min(D[i], D[j]+abs(S[i]-S[j])); } last[lvl+N] = i; } return D[K]; }

 

3. train

 

$N$개의 정점이 있고, $M$개의 간선이 있는 방향성 그래프가 주어진다. 두 사람 A와 B가 게임을 진행한다. 이 중 1개 이상의 정점은 충전소가 놓여있고, 각 정점마다 A, B 두 사람 중 한 사람이 주인이 된다. 기차가 어떤 시작점에서 시작하여 이동을 시작한다. 기차가 어떤 정점에 최초로 도착하면 해당 정점의 주인이 그 정점에서 나가는 간선 중 하나를 선택하고 거기로 나간다. 이후 방문했을 때도, 이전에 정한 간선을 따른다. 이후에 기차는 같은 곳을 계속 돌게 되는데 도는 곳에 충전소가 있으면 A의 승리, 없으면 B의 승리다. 서로 최선을 다할 때, 각 정점마다 시작점이 될 때 누가 이기는지 구하는 문제다.

 

이 문제에서 정점에 최초로 방문했을 때, 나가는 간선을 고르고 이후에도 유지가 된다고 적혀있다. 하지만 이러한 조건이 없어도 게임의 내용은 전혀 변하지 않는다. 즉, 정점을 방문할 때마다 나가는 간선을 고르는 것으로 문제 상황을 바꿔도 정확히 동일한 문제가 된다.

 

B의 승리가 확실한 시작점들을 계속 구해나갈 것이다. 우선 이를 위해, A가 어떤 간선을 선택하더라도 절대로 충전소로 갈 수 없는 시작점들의 집합을 $S$라고 할 때, 집합 $S$는 $S$의 여집합을 구하는 방식으로 아래와 같은 방법으로 찾아나갈 수 있다:

 

1) 처음에 집합 $S$에 모든 정점들을 넣는다. 그리고 모든 충전소를 집합 $S$에서 지운다.

2) 주인이 A인 정점 $v$에 대해서, $v$에서 나가는 모든 간선이 집합 $S$에 없는 정점을 향한다면, 정점 $v$를 집합 $S$에서 지운다.

3) 주인이 B인 정점 $v$에 대해서, $v$에서 집합 $S$에 없는 정점으로 향하는 간선이 있다면, 정점 $v$를 집합 $S$에서 지운다.

4) 이를 반복한다.

 

집합 $S$에 있는 정점들은 시작점이 될 때 B의 승리가 확실한 정점들이다. 집합 $S$에 없더라도 B의 승리가 확실한 정점을 더 구할 수 있는데, 바로 A가 어떤 간선을 선택하더라도 반드시 집합 $S$에 속한 정점으로 오게되는 시작점들이다. 위에서 언급한 방법과 비슷한 방법으로 이러한 정점들을 구할 수 있다. 위의 방법은 위상정렬할 때, in degree가 0인 정점들을 계속 지워주는 것과 비슷한 방식으로 queue를 이용하여 총 시간복잡도 $O(M)$에 구현할 수 있다.

 

다음과 같은 그래프를 생각해보자. 정점의 주인은 모두 A라고 하자. 아래의 그래프에서 집합 $S$에는 2번 정점만 있게 되고, 추가적으로 1번 정점까지 B의 승리가 확실한 시작점이 된다. 하지만, 0번 정점은 실제로 B의 승리가 확실한 정점임에도 불구하고 구하지 못한다.

 

 

이유는 0번 정점은 A가 간선을 잘 선택하면 충전소에 갈 수도 있고, 또 간선을 잘 선택하면 집합 $S$에 속한 정점으로 가지 않을 수도 있기 때문이다. 좀 더 자세히 말하자면 0번 정점처럼 충전소에 가면 어쩔 수 없이 집합 $S$에 속한 정점으로 이동하게 되는 정점에 대한 처리가 남았다.

 

B의 승리가 확실한 시작점 중에 만약 충전소가 있다면 이는 의미가 전혀 없는 충전소가 된다. 이러한 충전소들을 지우고 같은 과정을 최대 $N$번 반복하면 0번 정점 같은 B의 승리가 확실한 정점들도 찾을 수 있다. 한 번 과정을 진행할 때마다 $O(M)$의 시간이 걸리므로, 총 시간복잡도 $O(NM)$에 B의 승리가 확실한 정점들을 모두 찾을 수 있고, B의 승리가 확실하지 않은 정점은 A의 승리가 확실하다는 것도 알 수 있다. 따라서 문제를 해결했다.

 

#include "train.h" #include <bits/stdc++.h> using namespace std; #define MAXN 5003 #define pb push_back #define sz(v) ((int)(v).size()) int N, M; int out_deg[MAXN]; vector <int> from[MAXN]; bool A[MAXN], R[MAXN]; bool S[MAXN], WB[MAXN]; int C[MAXN]; vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) { N = sz(a); M = sz(u); for (int i=0;i<M;i++){ int a = ++u[i], b = ++v[i]; from[b].pb(a); out_deg[a]++; } for (int i=1;i<=N;i++){ A[i] = a[i-1]; R[i] = r[i-1]; } for (;;){ queue <int> que; for (int i=1;i<=N;i++){ S[i] = R[i]; if (S[i]) que.push(i); C[i] = 0; } while (!que.empty()){ int q = que.front(); que.pop(); for (int t: from[q]) if (!S[t]){ C[t]++; if (A[t] && C[t] || !A[t] && C[t] == out_deg[t]) S[t] = 1, que.push(t); } } for (int i=1;i<=N;i++){ WB[i] = !S[i]; if (WB[i]) que.push(i); C[i] = 0; } while (!que.empty()){ int q = que.front(); que.pop(); for (int t: from[q]) if (!WB[t]){ C[t]++; if (A[t] && C[t] == out_deg[t] || !A[t] && C[t]) WB[t] = 1, que.push(t); } } bool sw = 0; for (int i=1;i<=N;i++) if (R[i] && WB[i]) sw = 1, R[i] = 0; if (!sw) break; } vector <int> ret; for (int i=1;i<=N;i++) ret.pb(!WB[i]); return ret; }