Google CodeJam 2019 Round 2 풀이

문제 및 채점: 사이트

A. New Elements: Part 1

 

질량이 X인 원소 C가 있고, 질량이 Y인 원소 J가 있다. 분자 N개가 있는데, i번째 분자에 포함된 원소 C의 개수는 C[i]개고, 포함된 원소 J의 개수는 J[i]개다. 원소 C와 원소 J 이외에 다른 원소는 포함되어 있지 않다. 분자를 질량 순서대로 정렬하려고 한다. 다만, 분자의 질량은 모두 달라야 한다. 이때, 정렬 결과로 가능한 순서는 모두 몇 개인지 구하는 문제다.

 

서로 다른 i와 j에 대해, C[i] ≤ C[j], J[i] ≤ J[j]를 만족하면 질량 X, Y와 상관없이 질량의 대소 관계가 명확하다. 다만, C[i] < C[j], J[i] > J[j]와 같이 원소 C 개수의 대소 관계와 원소 J 개수의 대소 관계가 뒤집혀있을 때에는 질량 X, Y의 비율에 따라 대소 관계가 달라진다. 그리고 질량 X와 Y의 값이 정해지면 순서는 유일하게 결정된다. 이 문제의 풀이는 서로 다른 분자에 대해 같은 질량이 되는 질량 X, Y의 비율을 모두 구하여 가지 수를 구하고 1을 더하면 문제에서 요구한 가능한 순서의 개수가 된다.

 

#include <bits/stdc++.h> using namespace std; #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() typedef pair<int, int> pii; int T, N; int A[301], B[301]; int gcd(int a, int b){ return b ? gcd(b, a%b) : a; } void solve() { scanf("%d", &N); for (int i=1;i<=N;i++) scanf("%d%d", A+i, B+i); vector <pii> arr; for (int i=1;i<=N;i++) for (int j=1;j<=N;j++){ if (A[i] > A[j] && B[i] < B[j]){ int a = B[j]-B[i], b = A[i]-A[j], g = gcd(a, b); a /= g, b /= g; arr.pb({a, b}); } } sort(all(arr)); arr.erase(unique(all(arr)), arr.end()); printf("%d\n", sz(arr)+1); } int main() { for (scanf("%d", &T);T--;){ static int ts = 0; printf("Case #%d: ", ++ts); solve(); } }

 

B. Pottery Lottery

 

1번부터 100번까지 차례대로 번호가 매겨진 사람 100명이 게임에 참가한다. 화분이 20개가 있는데, 1번 사람부터 차례대로 나와 자신의 번호표를 임의로 한 화분을 정해 그 화분 아래에 둔다. 100명의 사람이 모두 자신의 번호표를 두고 난 뒤 게임이 종료되며, 가장 적은 수의 번호표가 있는 화분에 번호표를 둔 사람이 게임의 승자가 된다. 만약, 가장 적은 수의 번호표가 있는 화분이 여러 개라면 게임은 무효가 되며 아무도 승자가 되지 않는다.

 

문제는 이 게임에서 100번 사람이 되어 두 종류의 반칙을 적절히 사용하여 자신의 승률을 90% 이상으로 만드는 것이다. 두 종류의 반칙은 다음과 같다.

1. 어떤 사람이 화분에 번호표를 두고 난 뒤, 아주 정교하게 위조된 번호표를 만들어 원하는 화분 아래에 둔다. 위조한 번호표에 번호는 마음대로 적을 수 있다.

2. 어떤 사람이 화분에 번호표를 두고 난 뒤, 원하는 화분을 선택하여 그 화분에 있는 번호표 구성을 확인할 수 있다. 다만, 직전에 번호표를 둔 화분이 무엇인지는 알지 못한다.

 

모든 화분에 100이 적힌 번호표를 위조하여 정확히 하나씩 넣어두자. 그러면, 가장 적은 수의 번호표가 있는 화분이 여러 개가 아닌 경우에는 항상 승자가 될 수 있다. 100번의 차례 중에 20번은 각 화분에 100이 적힌 번호표를 넣어두는데 활용하고, 나머지 80번은 최소 동률을 최대한 없애는데 활용하면 된다. 이때, 가능한 전략은 여러 가지가 가능하다.

 

아래에 첨부된 코드에서 구현한 방법은 80번 중 첫 50번은 1 이상 10 이하 화분 중에 임의로 한 화분을 선택하여 아무 번호표를 아래에 넣어둔다. 즉, 1 이상 10 이하의 화분은 최소 개수의 번호표가 없도록 밑 작업을 한다. 이후 20번은 각 화분에 있는 번호표 개수를 조사하여, 다음 10번 동안 조사한 번호표 개수를 토대로 번호 충돌이 일어나지 않게 동률을 없애는데 집중한다. 이렇게 구현했을 때, 총 250개의 게임 중 평균 약 235 게임의 승자가 된다.

 

#include <bits/stdc++.h> using namespace std; int main() { int T; for (scanf("%d", &T);T--;){ vector <int> cnt(21, 0); vector <queue<int>> rest(21); for (int i=1;i<=100;i++){ scanf("%*d"); if (i < 20){ printf("%d 100\n", i); fflush(stdout); } else if (i == 100){ printf("20 100\n"); fflush(stdout); } else if (70 <= i && i < 90){ int vase = i-70+1; printf("%d 0\n", vase); fflush(stdout); int n; scanf("%d", &n); vector <bool> vis(70, 0); for (int j=0;j<n;j++){ int idx; scanf("%d", &idx); if (idx < 70) vis[idx] = 1; } int x = 1; for (int j=1;j<70;j++) if (!vis[j]){ rest[vase].push(x); } cnt[vase] = n; } else if (i >= 90){ int t1 = 1, t2 = 2; for (int j=3;j<=20;j++){ if (cnt[t1] >= cnt[j]) t2 = t1, t1 = j; else if (cnt[t2] >= cnt[j]) t2 = j; } cnt[t2]++; printf("%d %d\n", t2, rest[t2].front()); fflush(stdout); rest[t2].pop(); } else{ int vase = (i-20)%10+1; printf("%d 100\n", vase); fflush(stdout); } } } }

 

C. New Elements: Part 2

 

질량이 X인 원소 C가 있고, 질량이 Y인 원소 J가 있다. 분자 N개가 있는데, i번째 분자에 포함된 원소 C의 개수는 C[i]개고, 포함된 원소 J의 개수는 J[i]개다. 원소 C와 원소 J 이외에 다른 원소는 포함되어 있지 않다. 분자들은 질량 순서대로 주어지며, 서로 다른 두 분자는 같은 질량을 가지지 않는다. 이때, 가능한 질량 X, Y를 구하는데, 가능한 X 중 가장 작은 값을 구하며, 만약, 질량 X가 가장 작은 경우가 여러 가지라면 질량 Y도 가장 작은 값으로 구하는 문제다.

 

i < j인 i, j에 대해 C[i] < C[j]이고, J[i] > J[j]인 경우를 생각하면 질량 X와 Y의 비율 Y/X는 다음 조건을 만족해야 한다.

$\cfrac{Y}{X} < \cfrac{C_j-C_i}{J_i-J_j}$

비슷한 경우로, C[i] > C[j]이고, J[i] < J[j]인 경우를 생각하면 다음 조건을 만족해야 한다.

$\cfrac{Y}{X} > \cfrac{C_i-C_j}{J_j-J_i}$

 

이처럼 질량 비율 Y/X에 대해 하한과 상한이 정해진다. 즉, 유리수 $l$과 $r$에 대해, $l < \frac{Y}{X} < r$을 만족하는 가장 작은 $(X, Y)$를 구하는 문제가 된다. 이는 Stern-Brocot 트리에서 이분 탐색을 통해 $O(\lg{X+Y})$ 시간에 해결할 수 있다.

 

#include <bits/stdc++.h> using namespace std; typedef long long lld; int T, N; int A[11], B[11]; struct F{ lld gcd(lld a, lld b){ return b ? gcd(b, a%b) : a; } F(lld a=0, lld b=0){ lld g = gcd(a, b); a /= g; b /= g; F::a = a; F::b = b; } lld a, b; bool operator < (const F &ot)const{ return a*ot.b < ot.a*b; } }; void solve() { scanf("%d", &N); for (int i=1;i<=N;i++) scanf("%d%d", A+i, B+i); F l(0, 1), r(1, 0); for (int i=1;i<=N;i++) for (int j=i+1;j<=N;j++){ if (A[i] < A[j]){ if (B[i] > B[j]){ F v(A[j]-A[i], B[i]-B[j]); r = min(r, v); } }else if (A[i] > A[j]){ if (B[i] < B[j]){ F v(A[i]-A[j], B[j]-B[i]); l = max(l, v); } else{ puts("IMPOSSIBLE"); return; } }else{ if (B[i] > B[j]){ puts("IMPOSSIBLE"); return; } } } if (!(l < r)){ puts("IMPOSSIBLE"); return; } F s(0, 1), e(1, 0), t; for (;;){ F m(s.a+e.a, s.b+e.b); if (l < m && m < r){ t = m; break; } if (!(m < r)){ // go left lld ks = 1, ke = 1; while (!(F(ke*s.a+e.a, ke*s.b+e.b) < r)) ke <<= 1; while (ks <= ke){ lld km = ks+ke>>1; if (F(km*s.a+e.a, km*s.b+e.b) < r) ke = km-1; else ks = km+1; } e = F(ke*s.a+e.a, ke*s.b+e.b); }else{ // go right lld ks = 1, ke = 1; while (!(l < F(s.a+ke*e.a, s.b+ke*e.b))) ke <<= 1; while (ks <= ke){ lld km = ks+ke>>1; if (l < F(s.a+km*e.a, s.b+km*e.b)) ke = km-1; else ks = km+1; } s = F(s.a+ke*e.a, s.b+ke*e.b); } } printf("%lld %lld\n", t.b, t.a); } int main() { for (scanf("%d", &T);T--;){ static int ts = 0; printf("Case #%d: ", ++ts); solve(); } }

 

D. Contransmutation

 

금속 종류 M개가 있다. 금속은 1번부터 M번까지 번호가 매겨져 있다. 연금술을 통하여 i번 금속 1g을 이용하여 R1[i]번 금속 1g과, R2[i]번 금속 1g을 만들 수 있다. 초기에 i번 금속은 G[i]g 만큼 있다. 적절한 연금술 연산을 통하여 1번 금속의 양을 최대로 많이 만드는 문제다. 만약 만들 수 있는 1번 금속의 양이 무한하다면 "UNBOUNDED"를 출력한다.

 

문제 상황을 방향성 그래프로 표현할 수 있다. i번 정점에는 정확히 2개의 나가는 방향 간선이 있는데, 각각 R1[i], R2[i]번 정점을 가리킨다. i번 정점에서 시작하여, 하나 이상의 간선을 통해 다시 i번 정점으로 돌아올 수 있으면 i번 정점을 이용하여 한 종류 이상의 금속을 무한히 만들 수 있다. 이를 통하여 무한히 만들 수 있는 금속(정점)들을 모두 색칠할 수 있다. 이 방법은 그래프에서 SCC(Strongly Connected Component, 강연결요소)를 모두 구하면 편하게 구현할 수 있다. i번 정점에서 하나 이상의 간선을 통해 다시 i번 정점으로 돌아올 수 있는 것의 필요충분조건은 i번 정점이 속한 SCC의 크기가 2이상이거나 i번 정점이 자기 자신을 가리키는 self-edge가 있다는 것이다. 이렇게 일부 무한히 만들 수 있는 정점을 색칠한 뒤에 Flood-Fill을 통해 나머지 무한히 만들 수 있는 정점들도 구할 수 있다. 그러면 이제 정답의 UNBOUNDED 여부를 알 수 있다.

 

정답이 UNBOUNDED가 아닌 경우, 풀이의 핵심 아이디어는 그래프에서 구한 SCC 안에서 무한히 생성 가능한 정점이 없기 때문에 어떤 연금술 연산을 진행해도 SCC 안에서 금속의 총질량은 유지된다는 것이다. 이 아이디어를 통해 SCC의 질량이라는 것을 정의할 수 있고, SCC를 하나의 정점으로 두어 만들어진 DAG(Directed Acyclic Graph, 유향 비순환 그래프)에서 위상 정렬을 통해 1번 정점이 속한 SCC가 가질 수 있는 최종 질량을 구하여 문제에서 요구한 답을 구할 수 있다.

 

#include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define pb push_back const int MOD = 1e9 + 7; int T, N; int A[MAXN]; vector <int> con[MAXN]; int K, G; int idx[MAXN], low[MAXN], grp[MAXN], sz[MAXN]; bool vis[MAXN], self_edge[MAXN]; stack <int> stk; bool inf[MAXN], exist[MAXN]; int gdeg[MAXN], V[MAXN]; vector <int> gcon[MAXN]; // Tarjan's Algorithm void dfs(int n) { idx[n] = low[n] = ++K; stk.push(n); vis[n] = 1; for (int t: con[n]){ if (!idx[t]){ dfs(t); low[n] = min(low[n], low[t]); }else if (vis[t]){ low[n] = min(low[n], idx[t]); } } if (low[n] == idx[n]){ G++; for (;;){ int t = stk.top(); stk.pop(); vis[t] = 0; grp[t] = G; sz[G]++; if (n == t) break; } } } void solve() { scanf("%d", &N); K = G = 0; for (int i=1;i<=N;i++){ con[i].clear(); gcon[i].clear(); idx[i] = low[i] = grp[i] = vis[i] = sz[i] = self_edge[i] = 0; inf[i] = exist[i] = gdeg[i] = V[i] = 0; } for (int i=1;i<=N;i++){ int a, b; scanf("%d%d", &a, &b); con[i].pb(a); con[i].pb(b); if (i == a || i == b) self_edge[i] = 1; } for (int i=1;i<=N;i++) scanf("%d", A+i); for (int i=1;i<=N;i++) if (!idx[i]) dfs(i); for (int i=1;i<=N;i++){ if (A[i]) exist[grp[i]] = 1; V[grp[i]] = (V[grp[i]] + A[i]) % MOD; for (int t: con[i]) if (grp[i] != grp[t]){ gcon[grp[i]].pb(grp[t]); gdeg[grp[t]]++; } } queue <int> que; for (int i=1;i<=G;i++) if (!gdeg[i]) que.push(i); vector <int> order; while (!que.empty()){ int q = que.front(); que.pop(); order.pb(q); if (!exist[q]) inf[q] = 0; for (int t: gcon[q]){ exist[t] |= exist[q]; V[t] = (V[t]+V[q]) % MOD; if (!--gdeg[t]) que.push(t); } } for (int i=1;i<=N;i++) if (self_edge[i] || sz[grp[i]] > 1){ if (!exist[grp[i]]) continue; if (grp[i] == grp[con[i][0]]) inf[grp[con[i][1]]] = 1; if (grp[i] == grp[con[i][1]]) inf[grp[con[i][0]]] = 1; } for (int n: order) for (int t: gcon[n]) inf[t] |= inf[n]; if (inf[grp[1]]) puts("UNBOUNDED"); else printf("%d\n", V[grp[1]]); } int main() { for (scanf("%d", &T);T--;){ static int ts = 0; printf("Case #%d: ", ++ts); solve(); } }