2014 Asia - Kuala Lumpur Regional Contest

온라인 아카이브 링크

A. The Mountain of Gold?

0번 도시에서 시작하고 시공간을 이동할 수 있는 수단들이 주어졌을 때, 0번 도시의 과거로 돌아올 수 있는지 판별하는 문제다.

일반적으로 $O(NM)$ 시간복잡도의 Bellman-ford 알고리즘은 전체 그래프에서 음수 싸이클이 있는지 판별할 때 쓰인다. 이 문제에서는 0번 도시와 강하게 연결된 연결 요소(0번 도시에서 $x$로 갈 수 있고, $x$에서 0번 도시로 올 수도 있는 $x$들의 집합)에서 음수 싸이클이 있는지 Bellman-ford로 $O(NM)$만에 확인해주면 된다.

#include <stdio.h> #include <queue> #include <vector> using namespace std; typedef vector<int> arr; int T, N, M; int D[1001]; bool V[1001], U[1001]; vector <arr> con, conr; struct { int s, e, c; } edge[2001]; void bfs(bool *vis, vector <arr> &cond) { queue <int> que; que.push(1); vis[1] = 1; while (!que.empty()){ int q = que.front(); que.pop(); for (int t: cond[q]){ if (!vis[t]) vis[t] = 1, que.push(t); } } } int main() { int ts = 0, i, j; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d", &N, &M); con.clear(), conr.clear(); con.resize(N+1, arr()); conr.resize(N+1, arr()); for (i=1;i<=M;i++){ scanf("%d%d%d", &edge[i].s, &edge[i].e, &edge[i].c); edge[i].s++; edge[i].e++; con[edge[i].s].push_back(edge[i].e); conr[edge[i].e].push_back(edge[i].s); } for (i=1;i<=N;i++) V[i] = 0, U[i] = 0; bfs(V, con); bfs(U, conr); for (i=1;i<=N;i++) V[i] &= U[i], D[i] = 2e9; D[1] = 0; for (i=1;i<=N;i++){ bool sw = 0; for (j=1;j<=M;j++) if (V[edge[j].s] && V[edge[j].e]){ if (D[edge[j].e] > D[edge[j].s]+edge[j].c) D[edge[j].e] = D[edge[j].s]+edge[j].c, sw = 1; } if (!sw) break; } puts(i > N ? "possible" : "not possible"); } }

B. Sequence

이진수열이 주어지고 하나의 비트를 뒤집을 수 있는 연산을 $K$번 할 수 있을 때, 모두 0으로 만드는 경우의 수를 구하는 문제다.

Dynamic Programming으로 해결할 수 있다.

아래와 같이 다이나믹 배열을 정의하자.

D[i][j] = i번의 연산이 남았고 1의 개수가 j개 일 때, 모두 0으로 만드는 경우의 수

점화식은 아래와 같다.

D[i][j] = j * D[i-1][j-1] + (N-j) * D[i-1][j+1]

시간복잡도는 $O(NK)$ 다.

#include <stdio.h> typedef long long lld; const int MOD = 1e9 + 7; int T, N, K, B; int A[1001], D[1001][1001]; int dy(int one, int turn) { if (one > N || one < 0) return 0; int &ret = D[one][turn]; if (ret >= 0) return ret; if (!turn) return ret = !one; return ret = ((lld)one * dy(one-1, turn-1) + (lld)(N-one) * dy(one+1, turn-1))%MOD; } int main() { int ts = 0, i, j, k; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d", &N, &K); B = 0; for (i=1;i<=N;i++) scanf("%d", A+i), B += A[i]; if (B > K || ((B^K)&1)){ puts("0"); continue; } for (i=0;i<=N;i++) for (j=0;j<=K;j++) D[i][j] = -1; printf("%d\n", dy(B, K)); } }

C. Turtle Graphics

거북이의 시작 위치와 이동 명령이 주어졌을 때, 거북이의 최종 좌표와 두 번 이상 방문한 점의 개수를 세는 문제다.

문제에서 하라는대로 하면 된다.

#include <stdio.h> #include <memory.h> int yy[]={1, 0, -1, 0}, xx[]={0, 1, 0, -1}; int T, X, Y; int A[64][64]; char S[200]; int main() { int ts = 0, i; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d", &X, &Y); memset(A, 0, sizeof(A)); int dir = 0, ans = 0; scanf("%s", S); A[Y][X]++; for (i=0;S[i];i++){ if (S[i] == 'F'){ Y += yy[dir], X += xx[dir]; if (++A[Y][X] == 2) ans++; } else if (S[i] == 'L') dir = (dir+3)%4; else dir = (dir+1)%4; } printf("%d %d %d\n", X, Y, ans); } }

D. Circle and Marble

트리가 주어지고, 각 노드마다 구슬이 여러 개 있을 수 있다. 두 명이서 게임을 하는데, 각 차례마다 구슬 하나를 선택해 구슬이 있는 노드의 자식 노드로 움직일 수 있다. 만약 자기 차례에 더 이상 움직일 수 있는 구슬이 하나도 없는 경우 진다. 두 명 모두 최적의 전략으로 게임에 임할 때, 누가 이기는지 구하는 문제다.

주어진 트리에서 노드 별로 Grundy Number를 구한다. 각 구슬마다 자신이 있는 노드의 Grundy Number를 XOR 했을 때 결과가 0이면 처음 시작하는 사람이 지고, 0이 아니면 처음 시작하는 사람이 이긴다. 각 노드에 있는 구슬의 개수가 많지만, 구슬 개수의 홀짝성을 이용하면 쉬워진다.

문제에서 가능한 Grundy Number는 최대 14다. 트리 구성에서 노드의 Grundy Number가 $g$이기 위해서 그 노드의 서브 트리에 있는 노드 개수가 최소 $2^g$개 필요하기 때문이다.

#include <stdio.h> #include <vector> using namespace std; #define MAXN 20004 int T, N; int P[MAXN], A[MAXN], G[MAXN]; vector <int> con[MAXN]; void dfs(int n) { vector <bool> vis(15, 0); for (int t: con[n]){ dfs(t); vis[G[t]] = 1; } for (G[n]=0;vis[G[n]];G[n]++); } int main() { int ts = 0, i, j; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d", &N); for (i=1;i<=N;i++) scanf("%d", A+i), con[i].clear(), A[i] &= 1; for (i=1;i<=N;i++) scanf("%d", P+i), con[P[i]].push_back(i); dfs(1); int x = 0; for (i=1;i<=N;i++) x ^= A[i]*G[i]; puts(x ? "first" : "second"); } }

E. Group of Strangers

정점이 $N$개고 간선이 $M$개인 무방향성 그래프가 주어진다. 이 그래프에서 정점 3개를 선택하는데 선택 된 저점들이 서로 연결이 되어 있지 않은 것의 개수를 세는 문제다.

처음으로 $O(NM)$ 방법을 생각할 수 있다. 문제 데이터는 $O(NM)$ 방법보다 빠른 방법을 요구한다. 우선, 문제를 역으로 생각해서 간선이 적어도 하나라도 연결되어 있는 세 정점을 찾는 것으로 바꾼다. 그리고 차례대로 3개의 간선으로 연결되어 있는 세 정점 개수, 간선 2개로 연결되어 있는 세 정점 개수, 간선 1개로 연결되어 있는 세 정점 개수를 센다.

간선 3개로 연결되어 있는 세 정점의 개수는 그래프에서 그려지는 삼각형의 개수와 같다. 이 개수를 $O(M^{1.5})$으로 구할 수 있다.

우선 $N \leq 5000$이므로 임의의 두 점 사이에 간선이 연결되어 있는지 배열을 이용하여 $O(1)$만에 구할 수 있다. 차수가 $\sqrt{M}$ 이상인 정점들을 무거운 정점이라 하자. 무거운 정점의 개수는 $\sqrt{M}$ 이하다. 무거운 정점 3개로 이루어진 삼각형은 $(\sqrt{M})^3 = O(M^{1.5})$으로 해결 가능하다. 마찬가지로 무거운 간선을 정의할 수 있는데, 무거운 정점 두 개를 연결하는 간선을 무거운 간선이라 부르자.

무거운 간선이 아닌 간선이 연결하는 두 정점 $a$, $b$ 중 차수가 작은 정점을 $a$라 하자. 정의에 따라 $a$는 무거운 정점이 아니다. 때문에 $a$의 차수는 $\sqrt{M}$ 이하다. 이제 이 간선과 $a$에 연결된 다른 간선들을 모두 묶어보고 삼각형이 되는지 확인하면 된다. 이 시간복잡도도 $M \times \sqrt{M} = O(M^{1.5})$가 된다.

이제 간선 2개로 연결되어 있는 세 정점의 개수는 $O(N)$ 만에 구할 수 있다. 차수가 $d$인 정점 $i$를 포함한 간선 2개로 이루어질 수 있는 세 점의 개수는 ${d}\choose{2}$가 된다. 이를 다 더한다. 이 중에 삼각형이 있을 수 있는데, 더한 값을 삼각형 개수에 비례하게 뺀다.

마찬가지로 간선 1개로 연결되어 있는 세 정점의 개수도 $O(N)$ 만에 구할 수 있다. 차수가 $d$인 정점 $i$를 포함한 간선 1개로 이루어질 수 있는 세점의 개수는 $d \times (N - d - 1)$이다. 이를 다 더한 뒤, 앞에서 구한 간선 2개로 이루어질 수 있는 세 점 개수에 비례하여 값을 빼주면 된다.

총 시간복잡도는 $O(M^{1.5} + N)$이 된다.

#include <stdio.h> #include <vector> using namespace std; #define MAXN 5003 typedef long long lld; int T, N, M, R; int deg[MAXN]; int w[MAXN][MAXN]; bool H[MAXN]; vector <int> con[MAXN]; struct Z{ Z(int s=0, int e=0): s(s), e(e), h(0) {} int s, e; bool h; }; vector <Z> edges; int main() { int ts = 0, i, j; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d", &N, &M); edges.clear(); for (R=1;R*R<M;R++); while (M--){ scanf("%d%d", &i, &j); edges.emplace_back(i, j); w[i][j] = w[j][i] = 1; deg[i]++; deg[j]++; con[i].push_back(j); con[j].push_back(i); } vector <int> Hs; for (i=1;i<=N;i++) if (deg[i] >= R) H[i] = 1, Hs.push_back(i); for (Z &e: edges) if (H[e.s] && H[e.e]) e.h = 1; lld ans = (lld)N*(N-1)*(N-2)/6; int three = 0; for (int a: Hs) for (int b: Hs) if (w[a][b] && a < b) for (int c: Hs) if (b < c){ if (w[a][c] && w[b][c]) three++; } int cnt2 = 0, cnt3 = 0; for (Z &e: edges) if (!e.h){ if (deg[e.s] > deg[e.e]) swap(e.s, e.e); for (int t: con[e.s]){ if (w[t][e.e]){ if (H[t] && H[e.e]) cnt2++; else cnt3++; } } } cnt2 /= 2, cnt3 /= 3; three += cnt2 + cnt3; int two = 0; for (i=1;i<=N;i++) two += deg[i]*(deg[i]-1)/2; two -= three*3; int one = 0; for (i=1;i<=N;i++) one += deg[i]*(N-deg[i]-1); one = one/2 - two; ans -= three + two + one; printf("%lld\n", ans); for (i=1;i<=N;i++){ for (int t: con[i]) w[i][t] = 0; con[i].clear(); deg[i] = H[i] = 0; } } }

F. Pantun Grader

ICPC에 종종 등장하는 영어 문제다. 문제에서 하라는 대로 하면 된다. strtok 함수를 쓰면 쉽게 구현할 수 있다.

#include <stdio.h> #include <cstring> #include <string> #include <vector> using namespace std; #define sz(v) ((int)(v).size()) int T, N, A, B, C, D; char S[9999]; vector <string> V; int get_syl(const string &s) { if (s.find(' ') == string::npos){ int n = s.length(); if (n == 3 && strchr("aeiou", s[0])) return 2; if (n <= 3) return 1; string t = s.substr(n-2); if (n == 6 && (s.find("ng") != string::npos || s.find("ny") != string::npos)) return 2; if (n >= 6) return 3; return 2; } int ret = 0; strcpy(S, s.c_str()); for (char *pt=strtok(S, " \n\r");pt!=NULL;pt=strtok(NULL, " \n\r")){ ret += get_syl(pt); } return ret; } int main() { int ts = 0, i, j; for (scanf("%d ", &T);T--;){ printf("Case #%d: ", ++ts); gets(S); for (i=0;S[i];i++) if (isupper(S[i])) S[i] = tolower(S[i]); V.clear(); for (char *pt=strtok(S, ",.\n\r");pt!=NULL;pt=strtok(NULL, ",.\n\r")){ V.push_back(pt); } N = sz(V); A = B = C = D = 0; if (N > 4) D = 10*(N-4); vector <int> syl; for (string &s: V) syl.push_back(get_syl(s)); for (i=0;i<4&&i<N;i++) if (8 <= syl[i] && syl[i] <= 12) A += 10; for (i=0;i<2&&i+2<N;i++){ if (V[i].substr(V[i].length()-2) == V[i+2].substr(V[i+2].length()-2)) B += 20; if (syl[i] == syl[i+2]) C += 10; } printf("%d %d %d %d %d\n", A, B, C, D, A+B+C-D); } }

G. Hari Merdeka

$N$개의 알파벳이 주어지고, 각 알파벳을 쓰는데 비용이 주어진다. $M$개의 단어가 주어지고, 각 단어마다 문장에 등장 했을 때 얻는 점수가 주어진다. 쓰는데 비용 $B$를 넘지 않는 문장을 쓸 때, 단어 등장 점수의 합이 최대가 되는 문장의 점수를 구하는 문제다.

문제에서 주어지는 단어들을 가지고 Aho-Corasic Trie를 만들면 노드 개수가 최대 10,000개가 된다. Dynamic Programming으로 각 Aho-Corasic의 상태별로 돈을 $b$ 만큼 썼을 때 얻을 수 있는 최대 점수를 구한다. 총 시간복잡도는 $O(NM|W|B)$가 된다.

#include <stdio.h> #include <queue> using namespace std; int T, N, M, B, K; int cost[26], charnum[128], D[201][10001]; char buf[999]; struct NODE{ int score, idx; NODE *nxt[26], *f, *fnxt[26]; } container[10001], *root; NODE *new_node() { NODE *ret = &container[++K]; ret->idx = K; ret->score = 0; for (int i=0;i<N;i++) ret->nxt[i] = 0; ret->f = 0; return ret; } int main() { int ts = 0, i, j, k; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d%d", &N, &M, &B); for (i=0;i<N;i++){ char c; scanf(" %c%d", &c, cost+i); charnum[c] = i; } K = 0; root = new_node(); for (i=0;i<M;i++){ int score; scanf("%s%d", buf, &score); NODE *now = root; for (j=0;buf[j];j++){ int c = charnum[buf[j]]; if (!now->nxt[c]) now->nxt[c] = new_node(); now = now->nxt[c]; } now->score += score; } queue <NODE*> que; for (i=0;i<N;i++){ if (root->nxt[i]) root->nxt[i]->f = root, que.push(root->nxt[i]), root->fnxt[i] = root->nxt[i]; else root->fnxt[i] = root; } while (!que.empty()){ NODE *now = que.front(); que.pop(); for (i=0;i<N;i++){ if (now->nxt[i]){ NODE *t = now->nxt[i]; t->f = now->f; while (t->f != root && !t->f->nxt[i]) t->f = t->f->f; if (t->f->nxt[i]) t->f = t->f->nxt[i]; que.push(t); } NODE* &fnxt = now->fnxt[i]; fnxt = now; while (fnxt != root && !fnxt->nxt[i]) fnxt = fnxt->f; if (fnxt->nxt[i]) fnxt = fnxt->nxt[i]; } now->score += now->f->score; } for (i=0;i<=B;i++) for (j=1;j<=K;j++) D[i][j] = -1; D[0][1] = 0; int ans = 0; for (i=0;i<=B;i++) for (j=1;j<=K;j++) if (D[i][j] >= 0){ if (ans < D[i][j]) ans = D[i][j]; for (k=0;k<N;k++) if (i+cost[k] <= B){ int nxt = container[j].fnxt[k]->idx; if (D[i+cost[k]][nxt] < D[i][j]+container[nxt].score) D[i+cost[k]][nxt] = D[i][j]+container[nxt].score; } } printf("%d\n", ans); } }

H. Túnel de Rata

$S$개의 정점과 $L$개의 간선으로 이루어진 무방향성 그래프가 주어진다. 각 간선에는 길이가 있다. 간선에 카메라를 설치할 때, 설치 비용은 간선 길이와 같다. 그래프에서 모든 싸이클에 대해 싸이클에 속한 간선 중 적어도 하나에는 카메라를 설치하고 싶다. 이 때 카메라를 설치하는 최소 비용을 구하는 문제다.

어떤 간선에 카메라를 설치하면 그 간선이 포함된 싸이클에 대해서는 문제의 조건을 만족시켜준다. 따라서 카메라를 설치한 간선들을 다 지웠을 때 그래프에 싸이클이 존재하지 않으면 된다. 이제 문제는 전체 그래프에서 Maximum Spanning Tree를 구하는 것과 같다.

#include <stdio.h> #include <algorithm> using namespace std; #define MAXN 10004 #define MAXM 100005 int T, N, M; int S[MAXM], E[MAXM], C[MAXM], par[MAXN], num[MAXM]; bool cmp(const int &a, const int &b){ return C[a] > C[b]; } 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, &M); int ans = 0, ans2 = -1; for (i=1;i<=M;i++) scanf("%d%d%d", S+i, E+i, C+i), num[i] = i, ans += C[i]; for (i=1;i<=N;i++) par[i] = i; sort(num+1, num+M+1, cmp); int cnt = 0; for (i=1;i<=M;i++){ int x = num[i]; int a = find(S[x]), b = find(E[x]); if (a == b){ if (ans2 < 0) ans2 = C[x]; continue; } par[b] = a; ans -= C[x]; } printf("%d %d\n", ans, ans2); } }

I. Best Position

'G'(grain)와 'L'(livestock) 두 문자로 이루어진 $R \times C$ 크기의 직사각형이 있다. 마찬가지로 $H \times W$ 크기의 작은 직사각형이 주어진다. 작은 직사각형을 전체 직사각형에 뒤집지 않고 같은 문자의 개수가 최대화 되게 배치하는 문제다.

이 문제는 FFT(Fast Fuorier Transform, 고속 푸리에 변환)으로 해결할 수 있다. 큰 직사각형을 $RC$ 크기의 이진수열로 나타내는데, 위치에 있는 값이 'G'인 경우 1, 아닌 경우 0으로 나타낸다. 마찬가지의 규칙으로 작은 직사각형에 대해서는 $(H-1)C + W$ 크기의 이진수열로 나타낸다. 그런 뒤 FFT를 통해 convolution을 구하면 각 부분직사각형 위치마다 매치되는 'G'의 개수를 구할 수 있다. 마찬가지로 각 부분직사각형 위치마다 매치되는 'L'의 개수를 구할 수 있다. 시간복잡도는 테스트케이스별로 $O(RC \lg RC)$다.

#include <stdio.h> #define _USE_MATH_DEFINES #include <math.h> #include <complex> #include <vector> #include <algorithm> using namespace std; #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() typedef complex<double> base; // FFT code starts void fft(vector <base> &a, bool invert) { int n = sz(a); for (int i=1,j=0;i<n;i++){ int bit = n >> 1; for (;j>=bit;bit>>=1) j -= bit; j += bit; if (i < j) swap(a[i],a[j]); } for (int len=2;len<=n;len<<=1){ double ang = 2*M_PI/len*(invert?-1:1); base wlen(cos(ang),sin(ang)); for (int i=0;i<n;i+=len){ base w(1); for (int j=0;j<len/2;j++){ base u = a[i+j], v = a[i+j+len/2]*w; a[i+j] = u+v; a[i+j+len/2] = u-v; w *= wlen; } } } if (invert){ for (int i=0;i<n;i++) a[i] /= n; } } void multiply(const vector<int> &a,const vector<int> &b,vector<int> &res) { vector <base> fa(all(a)), fb(all(b)); int n = 1; while (n < max(sz(a), sz(b))) n <<= 1; fa.resize(n); fb.resize(n); fft(fa, false); fft(fb, false); for (int i=0;i<n;i++) fa[i] *= fb[i]; fft(fa, true); res.resize(n); for (int i=0;i<n;i++) res[i] = int(fa[i].real()+(fa[i].real()>0?0.5:-0.5)); } // FFT code ends int T, R, C, H, W; char P[501][502], Q[501][502]; void proc(char c, vector <int> &conv) { int i, j; vector <int> a, b; for (i=1;i<=R;i++) for (j=1;j<=C;j++) a.push_back(P[i][j] == c); for (i=1;i<=H;i++){ for (j=1;j<=W;j++) b.push_back(Q[i][j] == c); if (i < H) for (j=0;j<C-W;j++) b.push_back(0); } reverse(all(b)); multiply(a, b, conv); } int main() { int ts = 0, i, j, k; scanf("%d%d", &R, &C); for (i=1;i<=R;i++) scanf("%s", P[i]+1); for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%d%d", &H, &W); for (i=1;i<=H;i++) scanf("%s", Q[i]+1); vector <int> grain, livestock; proc('G', grain); proc('L', livestock); int n = R*C, m = (H-1)*C + W; int y = 0, x = 0, p = 0, q = -1; for (i=m-1;i<n;i++){ int t = i-m+1; int my = t/C + 1, mx = t%C + 1; if (my+H-1 > R || mx+W-1 > C) continue; if (p+q < grain[i] + livestock[i]){ p = grain[i], q = livestock[i]; y = my, x = mx; } } printf("%d %d %d %d\n", y, x, p, q); } }

J. Spokes Wheel

32비트 이진수 A, B가 16진수 형태로 주어진다. A를 최소 회수로 회전시켜서 B를 만들 수 있는 방법을 구하는 문제다.

문제에서 하라는 대로 하면 된다. 32비트 이진수를 unsigned int로 나타내고 비트 연산자를 이용해 쉽게 코딩할 수 있다.

#include <stdio.h> int T; unsigned A, B; int main() { int ts = 0, i; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%x%x", &A, &B); if (A == B){ puts("0 Any"); continue; } int right = 32, left = 32; for (i=0;i<32;i++){ unsigned t = (A >> i) | ((A & ((1 << i)-1)) << (32-i)); if (t != B) continue; if (right > i) right = i; if (left > 32-i) left = 32-i; } if (right < left) printf("%d Right\n", right); else if (right > left) printf("%d Left\n", left); else{ if (right == 32) puts("Not possible"); else printf("%d Any\n", left); } } }

K. Ball

'W' (White), 'R' (Red), 'G' (Green) 중 하나의 색으로 색칠되어있는 공 $L$개가 원형으로 배치되어 있다. 단위 시간이 지나면 특정 규칙에 따라 공의 색이 변한다. 단위 시간 $N$이 지났을 때, 각 색 별로 공이 몇 개 있는지 구하는 문제다.

'W'를 0, 'R'을 1, 'G'를 2로 나타내자. 그러면 단위 시간이 지났을 때 변하게 되는 공의 색은 (자기 색 + 오른쪽 공의 색)을 3으로 나눈 나머지가 된다. 현재 색을 $a_i (0 \leq i < L)$로 나타내자. 단위 시간이 한 번 지났을 때 공의 색을 $b_i$로 나타내면 $b_i = a_i + a_{i+1}$이 된다.

단위 시간이 세 번 지났을 때 공의 색을 $c_i$로 나타내면 $c_i = a_i + 3a_{i+1} + 3a_{i+2} + a_{i+3}$가 된다. 이를 3으로 나눈 나머지이므로 정리하면 $c_i = a_i + a_{i+3}$이 된다.

마찬가지로 단위 시간이 아홉 번 지났을 때 공의 색을 $d_i$로 나타내면 $d_i = a_i + a_{i+9}$가 된다. 그렇다는 것은 단위 시간이 $3^k$번 지난 이후 $i$번 공의 색은 $a_i + a_{i+3^k}$가 된다는 것이다. 이를 통해 단위 시간 $N$이 지났을 때 공의 색을 $O(L \log N)$ 만에 구할 수 있다.

#include <stdio.h> #include <string.h> #define MAXN 20004 typedef long long lld; int T, N, A[MAXN], B[MAXN]; lld K; char S[MAXN]; int main() { int ts = 0, i; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); scanf("%s%lld", S, &K); N = strlen(S); for (i=0;i<N;i++){ if (S[i] == 'R') A[i] = 1; else if (S[i] == 'G') A[i] = 2; else A[i] = 0; } lld v = 1; for (;v<=K/3;v*=3); for (;v;v/=3) while (K >= v){ for (i=0;i<N;i++) B[i] = (A[i]+A[(i+v)%N])%3; for (i=0;i<N;i++) A[i] = B[i]; K -= v; } int cnt[3] = {0,}; for (i=0;i<N;i++) cnt[A[i]]++; for (i=0;i<3;i++) printf("%d ", cnt[i]); puts(""); } }