2014 Benelux Algorithm Programming Contest

코드포스 GYM 링크

A. Avoiding the Apocalypse

내가 아직 풀지 않았다.

B. Button Bashing

$n$ 종류의 버튼을 눌러 전자레인지의 시간을 맞추는 문제다. 시간은 음수가 될 수 없고, 1시간보다 많이 지날 수 없기 때문에 0~3600 사이에서 BFS를 돌리면 된다.

#include <stdio.h> #include <queue> using namespace std; int T, N, K; int D[3601], A[17]; int main() { int i, j; for (scanf("%d", &T);T--;){ scanf("%d%d", &N, &K); for (i=1;i<=N;i++) scanf("%d", A+i); for (i=0;i<3601;i++) D[i] = 2e9; D[0] = 0; queue <int> que; que.push(0); while (!que.empty()){ int q = que.front(); que.pop(); for (i=1;i<=N;i++){ int k = q+A[i]; if (k > 3600) k = 3600; if (k < 0) k = 0; if (D[k] == 2e9) D[k] = D[q]+1, que.push(k); } } for (i=K;i<3601;i++) if (D[i] < 2e9) break; printf("%d %d\n", D[i], i-K); } }

C. Citadel Construction

2차원 좌표 평면에 $n$개의 점이 있을 때, $n$개의 점을 통해 만들 수 있는 삼각형, 사각형 중 최대 넓이를 구하는 문제다.

2013 대전 리저널 D번 문제와 똑같지만 $n \leq 1000$으로 제한이 작다. 우선 Graham-Scan으로 $O(N \lg N)$만에 Convex-Hull을 구한다. 답이 되는 점들은 Convex-Hull을 이루는 점들 중에 있음이 자명하다.

최대 넓이를 구하기 위한 $O(N^2)$ 방법으로는 점 $i$를 잡고 점 $j$를 반시계방향 순서대로 진행했을 때, 직선 $\overline{ij}$ 에서 양 면으로 가장 먼 점 두 개를 잡아 사각형의 면적을 구하면 된다. 이 때 $j$가 반시계방향으로 이동함에 따라, 양 면에서 가장 먼 두 점 또한 반시계 방향으로 이동하게 되므로 $O(N^2)$ 시간안에 계산할 수 있다. 이러한 작업을 rotating-calipers 라고 부른다.

#include <stdio.h> #include <algorithm> using namespace std; #define MAXN 1004 int T, N; int X, Y; int stk[MAXN], scnt; int ccw(int ax, int ay, int bx, int by, int cx, int cy) { int k = (bx-ax)*(cy-ay) - (cx-ax)*(by-ay); if (k > 0) return 1; if (k) return -1; return 0; } struct Z{ int x, y; bool operator < (const Z &ot)const{ int v = ccw(X, Y, x, y, ot.x, ot.y); return v > 0 || v == 0 && (y < ot.y || y == ot.y && x < ot.x); } } A[MAXN]; int triangle(const Z &a, const Z &b, const Z &c) { return abs((a.x*b.y+b.x*c.y+c.x*a.y)-(a.x*c.y+b.x*a.y+c.x*b.y)); } int main() { int i, j, k; for (scanf("%d", &T);T--;){ scanf("%d", &N); for (i=1;i<=N;i++) scanf("%d%d", &A[i].x, &A[i].y); for (i=k=1;i<=N;i++) if (A[k].y > A[i].y || A[k].y == A[i].y && A[k].x > A[i].x) k = i; swap(A[1], A[k]); X = A[1].x, Y = A[1].y; sort(A+2, A+N+1); scnt = 0; stk[++scnt] = 1; stk[++scnt] = 2; for (i=3;i<=N;i++){ while (scnt > 1 && ccw(A[stk[scnt-1]].x, A[stk[scnt-1]].y, A[stk[scnt]].x, A[stk[scnt]].y, A[i].x, A[i].y) <= 0) stk[scnt--] = 0; stk[++scnt] = i; } if (scnt < 3){ puts("0"); continue; } if (scnt == 3){ int a = triangle(A[stk[1]], A[stk[2]], A[stk[3]]); printf("%d%s\n", a>>1, a&1?".5":""); continue; } int ans = 0; for (i=1;i<=scnt;i++){ int p = i+1, q = i+3; if (q > scnt) q -= scnt; for (j=i+2;j<=scnt;j++){ if (i == 1 && j == scnt) continue; while (p+1 < j && triangle(A[stk[i]], A[stk[j]], A[stk[p]]) <= triangle(A[stk[i]], A[stk[j]], A[stk[p+1]])) ++p; while (q%scnt+1 != i && triangle(A[stk[i]], A[stk[j]], A[stk[q]]) <= triangle(A[stk[i]], A[stk[j]], A[stk[q%scnt+1]])) q = q%scnt+1; ans = max(ans, triangle(A[stk[i]], A[stk[j]], A[stk[p]]) + triangle(A[stk[i]], A[stk[j]], A[stk[q]])); } } printf("%d%s\n", ans>>1, ans&1?".5":""); } }

D. Dropping Directions

사거리가 $N$개 있고, 그 중 한 사거리가 도착점으로 주어진다. 사거리 사이에서 이동 규칙이 있을 때, 최소 개수의 이정표를 세워 도착점으로 도달하게 하는 문제다.

들어오는 방향을 기준으로 하나의 사거리를 4개의 정점으로 분리할 수 있다. 이 정점들은 in degree가 1이고, out degree 또한 1이며, 하나의 고리 형태를 구성한다. 이 고리들 중 도착점을 포함하지 않은 고리의 개수가 정답이다.

#include <stdio.h> #define MAXN 100005 int T, N, G; int A[MAXN][4], D[MAXN][4]; bool V[MAXN][4]; void dfs(int n, int d, int &inc) { if (V[n][d]) return; if (n == G) inc = 1; V[n][d] = 1; dfs(A[n][d], (D[n][d]+2)%4, inc); } int main() { int i, j, k; for (scanf("%d", &T);T--;){ scanf("%d%d", &N, &G); for (i=1;i<=N;i++) for (j=0;j<4;j++) scanf("%d", A[i]+j), V[i][j] = 0; for (i=1;i<=N;i++) for (j=0;j<4;j++){ for (k=0;k<4;k++) if (A[A[i][j]][k] == i) D[i][j] = k; } int ans = 0; for (i=1;i<=N;i++) for (j=0;j<4;j++) if (!V[i][j]){ int inc = 0; dfs(i, j, inc); if (!inc) ans++; } printf("%d\n", ans>>1); } }

E. Excellent Engineers

$n$명의 사람이 있고 세 분야에 대해서 등수를 매겼다. 세 분야 모두 자신보다 앞선 사람이 없는 사람의 수를 구하는 문제다.

우선 첫 분야를 기준으로 정렬한다. 그러면 이제 정렬되지 않은 두 분야 문제로 바뀐다. 이는 두 번째 분야 등수를 indexed tree의 index로 삼고, 세 번째 분야 등수를 value로 삼아서 index tree를 돌리면 해결할 수 있다.

#include <stdio.h> #include <algorithm> using namespace std; #define MAXN 100005 #define TS 262144 int T, N; int tree[TS], ST, SZ; struct Z{ int a, b, c; bool operator < (const Z&ot)const{ return a < ot.a; } } A[MAXN]; void reg(int n, int v) { for (n+=ST;n;n>>=1) if (tree[n] > v) tree[n] = v; } int get_min(int l, int r) { int ret = 2e9; for (l+=ST,r+=ST;l<=r;l>>=1,r>>=1){ if (l&1){ if (ret > tree[l]) ret = tree[l]; l++; } if (!(r&1)){ if (ret > tree[r]) ret = tree[r]; r--; } } return ret; } int main() { int i; for (scanf("%d", &T);T--;){ scanf("%d", &N); for (i=1;i<=N;i++) scanf("%d%d%d", &A[i].a, &A[i].b, &A[i].c); sort(A+1, A+N+1); for (ST=1;ST<N;ST<<=1); SZ = ST+ST; ST--; for (i=1;i<SZ;i++) tree[i] = 2e9; int ans = N; for (i=1;i<=N;i++){ int v = get_min(1, A[i].b-1); if (v < A[i].c) ans--; reg(A[i].b, A[i].c); } printf("%d\n", ans); } }

F. Floating Formation

그래프에 $n$개의 정점이 있고, $m$개의 간선이 있다. 차수가 1인 노드는 없어진다. 새로 차수가 1인 노드가 생기면 그 노드 또한 없어진다. 배를 정점에 연결하면 정점의 차수가 늘어나 정점이 없어지는 것을 방지할 수 있다. $k$개의 배를 사용할 수 있을 때, 가라 앉는 정점의 개수를 최소화하는 문제다.

그래프가 주어졌을 때, 싸이클에 포함되어 있는 정점은 없어지지 않는다. BCC(Biconnected Component)를 통해 그러한 정점들을 구할 수 있다. 문제 조건에 따라 초기 상태에서 없어지지 않는 정점이 존재한다. 없어지지 않는 정점들 중 하나를 트리의 루트로 삼는 BCC를 구한다. 싸이클에 포함되어 있는 정점들을 색칠하고, 그 정점들의 조상 정점들을 모두 색칠한다. 이 때 색칠된 정점들이 최종적으로 없어지지 않는 정점들이 된다.

이제 $k$개의 배를 적절히 사용하여 없어지지 않는 정점들의 개수를 최대화 해야한다. 이는 트리에서 말단 정점들을 선택하여 조상까지 모두 색칠할 때 최대로 색칠하는 문제이며, KOI 2013년 고등부 4번 수족관3 문제에서 사용한 욕심쟁이 기법으로 해결할 수 있다. 그 욕심쟁이기법은 매순간 최대로 색칠할 수 있는 정점이 많은 말단 정점들 순서대로 색칠하는 방법이다.

#include <stdio.h> #include <queue> #include <vector> using namespace std; #define MAXN 10004 #define mp make_pair #define pb push_back typedef pair<int,int> pii; int T, N, M, K, R, H[MAXN], B[MAXN], P[MAXN], S[MAXN], L[MAXN]; bool V[MAXN]; vector <int> con[MAXN]; void dfs(int n) { B[n] = 2e9; S[n] = 0; L[n] = n; for (int t: con[n]){ if (!H[t]){ P[t] = n, H[t] = H[n]+1, dfs(t); if (B[n] > B[t]) B[n] = B[t]; if (S[n] < S[t]) S[n] = S[t], L[n] = L[t]; } else if (P[n] != t && B[n] > H[t]) B[n] = H[t]; } ++S[n]; } void color_up(int n) { if (!n || V[n]) return; V[n] = 1; color_up(P[n]); } int main() { int i, j, k; for (scanf("%d", &T);T--;){ scanf("%d%d%d", &N, &M, &K); for (i=1;i<=N;i++) con[i].clear(), V[i] = 0; for (i=1;i<=M;i++){ scanf("%d%d", &j, &k); con[j].pb(k); con[k].pb(j); } for (i=1;i<=N;i++) H[i] = 0; H[1] = 1; P[1] = 0; dfs(1); for (i=1;i<=N;i++) if (B[i] <= H[i]){ R = i; break; } if (R > 1){ for (i=1;i<=N;i++) H[i] = 0; H[R] = 1; P[R] = 0; dfs(R); } for (i=1;i<=N;i++) if (B[i] <= H[i]) color_up(i); priority_queue <pii> que; for (i=1;i<=N;i++) if (!V[i]) que.push(mp(S[i], i)); while (!que.empty() && K){ int q = que.top().second; que.pop(); if (V[q]) continue; K--; color_up(L[q]); } int ans = 0; for (i=1;i<=N;i++) if (!V[i]) ans++; printf("%d\n", ans); } }

G. Growling Gears

$n$개의 기어가 주어지고, RPM에 따른 토크가 기울기가 음수인 포물선으로 주어진다. 최대의 토크를 낼 수 있는 기어 번호를 출력하는 문제다.

포물선이 $-aR^2 + bR + c$로 주어지면, 낼 수 있는 최대 토크는 $c + \frac{b^2}{4a}$다. 분수 비교를 통해 이 값들 중 최대값을 구할 수 있다.

#include <stdio.h> typedef long long lld; int T, N, X[11], Y[11]; int main() { for (scanf("%d", &T);T--;){ scanf("%d", &N); int ans = 1; for (int i=1;i<=N;i++){ int a, b, c; scanf("%d%d%d", &a, &b, &c); X[i] = 4*a*c + b*b; Y[i] = 4*a; if ((lld)X[ans]*Y[i] < (lld)X[i]*Y[ans]) ans = i; } printf("%d\n", ans); } }

H. Highway Hassle

$n$개의 정점이 있고, $m$개의 간선이 있다. $n$개의 정점 중 $s$개의 주유소가 있다. 연료통의 최대 용량은 $t$이며, 주유소 별로 주유 가격이 다를 수 있다. 간선을 지날 때 기름이 닳고 이동 도중 기름이 바닥나면 안된다. 시작점과 도착점이 주어질 때, 시작점에서 도착점으로 가는 최소 주유 비용을 구하는 문제다.

주유소의 개수 $s$의 제한이 $s \leq 120$으로 굉장히 작다. 주유소 사이의 최단 거리를 구하는 것은 Dijkstra 알고리즘을 $s$번 수행하여 구할 수 있다. 주유소 $u$에서 다른 주유소 $v$로 최단 거리로 이동할 때 반드시 아래에 주어진 두 가지 경우 중 하나다.

1. 주유소 $u$에서 기름을 꽉 채워서 가는 경우
2. 주유소 $v$에 도착했을 때 기름이 바닥나는 경우

이에 따라 주유소 별로 주유소에 도착햇을 때 기름이 남은 가능한 경우는 총 $s^2$가지 경우 뿐이다. 이에 대해 Dijkstra 알고리즘을 하면 총 시간복잡도는 $O(s^3 + s(m + n \lg n))$이 된다.

#include <stdio.h> #include <queue> #include <vector> using namespace std; #define MAXN 1004 #define MAXS 139 #define pb push_back #define mp make_pair #define sz(v) ((int)(v).size()) typedef pair<int,int> pii; typedef long long lld; int T, N, M, S, F, ST, ED; int P[MAXS], num[MAXN], w[MAXS][MAXS]; lld D[MAXS][MAXS]; vector <int> con[MAXN], conf[MAXN]; struct Z{ Z(int v=0, int st=0, int fr=0): v(v), st(st), fr(fr) {} int v, st, fr; bool operator < (const Z &ot)const{ return v > ot.v; } }; void dijkstra(int n, int *d_arr) { vector <int> dist(N+1, 2e9); priority_queue <pii> que; dist[n] = 0; que.push(mp(0, n)); while (!que.empty()){ int q = que.top().second, d = -que.top().first; que.pop(); if (dist[q] != d) continue; for (int i=sz(con[q]);i--;){ int k = con[q][i], f = conf[q][i]; if (dist[k] > dist[q]+f) dist[k] = dist[q]+f, que.push(mp(-dist[k], k)); } } for (int i=1;i<=N;i++) if (num[i]) d_arr[num[i]] = dist[i]; } int main() { int i, j, k; for (scanf("%d", &T);T--;){ scanf("%d%d%d%d", &N, &M, &S, &F); for (i=1;i<=N;i++) con[i].clear(), conf[i].clear(), num[i] = 0; while (M--){ scanf("%d%d%d", &i, &j, &k); con[i].pb(j); conf[i].pb(k); con[j].pb(i); conf[j].pb(k); } for (i=1;i<=S;i++){ scanf("%d%d", &k, P+i); num[k] = i; } scanf("%d%d", &ST, &ED); if (!num[ED]) num[ED] = ++S, P[S] = 100; for (i=1;i<=N;i++) if (num[i]){ dijkstra(i, w[num[i]]); } for (i=1;i<=S;i++) for (j=1;j<=S;j++) D[i][j] = 1e16; priority_queue <Z> que; D[num[ST]][num[ST]] = 0; que.push(Z(0, num[ST], num[ST])); while (!que.empty()){ Z q = que.top(); que.pop(); if (q.v != D[q.st][q.fr]) continue; int now_f = q.st == q.fr ? 0 : F - w[q.fr][q.st]; for (i=1;i<=S;i++) if (i != q.st){ if (w[q.st][i] > F) continue; int fr = q.st; int v = (F-now_f) * P[q.st]; if (D[i][fr] > q.v+v) D[i][fr] = q.v+v, que.push(Z(q.v+v, i, fr)); v = max(0, w[q.st][i]-now_f) * P[q.st]; fr = i; if (D[i][i] > q.v+v) D[i][i] = q.v+v, que.push(Z(q.v+v, i, i)); } } printf("%lld\n", D[num[ED]][num[ED]]); } }

I. Interesting Integers

내가 아직 풀지 않았다.

J. Jury Jeopardy

특정 조건을 만족하는 미로가 있고, 그 미로를 돌아다니는 로봇이 이동하는 규칙이 있다. 로봇이 미로를 이동하는 방식이 주어졌을 때, 미로를 구하는 문제다.

미로의 모든 부분을 '#'로 채우고 로봇이 이동하는 곳을 '.'로 바꾸면 된다. 시작점이 어디인지 잘 모를 수 있으므로, 상대적으로 큰 미로판에서 일부 부분만을 출력하면 된다.

#include <stdio.h> int yy[]={0, 1, 0, -1}, xx[] = {1, 0, -1, 0}; int T; char S[999999], A[999][999]; int main() { int i, j, k; for (i=0;i<999;i++) for (j=0;j<999;j++) A[i][j] = '#'; for (scanf("%d", &T), printf("%d\n", T);T--;){ scanf("%s", S); int y = 400, x = 400, dir = 0; int sy = y, sx = x, ey = y, ex = x; A[y][x] = '.'; for (i=0;S[i];i++){ if (S[i] == 'F'); else if (S[i] == 'B'){ dir = (dir+2)%4; }else if (S[i] == 'L'){ dir = (dir+3)%4; }else dir = (dir+1)%4; y += yy[dir]; x += xx[dir]; if (sy > y) sy = y; if (sx > x) sx = x; if (ey < y) ey = y; if (ex < x) ex = x; A[y][x] = '.'; } ex++; sy--; ey++; printf("%d %d\n", ey-sy+1, ex-sx+1); for (i=sy;i<=ey;i++, puts("")) for (j=sx;j<=ex;j++) printf("%c", A[i][j]), A[i][j] = '#'; } }

K. Key to Knowledge

OX 퀴즈에 $m$개의 문제가 있고, $n$명의 응시자가 제출한 답안과 맞은 문제 수가 주어졌을 때, 실제 시험에서 가능한 정답지의 가지수를 구하는 문제다.

$m \leq 30$으로 $m$ 제한이 큰 편이다. 정답지 후보의 개수는 $2^m$으로 상당히 크다. 이제 문제를 왼쪽과 오른쪽 두 부분으로 나눈다. 그러면 각 문제 집합 별로 가능한 정답지 후보의 개수는 많아야 $2^{15} = 32768$가지가 된다. 이제 반으로 나눈 정답지 후보 두 개를 적절히 합쳐 실제 가능한 정답지가 되는지 확인하면 된다.

#include <stdio.h> #include <map> using namespace std; typedef long long lld; int T, N, M, P, Q; int A[12][30], B[12]; int main() { int i, j, k; for (scanf("%d", &T);T--;){ scanf("%d%d", &N, &M); Q = (M>>1); P = M - Q; for (i=0;i<N;i++){ for (j=0;j<M;j++) scanf("%1d", A[i]+j); scanf("%d", B+i); } map <lld, int> cnt; map <lld, int> mymsk; for (int msk=0;msk<(1<<Q);msk++){ lld idx = 0; for (i=0;i<N;i++){ int c = 0; for (j=P;j<M;j++){ if (((msk>>(j-P))&1) == A[i][j]) c++; if (c > B[i]) break; } if (j < M) break; idx = idx * 31 + c; } if (i < N) continue; int c = ++cnt[idx]; if (c == 1) mymsk[idx] = msk; } int ans = 0, path = 0; for (int msk=0;msk<(1<<P);msk++){ lld idx = 0; for (i=0;i<N;i++){ int c = B[i]; for (j=0;j<P;j++){ if (((msk>>j)&1) == A[i][j]) c--; } if (c < 0) break; idx = idx * 31 + c; } if (i < N) continue; auto it = cnt.find(idx); if (it != cnt.end()){ ans += it->second; if (ans == 1){ int r = mymsk[idx]; path = msk | (r << P); } } } if (ans == 1){ for (i=0;i<M;i++) printf("%d", (path>>i)&1); puts(""); }else{ printf("%d solutions\n", ans); } } }