2014 Asia - Jakarta Regional Contest

문제 링크

A. Cluster Analysis

$N$개의 수가 주어진다. 두 수의 차이가 $K$ 이하면 두 수가 같은 cluster 안에 포함된다. 이 때 생기는 cluster의 개수를 구하는 문제다.

$N \leq 100$으로 제한이 굉장히 작다. 따라서 $O(N^2)$ 안에 그래프의 간선을 그릴 수 있고, union-find나 flood-fill을 통하여 cluster의 개수를 세면 된다.

#include <stdio.h> #include <stdlib.h> int T, N, K; int A[101], par[101]; int find(int n){ return par[n]==n ? n : (par[n] = find(par[n])); } int main() { int ts = 0, i, j; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d", &N, &K); for (i=1;i<=N;i++) scanf("%d", A+i), par[i] = i; for (i=1;i<N;i++) for (j=i+1;j<=N;j++) if (abs(A[i]-A[j]) <= K){ int a = find(i), b = find(j); if (a != b) par[b] = a; } int ans = 0; for (i=1;i<=N;i++) if (find(i) == i) ans++; printf("%d\n", ans); } }

B. Body Building

$N$개의 정점과 $M$개의 간선으로 이루어진 무방향성 그래프가 주어진다. 이 그래프에서 하나의 연결 요소를 덤벨로 구분할 수 있다. 덤벨이란, 하나의 손잡이 간선과 간선 양 쪽에 같은 수의 정점으로 구성된 완전 그래프가 있어야한다. 덤벨로 구분할 수 있는 연결 요소의 개수를 구하는 문제다.

편의상 입력으로 주어지는 그래프를 연결 그래프라고 하자. 우선 정점의 수 $N$은 짝수여야한다. $N = 2K$라고 할 때, $N-2$개의 정점의 차수는 $K-1$이어야 하고, 두 정점의 차수는 $K$이어야한다. 이를 통하여 손잡이 간선에 포함된 두 정점을 구할 수 있다. 이를 통해 그래프가 덤벨 모양인지 쉽게 확인할 수 있다.

#include <stdio.h> #include <vector> using namespace std; #define sz(v) ((int)(v).size()) int T, N, M; int w[101][101], deg[101]; bool V[101]; vector <int> list; void dfs(int n) { if (V[n]) return; V[n] = 1; list.push_back(n); for (int i=1;i<=N;i++) if (w[n][i] && !V[i]) dfs(i); } int main() { int ts = 0, i, j, k; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d", &N, &M); for (i=1;i<=N;i++) V[i] = deg[i] = 0; for (i=1;i<=N;i++) for (j=1;j<=N;j++) w[i][j] = 0; for (i=1;i<=M;i++) scanf("%d%d", &j, &k), w[j][k] = w[k][j] = 1, deg[j]++, deg[k]++; int ans = 0; for (i=1;i<=N;i++) if (!V[i]){ list.clear(); dfs(i); int n = sz(list); if (n&1) continue; int cnt = 0, a = 0, b = 0, m = (n >> 1); for (int t: list){ if (deg[t] == m){ cnt++; b = a, a = t; }else if (deg[t] != m-1) cnt = 3; } if (cnt != 2) continue; w[a][b] = 0; for (int t: list) V[t] = 0; list.clear(); dfs(a); if (sz(list) != m){ dfs(b); continue; } list.clear(); dfs(b); if (sz(list) != m) continue; ans++; } printf("%d\n", ans); } }

C. Electric Bike

$N$개의 구간으로 이루어진 자전거 코스가 있다. 전기 자전거를 통해 이 구간 차례대로 모두 지나야한다. 전기 자전거의 동력에 따라 쓰이는 연료량과 얻는 힘이 다르다. $E$ 만큼의 연료가 있고 자전거 동력을 $K$번 바꿀 수 있을 때, $N$개의 구간을 지나기 위한 최소 추가 힘을 구하는 문제다.

D[i][j][k][l] = i번 구간까지 지났고 마지막 동력이 j이고 동력을 k번 바꿨고 사용한 총 연료량이 l일 때, 최소 추가 힘

위와 같이 DP 배열을 잡고 해결하면 된다. 시간복잡도는 $O(NKE)$이다.

#include <stdio.h> #include <algorithm> using namespace std; int T, N, K, E; int A[1001], B[4] = {0, 4, 8, 11}, D[1001][4][11][51]; int main() { int ts = 0, i, j, k, l; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d%d", &N, &K, &E); for (i=1;i<=N;i++) scanf("%d", A+i); for (i=0;i<=N;i++) for (j=0;j<4;j++) for (k=0;k<=K;k++) for (l=0;l<=E;l++) D[i][j][k][l] = 2e9; D[0][0][0][0] = 0; for (i=0;i<N;i++) for (j=0;j<4;j++) for (k=0;k<=K;k++) for (l=0;l<=E;l++) if (D[i][j][k][l] < 2e9){ for (int t=0;t<4;t++){ int nk = k+(j!=t), nl = l+t; if (nk > K || nl > E) continue; if (D[i+1][t][nk][nl] > D[i][j][k][l]+max(0, A[i+1]-B[t])) D[i+1][t][nk][nl] = D[i][j][k][l]+max(0, A[i+1]-B[t]); } } int ans = 2e9; for (i=0;i<4;i++) for (j=0;j<=K;j++) for (k=0;k<=E;k++) if (ans > D[N][i][j][k]) ans = D[N][i][j][k]; printf("%d\n", ans); } }

D. Kevin's Problem

1부터 $N$까지의 수 $N$개로 이루어진 순열들이 있다. 하나의 순열이 있을 때, 특정 규칙을 통해 수 하나를 선택한다. 이 때 수 $P$가 선택되는 순열의 개수를 구하는 문제다.

D[i][j] = 수열의 마지막 수가 i고, 길이가 j인 증가 수열의 개수 (단, 수열에 $P$는 들어가지 않는다)

위와 같이 DP 배열을 정의하여 문제를 해결할 수 있다.

기본적인 아이디어는 수 $P$가 들어갈 위치를 정하고, $P$ 바로 앞에 오는 수를 정했을 때 경우의 수를 계산하면 된다.

아래와 같이 예외로 생각해주어야하는 경우가 존재한다.

1. $P = N$ 인 경우
2. $K = N-1$ 인 경우
3. $P$가 순열의 마지막에 있는 경우

시간복잡도는 $O(N^2)$이다.

#include <stdio.h> typedef long long lld; const int MOD = 1e9 + 7; int T, N, K, P; int D[501][501], F[501]; inline void add(int &t, int v){ t = (t+v)%MOD; } int main() { int ts = 0, i, j; F[0] = 1; for (i=1;i<501;i++) F[i] = (lld)F[i-1] * i % MOD; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d%d", &N, &K, &P); D[0][0] = 1; for (j=1;j<N;j++){ int sum = 0; for (i=1;i<=N;i++){ add(sum, D[i-1][j-1]); D[i][j] = i == P ? 0 : sum; } } int ans = 0; if (P == N){ for (i=1;i<N;i++) add(ans, (lld)D[i][N-K] * F[K-1] % MOD); }else if (K == N-1){ ans = F[K]; }else{ for (i=K+1;i<=N;i++){ for (j=P+1;j<=N;j++){ add(ans, (lld)D[j][i-K] * F[N-(i-K+1)] % MOD); } } for (i=1;i<P;i++){ add(ans, (lld)D[i][N-K] * F[K-1] % MOD); } } printf("%d\n", ans); } }

E. Cutting Tree

포레스트(1개 이상의 트리들로 이루어진 그래프)가 주어진다. 그리고 특정 간선을 지우는 질의와 두 정점이 연결되어 있는지 묻는 질의가 주어진다. 질의를 입력으로 주어진 순서대로 처리하는 문제다.

질의가 주어진 역순으로 문제를 뒤집으면, 질의는 간선을 지우는 것이 아니라 간선이 추가되는 질의로 바뀌게 된다. 이제 union-find를 통해 두 정점이 연결되어 있는지 확인할 수 있다.

#include <stdio.h> #include <vector> using namespace std; #define MAXN 20004 #define MAXM 5003 int T, N, M; int par[MAXN], P[MAXN], X[MAXN], ord[MAXN]; struct Z{ char c; int a, b; } Q[MAXM]; bool cmp(const int &a, const int &b){ return X[a] > X[b]; } int find(int n){ return par[n] == n ? n : (par[n] = find(par[n])); } inline void con(int a, int b) { if (!a || !b) return; a = find(a), b = find(b); if (a == b) return; par[b] = a; } int main() { int ts = 0, i, j, k; for (scanf("%d", &T);T--;){ printf("Case #%d:\n", ++ts); scanf("%d%d", &N, &M); for (i=1;i<=N;i++) scanf("%d", P+i), X[i] = 2e9, ord[i] = par[i] = i; for (i=1;i<=M;i++){ scanf(" %c%d", &Q[i].c, &Q[i].a); if (Q[i].c == 'Q') scanf("%d", &Q[i].b); else if (X[Q[i].a] > i) X[Q[i].a] = i; } sort(ord+1, ord+N+1, cmp); vector <int> ans; for (i=M,j=1;i;i--){ while (j <= N && X[ord[j]] >= i){ con(P[ord[j]], ord[j]); j++; } if (Q[i].c != 'Q') continue; ans.push_back(find(Q[i].a) == find(Q[i].b)); } for (i=(int)ans.size();i--;) puts(ans[i] ? "YES" : "NO"); } }

F. Double Swords

$N$ 마리의 용이 있다. 용을 잡으려면 양손에 검을 하나씩 총 두 개의 검이 필요하다. 용 별로 필요한 검 하나는 크기가 정해지고, 나머지 검 하나는 특정 범위를 만족하면 된다. 이 때 모든 용을 잡기 위해 필요한 검의 최소 개수를 구하는 문제다.

편의상 왼손에 쥘 검을 크기가 정해진 검, 오른손에 쥘 검이 범위로 주어진 검이라 하자. 왼손으로 쥘 검의 크기들의 검은 반드시 필요한 검의 크기들이다. 이제 문제는 최소 개수의 검으로 오른손에 쥘 검들을 만들면 된다. 이는 여러 개의 구간들이 있고 모든 구간을 찍기 위해 필요한 점의 최소 개수와 같다. 이는 욕심쟁이기법으로 쉽게 구할 수 있다.

#include <stdio.h> #include <set> #include <algorithm> using namespace std; #define MAXN 100005 int T, N, M; int A[MAXN], B[MAXN], C[MAXN]; struct Z{ int s, e; bool operator < (const Z &ot)const{ return s < ot.s; } } V[MAXN]; int main() { int ts = 0, i; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d", &N); set <int> S; for (i=1;i<=N;i++) scanf("%d%d%d", A+i, B+i, C+i), S.insert(A[i]); M = 0; for (i=1;i<=N;i++){ auto it = S.lower_bound(B[i]); if (it != S.end()){ if (*it == A[i]){ ++it; if (it != S.end() && *it <= C[i]) continue; } else if (*it <= C[i]) continue; } V[++M].s = B[i], V[M].e = C[i]; } sort(V+1, V+M+1); int mn = 2e9, ans = 0; for (i=1;i<=M;i++){ if (mn < V[i].s){ mn = 2e9; ans++; } if (mn > V[i].e) mn = V[i].e; } if (mn < 2e9) ans++; printf("%d\n", ans+(int)S.size()); } }

G. Prime Switch

$N$개의 전구가 있고, $K$개의 스위치가 있다. 전구는 1번부터 $N$번까지 번호가 매겨져 있다. 스위치에도 번호가 적혀있다. 이 번호들은 서로 다르며 소수(prime number)이다. 이 스위치를 누르면 스위치 번호의 배수가 적힌 전구들의 상태가 뒤집힌다. 이 때, 스위치를 적절히 눌러 켜져있는 전구의 개수를 최대화 하는 문제다.

$\sqrt{N}$보다 같거나 작은 번호를 가진 스위치는 많아야 11개다. 이 들에 대해 $2^{11}$가지의 경우에 대해 모두 처리하고 각 경우마다 $\sqrt{N}$보다 번호가 큰 스위치들에 대해서는 서로 독립이므로 욕심쟁이기법을 통해 전구의 개수를 최대화 할 수 있다.

#include <stdio.h> #include <algorithm> using namespace std; #define MAXN 1004 #define bit(n) (1<<((n)-1)) int T, N, M, K, R; int A[MAXN]; bool V[MAXN]; int main() { int ts = 0, i, j; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d", &N, &K); for (i=1;i<=K;i++) scanf("%d", A+i); sort(A+1, A+K+1); for (R=1;R*R<=N;R++); R--; for (i=1;i<=K;i++) if (A[i] <= R) M = i; int ans = 0; for (int msk=0;msk<(1<<M);msk++){ for (i=1;i<=N;i++) V[i] = 0; for (i=1;i<=M;i++) if (msk&bit(i)){ for (j=A[i];j<=N;j+=A[i]) V[j] ^= 1; } for (i=M+1;i<=K;i++){ int cnt = 0; for (j=A[i];j<=N;j+=A[i]){ if (V[j]) cnt--; else cnt++; } if (cnt > 0){ for (j=A[i];j<=N;j+=A[i]) V[j] ^= 1; } } int cnt = 0; for (i=1;i<=N;i++) if (V[i]) cnt++; if (ans < cnt) ans = cnt; } printf("%d\n", ans); } }

H. I Want That Cake

A팀과 B팀에 각각 $N$명씩 사람이 있다. $M$개의 팬케잌이 있고, 한 사람이 한 개에서 $K$개의 팬케잌을 먹을 수 있다. 마지막 펜케잌을 먹는 사람이 속한 팀이 이기는 게임을 한다. 다만 두 팀이 번갈아가면서 진행하지 않고 미리 순서를 정해둔다. 두 팀에 속한 각 선수들이 최선을 다할 때 어느 팀이 이기는지 구하는 문제다.

D[i][j] = i번째 사람의 차례고, 남은 팬케잌의 개수가 j일 때 i번째 사람이 이기면 1, 지면 0

위와 같이 DP 배열을 정의한다.

i번째 사람과 i+1번째 사람이 같은 팀에 속한 경우와 그렇지 않은 경우에 따라 점화식이 달라지게 된다.

쉽게 생각하면 $O(NMK)$의 시간복잡도를 보이는데, 점화식의 특성을 잘 이용하면 $O(NM)$에 해결할 수 있다.

#include <stdio.h> #define MAXN 2004 int T, N, M, K, L; int D[MAXN][MAXN]; char S[MAXN]; int main() { int ts = 0, i, j; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d%d%s", &N, &M, &K, S+1); L = (N << 1); for (i=1;i<=L;i++){ D[i][0] = 0; for (j=1;j<=M;j++) D[i][j] = j <= K ? 1 : -1; } for (i=L;--i;){ int p = 0, q = 0, zero = 0, one = 0; for (j=K+1;j<=M-i+1;j++){ while (q <= j-1){ if (D[i+1][q]) one++; else zero++; q++; } while (p < j-K){ if (D[i+1][p]) one--; else zero--; p++; } D[i][j] = 0; if (S[i] == S[i+1]){ if (one) D[i][j] = 1; }else{ if (zero) D[i][j] = 1; } } } printf("%c\n", D[1][M] ? S[1] : ('A'+'B'-S[1])); } }

I. Maze Mayhem

$N \times M$ 크기의 미로가 있다. 이 미로에서는 오른쪽과 아래 방향으로만 이동할 수 있다. 미로의 시작점은 왼쪽-위 점이고, 도착점은 오른쪽-아래 점이다. 이제 $K$개 이하의 장애물을 설치해서 시작점에서 도착점으로 가지 못하게 해야 한다. 가능한 경우의 수를 구하는 문제다.

D[i][j][k][l] = i번 이동했고, 도달가능한 상황이 j이고, 설치한 장애물의 개수가 k이고, l번까지 장애물을 설치했을 때 경우의 수

위와 같이 DP 배열을 정의한다.

도달 가능한 상황이라 함은 i번 이동했을 때 도달 가능한 위치가 최대 $N$가지이다. 그러므로 가능한 상황의 수는 $2^N$가지이므로 길이가 $N$인 이진수로 나타낼 수 있다.

장애물을 l번 줄까지 놓았다는 것은 가능한 $N$개의 상황 중 l번까지 장애물을 설치했음을 의미한다. 중복으로 경우를 세는 경우에 대비하기 위해 필요하다.

#include <stdio.h> #define bit(n) (1<<(n)) const int MOD = 1e9 + 7; int T, N, M, K; int D[16][1<<8][65][9]; inline void add(int &t, int v){ t = (t+v)%MOD; } int main() { int ts = 0, i, j, k, l; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d%d", &N, &M, &K); for (i=0;i<N+M-1;i++) for (j=0;j<bit(N);j++) for (k=0;k<=K;k++) for (l=0;l<=N;l++) D[i][j][k][l] = 0; D[0][1][0][0] = 1; for (i=0;i<N+M-1;i++) for (l=0;l<=N;l++) for (j=0;j<bit(N);j++) for (k=0;k<=K;k++) if (D[i][j][k][l]){ if (k < K && l < N && i-l >= 0 && i-l < M){ int t = j & bit(l) ? j ^ bit(l) : j; add(D[i][t][k+1][l+1] , D[i][j][k][l]); } if (l < N) add(D[i][j][k][l+1], D[i][j][k][l]); if (i == N+M-2 || l < N) continue; int nxt = 0; for (int y=0;y<N;y++) if (j & bit(y)){ int x = i-y; if (x+1 < M) nxt |= bit(y); if (y+1 < N) nxt |= bit(y+1); } add(D[i+1][nxt][k][0], D[i][j][k][l]); } int ans = 0; for (k=0;k<=K;k++) add(ans, D[N+M-2][0][k][N]); printf("%d\n", ans); } }

J. Leveling Ground

길이가 $N$인 산 모양이 주어진다. 길이가 $M$인 구간을 공사해야한다. 공사는 구간에 속한 가장 낮은 높이에 맞춰 구간안에 있는 모든 땅을 판다. 이 때 비용은 파는 땅의 단면의 면적과 같다. 문제에 있는 그림에서 점('.') 하나는 비용이 1이며, 경사 ('/')는 비용이 0.5다. 이 때 공사 가능한 여러 구간들 중 최소 비용으로 공사할 수 있는 구간의 비용을 구하는 문제다.

길이가 $M$인 각 구간에 대해서 구간 내의 높이(점의 개수)의 합과 경사의 개수, 그리고 최소 높이를 알면 그 구간에 대한 공사 비용을 구할 수 있다. 이는 deque(Double-Ended Queue)와 같은 자료구조를 통해 구현할 수 있다.

#include <stdio.h> #include <deque> using namespace std; #define MAXN 1000006 typedef long long lld; int T, N, M; int H[MAXN]; char A[MAXN]; int main() { int ts = 0, i, j; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d%s", &N, &M, A+1); int h = 0; for (i=1;i<=N;i++){ if (A[i] == '/') H[i] = h++; else if (A[i] == '_') H[i] = h; else H[i] = --h; } lld sum = 0; int slope = 0; deque <int> dq; lld ans = 1e18; for (i=j=1;i<=N;i++){ while (j <= i-M){ sum -= H[j]; if (A[j] != '_') slope--; j++; } sum += H[i]; if (A[i] != '_') slope++; while (!dq.empty() && H[dq.back()] >= H[i]) dq.pop_back(); dq.push_back(i); while (dq.front() <= i-M) dq.pop_front(); if (i < M) continue; lld p = sum - (lld)H[dq.front()] * M, v = p + p + slope; if (ans > v) ans = v; } printf("%lld.%d\n", ans>>1, (int)(ans&1)*5); } }

K. Punching Robot

$N \times M$ 크기의 미로가 있다. 이 미로에서는 오른쪽과 아래 방향으로만 이동할 수 있다. 미로의 시작점은 왼쪽-위 점이고, 도착점은 오른쪽-아래 점이다. 미로 위에 $K$개의 장애물이 있는데 장애물들은 $1 \times 1$ 크기가 아닌 $3 \times 3$ 크기다. 장애물을 지나지 않고 시작점에서 도착점으로 가는 경로의 개수를 구하는 문제다.

$3 \times 3$ 크기의 장애물 하나를 $1 \times 1$ 크기의 장애물 9개로 바꾸고 문제를 생각한다. 그러면 총 90개의 장애물이 있을 수 있다. 이제 DP 배열을 아래와 같이 정의한다.

D[i] = 시작점에서 출발하여 장애물 i까지 장애물을 하나도 거치지 않고 가는 경우의 수

자세한 점화식은 생략한다.

문제에서 제일 중요한 것은 ${n}\choose{k}$를 $\mod 997$안에서 빠르게 구해야한다. 이는 뤼카의 정리를 이용하여 $\log {n+k}$ 시간안에 구할 수 있다. 일반적으로 생각할 수 있는 방법으로 구하면 $997!$이 997의 배수가 되어버려서 Modulo Inverse를 제대로 구할 수 없다.

#include <stdio.h> #include <vector> #include <algorithm> using namespace std; #define all(v) (v).begin(), (v).end() const int MOD = 997; int T, N, M, K; int C[MOD][MOD], D[99]; struct Z{ Z(int y=0, int x=0): y(y), x(x) {} int y, x; bool operator < (const Z &ot)const{ return y != ot.y ? y < ot.y : x < ot.x; } bool operator == (const Z &ot)const{ return y == ot.y && x == ot.x; } }; int choose(int n, int k) { int ret = 1; for (;n;n/=MOD, k/=MOD){ int p = n % MOD, q = k % MOD; ret = ret * C[p][q] % MOD; } return ret; } inline int count(int y, int x){ return choose(y+x, x); } int main() { int ts = 0, i, j, k; C[0][0] = 1; for (i=1;i<MOD;i++){ C[i][0] = 1; for (j=1;j<=i;j++) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD; } for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d%d", &N, &M, &K); vector <Z> A; for (i=1;i<=K;i++){ scanf("%d%d", &j, &k); for (int y=j-1;y<j+2;y++) for (int x=k-1;x<k+2;x++) A.emplace_back(y, x); } A.emplace_back(N, M); sort(all(A)); A.erase(unique(all(A)), A.end()); K = (int)A.size(); for (i=0;i<K;i++){ D[i] = count(A[i].y-1, A[i].x-1); for (j=0;j<i;j++) if (A[j].x <= A[i].x){ D[i] -= D[j] * count(A[i].y-A[j].y, A[i].x-A[j].x) % MOD; if (D[i] < 0) D[i] += MOD; } } printf("%d\n", D[K-1]); } }