2013 Asia - Jakarta Regional Contest

온라인 아카이브 링크

A. Number Assignment

문제에서 주어진 수들을 정렬한 다음 Dynamic Programming를 이용해 해결한다.

D[i][j] = 1~i번 수가 있고, 이를 j개의 그룹으로 나눴을 때 가능한 최소 비용 합

점화시은 아래와 같다.

D[i][j] = min(D[k][j-1] + A[i] - A[k+1]) (for j-1 ≤ k < i)

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

#include <stdio.h> #include <algorithm> using namespace std; int T, N, M; int A[101], D[101][101]; 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++) scanf("%d", A+i); sort(A+1, A+N+1); for (i=1;i<=N;i++) D[i][1] = A[i]-A[1]; for (i=2;i<=M;i++){ for (j=i;j<=N;j++){ D[j][i] = 2e9; for (k=i-1;k<j;k++) if (D[j][i] > D[k][i-1]+A[j]-A[k+1]) D[j][i] = D[k][i-1]+A[j]-A[k+1]; } } printf("%d\n", D[N][M]); } }

B. Network Packet Ordering

가장 쉬운 방법으로는 $O(NM)$ Dynamic Programming을 생각할 수 있다. 하지만 이 방법은 제한 시간을 초과한다.

입력으로 두 종류 패킷이 들어온 시간이 들어오는데, 유의해야할 것은 패킷들이 들어오는 시간은 한 종류 안에서 서로 다르다. 그리고 문제 조건에서 $D \leq 100$으로 굉장히 작은 것을 알 수 있다. 따라서 기존 DP에서 $NM$개의 상태가 모두 필요하지 않음을 알 수 있다. 이를 이용해 상태의 개수를 줄이면 $O(D(N+M))$이 됨을 알 수 있다. 이 상태만을 이용하여 DP를 하면 된다.

#include <stdio.h> #define MAXN 50004 const int MOD = 1e9 + 9; int T, N, M, K; int A[MAXN], B[MAXN]; int D[MAXN][2][101], E[MAXN][2][101]; bool get_idx(int a, int b, int last, int &p, int &q) { if (last){ // b is last if (!(A[a] < B[b]+K && (a == N || B[b] < A[a+1]+K))) return 0; if (A[a] >= B[b]){ p = 0; q = A[a]-B[b]; } else{ p = 1; q = (a == N || A[a+1] >= B[b]) ? 0 : B[b]-A[a+1]; } } else{ if (!(B[b] < A[a]+K && (b == M || A[a] < B[b+1]+K))) return 0; if (B[b] >= A[a]){ p = 0; q = B[b]-A[a]; } else{ p = 1; q = (b == M || B[b+1] >= A[a]) ? 0 : A[a]-B[b+1]; } } return 1; } int dy2(int a, int b); int dy1(int a, int b) { int p, q; if (!a && !b) return 1; if (!a || !get_idx(a, b, 0, p, q)) return 0; int &ret = D[a][p][q]; if (ret >= 0) return ret; return ret = (dy1(a-1,b)+dy2(a-1,b))%MOD; } int dy2(int a, int b) { int p, q; if (!b || !get_idx(a, b, 1, p, q)) return 0; int &ret = E[b][p][q]; if (ret >= 0) return ret; return ret = (dy1(a,b-1)+dy2(a,b-1))%MOD; } int main() { int ts = 0, i, j, k; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d%d", &N, &M, &K); for (i=1;i<=N;i++) scanf("%d", A+i); for (i=1;i<=M;i++) scanf("%d", B+i); for (i=1;i<=N;i++) for (j=0;j<2;j++) for (k=0;k<101;k++) D[i][j][k] = -1; for (i=1;i<=M;i++) for (j=0;j<2;j++) for (k=0;k<101;k++) E[i][j][k] = -1; int ans = (dy1(N, M) + dy2(N, M))%MOD; printf("%d\n", ans); } }

C. The Busiest City

어떤 도시 $i$에서 바쁜 정도를 계산하기 위해서 도시 $i$를 루트로 한 rooted tree를 고려하면 된다. 그 때 $i$의 두 자식 노드들의 서브트리의 크기들의 곱의 합이 바쁜 정도가 된다. 이러기 위해서 자식 노드의 개수가 $C$개라 할 때, $O(C^2)$의 연산이 필요해보이지만 조금만 더 생각하면 이 계산을 $O(C)$만에 할 수 있다. 따라서, 전체 시간복잡도는 $O(N)$이 된다.

#include <stdio.h> #include <vector> using namespace std; #define MAXN 20005 #define pb push_back int T, N, ans; int S[MAXN]; vector <int> con[MAXN]; void dfs(int n, int from) { S[n] = 0; int b = 0, sum = 0; for (int t: con[n]){ if (t == from) continue; dfs(t, n); b += S[n] * S[t]; S[n] += S[t]; } b += S[n] * (N - S[n] - 1); ++S[n]; if (ans < b) ans = b; } int main() { int ts = 0, i, j, k; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d", &N); for (i=1;i<=N;i++) con[i].clear(); for (i=1;i<N;i++){ scanf("%d%d", &j, &k); con[j].pb(k); con[k].pb(j); } ans = 0; dfs(1, 0); printf("%d\n", ans); } }

D. Power Plant

그냥 Minimum Cost Spanning Tree를 구하는 Kruskal 알고리즘을 생각할 수 있다. 하지만 문제 조건에서 발전소가 같은 Spanning Tree 안에 있으면 안된다는 조건이 있다. 이 조건과 상관 없이 Kruskal 알고리즘을 하여도 상관 없을을 직관적으로 알 수 있다. 따라서 Kruskal 알고리즘의 union-find 도중 union 하려는 두 집단이 각각 발전소를 포함하고 있으면 union 연산을 생략한다.

#include <stdio.h> #include <algorithm> using namespace std; typedef long long lld; int T, N, M, K; int P[201], V[201]; struct Z{ int a, b, c; bool operator < (const Z &ot)const{ return c < ot.c; } } E[40001]; int find(int n){ return n==P[n]?n:(P[n]=find(P[n])); } int main() { int ts = 0, i, j, k; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d%d", &N, &M, &K); for (i=1;i<=N;i++) P[i] = i, V[i] = 0; for (i=1;i<=K;i++) scanf("%d", &k), V[k] = 1; for (i=1;i<=M;i++){ scanf("%d%d%d", &E[i].a, &E[i].b, &E[i].c); } sort(E+1, E+M+1); lld ans = 0; for (i=1;i<=M;i++){ const Z &e = E[i]; int a = find(e.a), b = find(e.b); if (a == b || V[a] && V[b]) continue; P[b] = a; V[a] |= V[b]; ans += e.c; } printf("%lld\n", ans); } }

F. Pasti Pas!

가장 긴 Palindrom을 만들기 위해서 어떤 문자열 $S$를 $\alpha\beta\alpha$로 나타낼 수 있을 때, 가능한 가장 짧은 길이의 $\alpha$를 찾고 $\beta$에 대해서 작업을 재귀적으로 이어나가면 된다. 가장 짧은 길이의 $\alpha$가 항상 좋다라는 증명은 생략한다.

이를 수행하기 위한 두 가지 방법이 있다. 하나는 Suffix Array와 LCP, RMQ(Range Minimum Query)를 이용한 $O(N \lg N)$ 방법이고, 하나는 해싱을 이용한 $O(N)$ 방법이다. 두 방법은 두 문자열이 같은지 비교를 빠르게 하기 위해 사용된다. 전자는 확실한 정답률을 보이지만 난이도가 높다는 단점이 있으며, 후자는 확실하게 답을 알려주는 보장은 없지만 코딩이 매우 간단하단 장점이 있다. 코드는 두 가지 방법 모두 소개하겠다. 해싱의 정확도를 높이기 위해 하나의 해시 함수보다 두 개의 해시 함수를 구현하여 두 값을 비교한다.

#include <stdio.h> #include <string.h> #include <vector> #include <algorithm> using namespace std; #define MAXN 50004 int T, N, M; int SA[MAXN], lcp[MAXN][16], R[MAXN]; char S[MAXN]; void SuffixArray() { int i, j, k; int m = 26; vector <int> cnt(max(N, m)+1, 0), x(N+1, 0), y(N+1, 0); for (i=1;i<=N;i++) cnt[x[i] = S[i]-'A'+1]++; for (i=1;i<=m;i++) cnt[i] += cnt[i-1]; for (i=N;i;i--) SA[cnt[x[i]]--] = i; for (int len=1, p=1;p<N;len<<=1, m=p){ for (p=0, i=N-len;++i<=N;) y[++p] = i; for (i=1;i<=N;i++) if (SA[i] > len) y[++p] = SA[i]-len; for (i=0;i<=m;i++) cnt[i] = 0; for (i=1;i<=N;i++) cnt[x[y[i]]]++; for (i=1;i<=m;i++) cnt[i] += cnt[i-1]; for (i=N;i;i--) SA[cnt[x[y[i]]]--] = y[i]; swap(x, y); p = 1; x[SA[1]] = 1; for (i=1;i<N;i++){ x[SA[i+1]] = SA[i]+len <= N && SA[i+1]+len <= N && y[SA[i]] == y[SA[i+1]] && y[SA[i]+len] == y[SA[i+1]+len] ? p : ++p; } } } void LCP() { int i, j, k=0; for (i=1;i<=N;i++) R[SA[i]] = i; for (i=1;i<=N;lcp[R[i++]][0]=k){ for (k?k--:0, j=SA[R[i]-1];S[i+k]==S[j+k];k++); } for (i=1;i<16;i++){ for (j=2;j<=N;j++){ lcp[j][i] = j<=(1<<i)?0:min(lcp[j-(1<<(i-1))][i-1],lcp[j][i-1]); } } } bool same(int a, int b, int len) { a = R[a], b = R[b]; if (a > b) swap(a, b); int ret = 2e9; for (int i=16;i--;) if (b-(1<<i) >= a) ret = min(ret, lcp[b][i]), b -= (1<<i); return ret >= len; } int main() { int ts = 0, i, j, k; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%s", S+1); N = strlen(S+1); M = N>>1; SuffixArray(); LCP(); int ans = 0; for (i=0, j=N;i<M;){ for (k=i+1;k<=M;k++){ if (same(i+1, j-(k-i)+1, k-i)) break; } if (k > M) break; j -= k-i; i = k; ans += 2; } if (i < M || (N&1)) ans++; printf("%d\n", ans); } }

#include <stdio.h> #include <string.h> #define MAXN 50004 typedef long long lld; const int MOD = 1e9 + 7; int T, N, P = 29, Q = 31; char S[MAXN]; int main() { int ts = 0, i, j, k; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%s", S+1); N = strlen(S+1); for (i=1;i<=N;i++) S[i] = S[i]-'A'+1; int p=0, q=0, x=0, y=0, a=1, b=1; int ans = 0; for (i=1, j=N;i<j;i++, j--){ p = (p+(lld)a*S[i])%MOD; q = (q+(lld)b*S[i])%MOD; x = ((lld)x*P+S[j])%MOD; y = ((lld)y*Q+S[j])%MOD; a = (lld)a*P%MOD; b = (lld)b*Q%MOD; if (p == x && q == y){ ans += 2; p = q = x = y = 0; a = b = 1; } } if (i == j || a > 1) ans++; printf("%d\n", ans); } }

G. Emergency Handling

가능한 $r$의 종류가 101가지 밖에 되지 않는다. 각 $r$ 값 마다 최대 힙(heap) 자료구조로 $t = 0$ 일 때 값을 저장해둔다. 그리고 A 종류 쿼리가 들어올 때 마다 101가지 $r$ 값에 대해서 $t = 0$ 일 때 값이 제일 큰 것을 가져와 주어진 $t$ 일 때 최대 값을 가져온다.

#include <stdio.h> #include <queue> using namespace std; int T, Q; priority_queue <int> que[101]; int main() { int ts = 0, i; for (scanf("%d", &T);T--;){ printf("Case #%d:\n", ++ts); for (i=101;i--;) que[i] = priority_queue<int>(); for (scanf("%d", &Q);Q--;){ char c; int t; scanf(" %c%d", &c, &t); if (c == 'P'){ int s, r; scanf("%d%d", &s, &r); s -= r*t; que[r].push(s); } else{ int mx = -1, r = -1; for (i=101;i--;) if (!que[i].empty()){ int s = que[i].top() + i*t; if (mx < s) mx = s, r = i; } printf("%d %d\n", mx, r); que[r].pop(); } } } }

H. Horrible Quiz

Dynamic Programming을 이용해 해결 가능하다.

D[i][j] = 1번부터 i번 문제까지 풀었고, 정답지를 볼 수 있는 기회가 j번 남았을 때 최소 기대값

E[i][j] = 1번부터 i번 문제까지 풀었고, 정답지를 볼 수 있는 기회가 j번 남았을 때 최대 기대값

으로 정의한다.

점화식은 간단하게 생각할 수 있다. 위와 같이 최소, 최대 두 가지 경우에 대해서 다이나믹 배열을 정의한 이유는 문제에서 요구하는 최소 값을 구하기 위해 최대 값이 필요한 경우가 있기 때문이다.

#include <stdio.h> int T, N, M; int C[1251], W[1251]; double D[1251][1251], E[1251][1251]; double dy2(int, int); double dy1(int n, int m) { if (n > N) return 15000; double &ret = D[n][m]; if (ret > -1e9) return ret; ret = (100-W[n] >= W[n] ? dy1(n+1, m) : dy2(n+1, m)) * ((100-W[n])/100. - W[n]/100.); if (!m) return ret; double v = (C[n] >= 100-C[n] ? dy1(n+1, m-1) : dy2(n+1, m-1)) * (C[n]/100. - (100-C[n])/100.); if (ret > v) ret = v; return ret; } double dy2(int n, int m) { if (n > N) return 15000; double &ret = E[n][m]; if (ret > -1e9) return ret; ret = (100-W[n] >= W[n] ? dy2(n+1, m) : dy1(n+1, m)) * ((100-W[n])/100. - W[n]/100.); if (!m) return ret; double v = (C[n] >= 100-C[n] ? dy2(n+1, m-1) : dy1(n+1, m-1)) * (C[n]/100. - (100-C[n])/100.); if (ret < v) ret = v; return ret; } 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++) scanf("%d", C+i); for (i=1;i<=N;i++) scanf("%d", W+i); for (i=1;i<=N;i++) for (j=0;j<=M;j++) D[i][j] = E[i][j] = -2e9; double ans = dy1(1, M); printf("%.3lf\n", ans); } }

I. Coins on a Ring

최종적으로 동전 사이의 거리는 $\frac{N}{M}$이다. 그리고 동전들의 상대적 위치는 처음 입력으로 주어지는 것과 다르지 않다. 이 점을 이용해 각 동전들의 Scale을 모두 갖게 만들자. 여러 가지 방법이 있겠지만 그 중 하나로는 동전들의 위치 $\{P_i\}$ 들을 정렬하고 $P'_i = (P_i - \frac{N}{M} \times i + N) \mod N$ 으로 치환하는 방법이 있다. 동전들의 Scale이 모두 같아졌으니 새로운 위치 $\{P'_i\}$에 대해 한 지점으로 동전들을 모으는 문제로 바뀐다.

#include <stdio.h> #include <algorithm> using namespace std; #define MAXM 20004 int T, N, M, A[MAXM]; int main() { int ts = 0, i, j; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d", &N, &M); for (i=1;i<=M;i++) scanf("%d", A+i); sort(A+1, A+M+1); for (i=1;i<=M;i++) A[i] = (A[i]-(N/M)*i+N)%N; sort(A+1, A+M+1); int ans = A[M]-A[1]; for (i=1;i<M;i++) ans = min(ans, A[i]+N-A[i+1]); printf("%d\n", (ans+1)>>1); } }

J. Alien Abduction Again

전형적인 Segment Tree를 이용하는 문제다. $x^3$항, $x^2$항, $x$항과 상수항에 있는 계수를 독립적이게 생각할 수 있으므로 Segment Tree의 각 노드 안에 4개의 값이 있다고 보면 된다. 나머지 연산에 유의하자.

#include <stdio.h> #include <algorithm> using namespace std; typedef long long lld; const int MOD = 1e9 + 7; int T, Q, K, N = 1000000; int S[4][1000001]; struct NODE{ int a, b, c, d, sum, me; NODE *left, *right; } container[6000000], *root; NODE *new_node(){ NODE *ret = &container[K++]; ret->a = ret->b = ret->c = ret->d = ret->sum = ret->me = 0; ret->left = ret->right = 0; return ret; } inline int VALUE(int a, int b, int c, int d, int s, int e){ int cs[4] ={d, c, b, a}, i, ret = 0; for (i=0;i<4;i++){ int v = (S[i][e]-S[i][s-1]+MOD)%MOD; ret = (ret+(lld)v*cs[i])%MOD; } return ret; } inline void add(int &t, int v) { t += v; if (t < 0) t += MOD; if (t >= MOD) t -= MOD; } void add(NODE *now, int s, int e, int l, int r, int a, int b, int c, int d) { if (e < l || s > r) return; if (l <= s && e <= r){ int v = VALUE(a, b, c, d, s, e); add(now->a, a); add(now->b, b); add(now->c, c); add(now->d, d); now->sum = (now->sum+v)%MOD; now->me = (now->me+v)%MOD; return; } if (!now->left) now->left = new_node(), now->right = new_node(); int m = (s+e)>>1; add(now->left, s, m, l, r, a, b, c, d); add(now->right, m+1, e, l, r, a, b, c, d); now->sum = ((now->me+now->left->sum)%MOD+now->right->sum)%MOD; } int get(NODE *now, int s, int e, int l, int r, int a, int b, int c, int d) { if (e < l || s > r) return 0; if (l <= s && e <= r){ int v = VALUE(a, b, c, d, s, e); return (v+now->sum)%MOD; } if (!now->left) now->left = new_node(), now->right = new_node(); int m = (s+e)>>1; add(a, now->a); add(b, now->b); add(c, now->c); add(d, now->d); return (get(now->left, s, m, l, r, a, b, c, d)+get(now->right, m+1, e, l, r, a, b, c, d))%MOD; } int main() { int ts = 0, i, j, k; for (i=1;i<1000001;i++){ k = 1; for (j=0;j<4;j++){ S[j][i] = (S[j][i-1]+k)%MOD; k = (lld)k*(i-1)%MOD; } } for (scanf("%d", &T);T--;){ printf("Case #%d:\n", ++ts); K = 0; root = new_node(); for (scanf("%d", &Q);Q--;){ char ch; int x1, x2, a, b, c, d; scanf(" %c%d%d%d%d%d%d", &ch, &x1, &x2, &a, &b, &c, &d); a = (a%MOD+MOD)%MOD; b = (b%MOD+MOD)%MOD; c = (c%MOD+MOD)%MOD; d = (d%MOD+MOD)%MOD; x1++; x2++; if (ch == 'p'){ add(root, 1, N, x1, x2, a, b, c, d); } else{ int e = get(root, 1, N, x1, x2, 0, 0, 0, 0); printf("%d\n", e); x1 = (lld)e*(x1-1)%N+1; x2 = (lld)e*(x2-1)%N+1; if (x1 > x2) swap(x1, x2); add(root, 1, N, x1, x2, a, b, c, d); } } } }