2015 Asia - Singapore Regional Contest

문제 링크

E. Association for Computing Machinery

N개의 문제가 있는 ICPC 세트가 있다. 각 문제별로 푸는 시간이 주어진다. p번 문제의 First Solve 상을 노려야하기 때문에 p번 문제를 제일 먼저 풀고 제일 좋은 전략으로 문제를 해결할 때, 푼 문제 수와 패널티를 구하는 문제다. 문제는 한 번에 맞는다고 가정한다.

p번 문제를 0번지에 놓고 1번지부터 이후를 푸는 시간순서로 정렬한 다음에 순서대로 시간이 300분이 될 때까지 해결한다.

#include <bits/stdc++.h> using namespace std; int N, P; int A[99]; int main() { scanf("%d%d", &N, &P); for (int i=0;i<N;i++) scanf("%d", A+i); swap(A[0], A[P]); sort(A+1, A+N); int sum = 0, cnt = 0, ans = 0; for (int i=0;i<N;i++){ sum += A[i]; if (sum > 300) break; cnt++; ans += sum; } printf("%d %d\n", cnt, ans); }

F. Air Conditioned Minions

일차원 상에 N개의 선분이 있을 때, 최소 몇 개의 점을 놓아서 모든 선분이 적어도 하나의 점을 포함하도록 하는지를 구하는 문제다.

N 범위와 좌표 범위가 작아서 다양한 방법이 가능하다.

#include <bits/stdc++.h> using namespace std; #define pb push_back int N; vector <int> arr[201]; int main() { scanf("%d", &N); for (int i=1;i<=N;i++){ int a, b; scanf("%d%d", &a, &b); arr[a].pb(b); } int mn = 2e9, ans = 0; for (int i=1;i<=N+N;i++){ if (mn < i) ans++, mn = 2e9; for (int e: arr[i]) mn = min(mn, e); } if (mn < 2e9) ans++; printf("%d\n", ans); }

C. Association for Control Over Minds

0번부터 500,000번까지 번호가 매겨진 재료가 있다. N개의 그룹을 순서대로 만드려고 한다. 그룹은 특정 재료들로 구성되어야한다. 이미 만들어진 그룹에 있는 재료를 일부 빼오는 것은 안되지만 그 그룹 자체를 가져오는 것은 가능하다. 그룹을 만들 수 있으면 무조건 만들 때, 몇 개의 그룹이 만들어지는지 구하는 문제다.

그룹을 만들 수 있는지 확인하는 작업을 union-find를 통해 이룬다. 어떤 그룹을 만들 때, 재료들이 속한 그룹들에 있는 재료 개수의 합이 필요한 재료 개수와 같으면 만들 수 있다는 것이다.

#include <bits/stdc++.h> using namespace std; #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() const int M = 500001; int N; int par[M+1], sz[M+1]; int cp(int n){ return par[n] == n ? n : (par[n] = cp(par[n])); } int main() { for (int i=1;i<=M;i++) par[i] = i, sz[i] = 1; scanf("%d", &N); int ans = 0; for (int i=1;i<=N;i++){ int n; scanf("%d", &n); vector <int> arr(n, 0); for (int j=0;j<n;j++) scanf("%d", &arr[j]), arr[j] = cp(arr[j]+1); sort(all(arr)); arr.erase(unique(all(arr)), arr.end()); int sum = 0; for (int t: arr) sum += sz[t]; if (sum != n) continue; ans++; for (int j=1;j<sz(arr);j++){ int a = arr[0], b = arr[j]; par[b] = a; sz[a] += sz[b]; sz[b] = 0; } } printf("%d\n", ans); }

G. Association for the Country of Mububa

수열이 주어졌을 때, 수열에서 연속성을 유지한 채 임의로 그룹을 나눈다. 왼쪽에 있는 그룹에 있는 수의 합이 오른쪽 그룹에 있는 수의 합 보다 크면 안된다. 이 때, 그룹 개수의 최대값을 구하는 문제다.

D[i][j] = 수열이 1번부터 j번까지 있다고 했을 때, 제일 오른쪽 그룹은 i번부터 j번까지인 경우, 그룹 개수의 최대값

위와 같이 다이나믹 배열을 정의하자. 대충 생각하면 $O(N^3)$ 방법이 떠오르지만 어렵지 않게 이를 $O(N^2)$으로 개선시킬 수 있다.

#include <bits/stdc++.h> using namespace std; typedef long long lld; int N; int A[3003], D[3003][3003], E[3003][3003]; lld S[3003]; int main() { scanf("%d", &N); for (int i=1;i<=N;i++) scanf("%d", A+i), S[i] = S[i-1] + A[i]; for (int i=1;i<=N;i++){ D[1][i] = 1; for (int j=i,k=i-1;j>1;j--){ if (k >= j) k = j-1; while (k > 0 && S[j-1] - S[k-1] <= S[i] - S[j-1]) k--; if (E[k+1][j-1]) D[j][i] = E[k+1][j-1] + 1; } for (int j=i;j;j--) E[j][i] = max(D[j][i], E[j+1][i]); } int ans = 0; for (int i=1;i<=N;i++) ans = max(ans, D[i][N]); printf("%d\n", ans); }

J. Association of Cats and Magical Lights

루트가 있는 트리가 주어지고, 각 노드별로 1이상 100이하의 수로 나타내는 색이 칠해져있다. 어떤 노드를 루트로 하는 서브트리에서 홀수번 등장하는 색의 개수를 구하는 쿼리와, 어떤 노드의 색을 바꾸는 쿼리를 해결하는 문제다.

트리에서 노드를 DFS 탐색 순서로 번호를 매기면, 어떤 노드를 루트로한 서브트리에 있는 노드 번호들은 연속되게 나타난다. 이를 이용해서 인덱스트리를 통해 문제를 해결할 수 있다. 노드에 색이 칠해져있다는 것을 비트로 나타내면 범위에 해당하는 노드의 비트들을 xor 연산했을 때 1의 개수가 홀수번 등장하는 색의 개수임을 알 수 있다. 색이 100종류이므로 이를 64bit 정수형 두 개로 표현하면 된다.

#include <bits/stdc++.h> using namespace std; #define MAXN 300005 #define pb push_back #define bit(n) (1LL << (n)) #define TS 1048576 typedef long long lld; int N, Q, K; int A[MAXN], num[MAXN], out[MAXN]; vector <int> con[MAXN]; void dfs(int n) { num[n] = ++K; for (int t: con[n]) dfs(t); out[n] = K; } struct Z{ lld a, b; Z operator ^ (const Z &ot)const{ return {a^ot.a, b^ot.b}; } void color(int n) { if (n > 50) b |= bit(n-51); else a |= bit(n-1); } int count() { int ret = 0; for (lld v=a;v;v^=v&(-v)) ret++; for (lld v=b;v;v^=v&(-v)) ret++; return ret; } } tree[TS]; int ST = TS/2-1; void change(int x, int c) { int n = ST+x; tree[n] = {0,}; tree[n].color(c); for (n>>=1;n;n>>=1) tree[n] = tree[n+n]^tree[n+n+1]; } Z get(int l, int r) { Z ret = {0,}; for (l+=ST,r+=ST;l<=r;l>>=1,r>>=1){ if (l&1) ret = ret^tree[l++]; if (!(r&1)) ret = ret^tree[r--]; } return ret; } int main() { scanf("%d%d", &N, &Q); for (int i=1;i<=N;i++) scanf("%d", A+i); for (int i=2;i<=N;i++){ int t; scanf("%d", &t); con[t].pb(i); } dfs(1); for (int i=1;i<=N;i++) tree[ST+num[i]].color(A[i]); for (int i=ST;i;i--) tree[i] = tree[i+i]^tree[i+i+1]; while (Q--){ int k, x; scanf("%d%d", &k, &x); if (k){ change(num[x], k); }else{ Z z = get(num[x], out[x]); printf("%d\n", z.count()); } } }

A. Association for Cool Machineries (Part 1)

$N \times N$ 크기의 미로판에 로봇이 놓여있고, 이동 명령이 주어진다. 로봇이 한 곳에 멈춰 있거나 무한히 움직이는데, 한 곳에 멈춰있으면 1을 출력하고, 무한히 움직이면 움직이는 싸이클의 최소 크기를 출력하는 문제다.

하나의 로봇의 위치와 현재 처리하는 명령의 위치 쌍에 대해서 다음 위치, 명령의 위치 쌍은 항상 같게 나온다. 즉, out degree가 1인 방향성 그래프에서 싸이클을 찾는 문제로 생각할 수 있다. 이 때 노드 개수는 약 $200 \times 200 \times 200$개가 된다. 문제에서 해결해야되는 것은 싸이클의 최소 크기를 구하는 것이므로 노드에서의 싸이클 크기가 아니라 로봇의 위치만 가지고 싸이클의 최소 크기를 구해야한다. 싸이클의 최소 크기는 노드에서의 싸이클 크기의 약수이며, 이를 구하는 것은 KMP 알고리즘을 통해 선형시간안에 해결가능하다.

#include <bits/stdc++.h> using namespace std; #define MAXL 6000006 #define pb push_back int yy[]={-1, 0, 1, 0}, xx[]={0, 1, 0, -1}; int N, M, L, sy, sx; int D[203][203][203]; int dir[128]; char C[203], A[203][203]; struct Z{ int y, x, t; bool operator == (const Z &ot)const{ return y == ot.y && x == ot.x; } } P[MAXL]; int F[MAXL]; int main() { dir['>'] = 1; dir['v'] = 2; dir['<'] = 3; scanf("%d%s", &N, C); M = strlen(C); for (int i=1;i<=N;i++) scanf("%s", A[i]+1); for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) if (A[i][j] == 'R') sy = i, sx = j; D[sy][sx][0] = 1; Z now = {sy, sx, 0}; for (;;){ int d = dir[C[now.t]]; Z nxt = {now.y+yy[d], now.x+xx[d], (now.t+1)%M}; if (A[nxt.y][nxt.x] == '#') nxt.y = now.y, nxt.x = now.x; if (D[nxt.y][nxt.x][nxt.t]) break; D[nxt.y][nxt.x][nxt.t] = D[now.y][now.x][now.t]+1; now = nxt; } Z start = now; for (;;){ int d = dir[C[now.t]]; Z nxt = {now.y+yy[d], now.x+xx[d], (now.t+1)%M}; if (A[nxt.y][nxt.x] == '#') nxt.y = now.y, nxt.x = now.x; else P[++L] = nxt; if (start == nxt && start.t == nxt.t) break; now = nxt; } if (!L){ puts("1"); return 0; } for (int i=2,k=0;i<=L;i++){ while (k && !(P[k+1] == P[i])) k = F[k]; if (P[k+1] == P[i]) k++; F[i] = k; } int ans = L; for (int i=F[L];i;i=F[i]) if (L % (L-i) == 0) ans = min(ans, L-i); printf("%d\n", ans); }

H. Association for Convex Main Office

2차원 좌표 평면에서 볼록다각형을 구성하는 N개의 점을 구하는 문제다. 점은 좌표 범위가 정해져있는 정수 좌표 위에 있어야한다.

이는 ICPC에서 보기드문 Output-Only 문제다. 정해져있는 정해가 있다기보다는 여러 테스트를 거쳐서 답을 도출해내야한다. 내 방법의 핵심 아이디어는 크기가 1보다 작은 기약분수들을 여러 개 구한 후 이용하는 것이다. 이 기약분수가 좌표 범위에 영향을 주는 정도는 분모와 분자의 합이다. 즉, 분모 분자 합이 작은 기약 분수들을 5만개 이용해서 이를 대칭시켜 볼록다각형을 완성하는 것이다. 말로 설명하기 너무 어려워서, 자세한 방법은 아래 코드를 참고하자.

#include <bits/stdc++.h> using namespace std; #define MAXN 500000 #define pb push_back #define all(v) (v).begin(), (v).end() typedef long long lld; int N; int stk[MAXN], scnt; struct Z{ int x, y; } A[MAXN]; int ccw(int ax, int ay, int bx, int by, int cx, int cy) { lld k = (lld)(bx - ax) * (cy - ay) - (lld)(cx - ax) * (by - ay); if (k > 0) return 1; if (k) return -1; return 0; } int ccw(Z a, Z b, Z c){ return ccw(a.x, a.y, b.x, b.y, c.x, c.y); } int gcd(int a, int b){ return b ? gcd(b, a%b) : a; } int main() { vector <Z> frac; for (int i=2;i<999;i++){ for (int j=1;j<i;j++) if (gcd(i, j) == 1){ frac.pb({i, j}); } } sort(all(frac), [](const Z &a, const Z &b){ return a.x+a.y < b.x+b.y; }); int sum = 0; vector <Z> lst; for (Z &z: frac){ sum += z.x + z.y; if (sum > 20000000) break; lst.pb(z); } sort(all(lst), [](const Z &a, const Z &b){ return (lld)a.y * b.x < (lld)b.y * a.x; }); auto lst2 = lst; reverse(all(lst2)); int x = 20000000, y = 0; for (Z &z: lst){ A[++N] = {x, y}; x += z.x, y += z.y; } for (Z &z: lst2){ A[++N] = {x, y}; x += z.y, y += z.x; } for (Z &z: lst){ A[++N] = {x, y}; x -= z.y, y += z.x; } for (Z &z: lst2){ A[++N] = {x, y}; x -= z.x, y += z.y; } for (Z &z: lst){ A[++N] = {x, y}; x -= z.x, y -= z.y; } for (Z &z: lst2){ A[++N] = {x, y}; x -= z.y, y -= z.x; } for (Z &z: lst){ A[++N] = {x, y}; x += z.y, y -= z.x; } for (Z &z: lst2){ A[++N] = {x, y}; x += z.x, y -= z.y; } /* Get convex hull for cross checking */ for (int i=2;i<=N;i++) if (A[1].y > A[i].y || A[1].y == A[i].y && A[1].x > A[i].x) swap(A[1], A[i]); sort(A+2, A+N+1, [](const Z &a, const Z &b){ int k = ccw(A[1], a, b); if (k) return k > 0; return abs(a.x-A[1].x)+abs(a.y-A[1].y) < abs(b.x-A[1].x)+abs(b.y-A[1].y); }); stk[scnt=1] = 1; for (int i=2;i<=N;i++){ while (scnt > 1 && ccw(A[stk[scnt-1]], A[stk[scnt]], A[i]) <= 0) scnt--; stk[++scnt] = i; } if (N != scnt) return 0; scanf("%d", &N); for (int i=1;i<=N;i++) printf("%d %d\n", A[i].x, A[i].y); }

D. Association of Computer Maintenance

약수의 개수가 $10^{10}$이하이고 소인수가 전부 100 보다 작으며, 한 소인수의 지수가 100보다 크지 않은 수가 주어진다. 이 수를 $A \times B$ 꼴로 나타내는 두 자연수 $A$, $B$가 있을 때 $A+B$의 최소값을 $10^9+7$로 나눈 나머지를 구하는 문제다.

산술기하평균에 의해 $A+B$가 최소가 되기 위해서는 $A/B$가 1이상이면서 제일 작은 $A$, $B$를 구하면 된다. 우선 긴자리 연산을 피하기 위해 log 스케일로 바꿔서 계산을 해주어야한다. 약수의 개수가 $10^{10}$ 이하이고 소인수의 지수가 100보다 크지 않으므로, 이 수를 약수의 개수가 $10^6$이하인 두 수로 나누어 약수들을 구한 뒤 $log A/B$가 0이상이면서 가장 작은 쌍을 구해 답을 구하면 된다.

#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 long long lld; const int MOD = 1e9 + 7; int N, P; int A[351], allcnt[99]; int primes[26], primenum[99]; char S[999]; struct Z{ int n, p; } L[99], R[99]; int LC, RC; struct NUM{ int cnt1[26], cnt2[26]; // 25 prime numbers under 100 double log; }; vector <NUM> LD, RD; int LDC, RDC; int nowcnt1[99], nowcnt2[99]; void dfs(int n, int sz, Z arr[], vector <NUM> &to) { if (n > sz){ NUM t = {0,}; for (int i=1;i<=P;i++){ t.cnt1[i] = nowcnt1[i], t.cnt2[i] = nowcnt2[i]; t.log += log10(primes[i])*(nowcnt1[i] - nowcnt2[i]); } to.pb(t); return; } for (int i=0;i<=arr[n].p;i++){ nowcnt1[primenum[arr[n].n]] = i; nowcnt2[primenum[arr[n].n]] = arr[n].p-i; dfs(n+1, sz, arr, to); nowcnt1[primenum[arr[n].n]] = nowcnt2[primenum[arr[n].n]] = 0; } } int main() { scanf("%s", S); for (int i=0;S[i];i+=2) A[++N] = (S[i]-'0')*10 + S[i+1]-'0'; for (int i=1;i<=N;i++) allcnt[A[i]]++; for (int i=2;i<99;i++) if (allcnt[i]){ primes[++P] = i; primenum[i] = P; } int cnt = 1; for (int i=1;i<=P;i++){ cnt *= (allcnt[primes[i]] + 1); if (cnt > 1e5){ for (int j=i;j<=P;j++) R[++RC] = {primes[j], allcnt[primes[j]]}; break; } L[++LC] = {primes[i], allcnt[primes[i]]}; } if (!RC) R[++RC] = {primes[1], 0}; dfs(1, LC, L, LD); dfs(1, RC, R, RD); LDC = sz(LD), RDC = sz(RD); vector <int> larr(LDC, 0), rarr(RDC, 0); for (int i=0;i<LDC;i++) larr[i] = i; for (int i=0;i<RDC;i++) rarr[i] = i; sort(all(larr), [](const int &a, const int &b){ return LD[a].log < LD[b].log; }); sort(all(rarr), [](const int &a, const int &b){ return RD[a].log < RD[b].log; }); double mn = 2e9; int lt, rt; for (int i=0,j=RDC-1;i<LDC;i++){ while (j && LD[larr[i]].log + RD[rarr[j-1]].log >= 0) j--; double v = LD[larr[i]].log + RD[rarr[j]].log; if (v >= 0){ if (mn > v) mn = v, lt = larr[i], rt = rarr[j]; } } int num1 = 1, num2 = 1; for (int i=1;i<=P;i++){ for (int j=LD[lt].cnt1[i]+RD[rt].cnt1[i];j--;) num1 = (lld)num1*primes[i]%MOD; for (int j=LD[lt].cnt2[i]+RD[rt].cnt2[i];j--;) num2 = (lld)num2*primes[i]%MOD; } printf("%d\n", (num1+num2)%MOD); }

B. Association for Cool Machineries (Part 2)

A번 문제에서 답의 크기가 1,000,000 이상이 나오는 입력데이터를 출력하는 프로그램을 만드는 문제다.

ICPC에서 정말 보기드문 Output-Only 문제다. 대회 주최측의 방법은 크기가 197만인 데이터까지 있다고 한다. 내 방법은 102만 정도나오며, 개선의 여지가 충분하다.

이 문제에서 답의 크기를 최대화 시키기 위한 핵심 아이디어는 아래 세 가지다.

1. 전체를 하나의 싸이클로 만들어야하며, 싸이클에 포함되는 칸의 개수가 많을수록 좋다.

2. 싸이클을 이루는 기본 명령 문자열을 구한 뒤, 앞 또는 뒤에 '><' 또는 '^v' 등을 붙여 진동시켜주는 것이 좋다.

3. 기본 명령 문자열은 짧으면 짧을수록 좋다.

사실 3번 아이디어는 크게 중요한 것은 아니지만, 100만보다 조금 작은 데이터를 개선시킬 때는 많이 중요하다. 시간이 5분도 남지 않아서 개선은 못했지만, 대회 때 95만 짜리 데이터를 만든 적이 있다.

1번 아이디어에서 싸이클을 만들 때, 중요한 것은 장애물이다. 장애물의 위치에 따라 결과적으로 움직이는 방향이 달라진다.

#include <bits/stdc++.h> using namespace std; const int N = 197; // N = 4x + 5 = 5y + 7 void print(const string &s, int n=1) { for (int i=n;i--;) printf("%s", s.c_str()); } int main() { string pat = ">>>vvv<<^^^^^^^>>><<vvv"; printf("%d\n", N); for (int i=(N-pat.length())/2;i-->0;) printf("><"); printf("%s\n", pat.c_str()); print("#", N); puts(""); print("#R"); print(".", N-3); puts("#"); for (int i=(N-7)/5;i--;){ print("#."); print("#", N-4); puts(".#"); print("#.#"); print("...#", (N-5)/4); puts(".#"); print("#.#."); print("#...", (N-5)/4); puts("#"); print("#.#."); print("#", N-4); puts(""); print("#.#"); print(".", N-4); puts("#"); } print("#."); print("#", N-4); puts(".#"); print("#.#"); print("...#", (N-5)/4); puts(".#"); print("#.#."); print("#...", (N-5)/4); puts("#"); print("#..."); print("#", N-4); puts(""); print("#", N); puts(""); }