2014-2015 ACM-ICPC, NEERC, Southern Subregional Contest

코드포스 GYM 링크

B. Colored Blanket

이 문제에서 입력이 어떻게 들어오든 상관 없이 답은 항상 존재한다. 이 사실을 간략하게 보이겠다.

담요가 $k$개 있고, 색상 종류가 최대 $n$개 일 때 아래와 같은 두 조건을 만족한다.

1. 가장 공이 적은 색상의 공의 개수 ≤ $\frac{k}{n}$
2. 가장 공이 많은 색상의 공의 개수 ≥ $\frac{k}{n}$

위 두 조건을 만족하기 때문에 하나의 키트에 가장 공이 적은 색상의 공들을 모두 넣고 남은 빈 공간을 가장 공이 많은 색상의 공으로 채우면 하나의 키트에는 두 색만 존재하여 문제 조건을 만족한다. 그리고 문제는 귀납적이게 한 단계로 줄어든다. 남은 공의 개수는 $k - \frac{k}{n}$개이며, 색상의 종류는 최대 $n-1$개다.

#include <stdio.h> #include <stack> using namespace std; #define MAXN 1004 int N, K; int A[MAXN], B[MAXN], C[MAXN]; stack <int> idx[MAXN]; int main() { int i, j, k; scanf("%d%d", &K, &N); for (i=1;i<=K;i++){ scanf("%d", A+i); if (A[i] < 0) A[i] = 1; C[A[i]]++; idx[A[i]].push(i); } for (i=1;i<=N;i++){ int mn = 0, mx = 0; for (j=1;j<=N;j++) if (C[j] < 2e9){ if (!mn || C[mn] > C[j]) mn = j; if (!mx || C[mx] < C[j]) mx = j; } if (C[mn] < K/N){ int left = K/N - C[mn]; while (!idx[mn].empty()) B[idx[mn].top()] = mx, idx[mn].pop(); while (!idx[mx].empty() && left--) B[idx[mx].top()] = mn, idx[mx].pop(), C[mx]--; } C[mn] = 2e9; } puts("Yes"); for (i=1;i<=K;i++){ if (!B[i]) B[i] = A[i]; printf("%d %d\n", A[i], B[i]); } }

C. Component Tree

전형적인 자료구조 문제다. 트리를 inorder로 방문하면서 새로 번호를 매기면, 하나의 서브트리를 연속한 수의 범위로 나타낼 수 있다. 이를 이용해서 top-down 방식의 indexed tree나 segment tree를 사용하면 된다. 가능한 속성이 매우 많을 수 있으므로, 트리의 각 노드에 속성마다 정보를 담고 있어야한다. 이는 STL map container를 사용하면 공간복잡도에 무리가 없다.

이 문제는 쿼리에 대해 바로 답을 출력하고 flush 해야만 다음 입력이 들어오는 대화형(communicate) 문제라는 것에 주의하자.

#include <stdio.h> #include <string.h> #include <string> #include <map> #include <vector> using namespace std; #define MAXN 300005 typedef pair<int, int> pii; int N, M, V, Q, K; int par[MAXN], num[MAXN], out[MAXN], ans[MAXN]; char buf[99]; vector <int> con[MAXN]; vector <pii> nodes[MAXN]; vector <string> values; map <string, int> str_to_num, val_to_num; int to_num(map <string, int> &mmm, const string &s, int &n) { auto it = mmm.find(s); if (it == mmm.end()) return mmm[s] = ++n; return it->second; } struct NODE{ map <int, pii> mem; NODE *left, *right; } container[600009], *root; int XX; NODE *new_node() { NODE *ret = &container[XX++]; ret->mem.clear(); ret->left = ret->right = NULL; return ret; } void dfs(int n) { num[n] = ++K; for (int k: con[n]) dfs(k); out[n] = K; } void write(NODE *now, int s, int e, int l, int r, int p, int v) { if (e < l || s > r) return; if (l <= s && e <= r){ pii &pr = now->mem[p]; if (pr.first < l) pr.first = l, pr.second = v; return; } if (now->left == NULL) now->left = new_node(), now->right = new_node(); int m = (s+e)>>1; write(now->left, s, m, l, r, p, v); write(now->right, m+1, e, l, r, p, v); } void get_value(NODE *now, int s, int e, int n, int p, int &t, int &v) { if (n < s || e < n) return; auto it = now->mem.find(p); if (it != now->mem.end()){ if (t < it->second.first) t = it->second.first, v = it->second.second; } if (s == e) return; int m = (s+e)>>1; if (!now->left) return; get_value(now->left, s, m, n, p, t, v); get_value(now->right, m+1, e, n, p, t, v); } int main() { int i, j, k; scanf("%d", &N); for (i=1;i<=N;i++){ for (scanf("%d%d", par+i, &j);j--;){ scanf("%s", buf); char *p = strtok(buf, "="); char *v = strtok(NULL, "="); int pn = to_num(str_to_num, p, M); int nv = to_num(val_to_num, v, V); nodes[pn].emplace_back(i, nv); } con[par[i]].push_back(i); } values.resize(V+1, ""); values[0] = "N/A"; for (auto it=val_to_num.begin();it!=val_to_num.end();++it) values[it->second] = it->first; dfs(1); root = new_node(); for (i=1;i<=M;i++){ for (pii &pr: nodes[i]){ write(root, 1, N, num[pr.first], out[pr.first], i, pr.second); } } scanf("%d", &Q); for (i=1;i<=Q;i++){ int n; scanf("%d%s", &n, buf); int p = to_num(str_to_num, buf, M); int t = 0, v = 0; get_value(root, 1, N, num[n], p, t, v); printf("%s\n", values[v].c_str()); fflush(stdout); } }

D. Data Center

문제에서 요구하는 구매해야하는 서버의 최소 개수는 쉽게 구할 수 있다. 용량이 많은 것 부터 사면서 총 용량이 $M$이상을 만족하는 순간을 계산하면 된다. 이제 구매해야하는 서버 개수 $K$를 알았다. $V_i \in \{0, 1\}$이므로 $V_i = 1$인 서버를 가장 많이 구매하면 된다. $V_i = 1$인 서버를 $x$개 샀을 때, $V_i = 0$인 서버를 $K-x$개 사는 것이므로, 각 서버 종류마다 가장 용량이 많은 서버 상위 $x$개와 $K-x$개의 용량을 합한 값이 $M$ 이상인지 매번 확인해주면 된다.

#include <stdio.h> #include <algorithm> using namespace std; #define MAXN 200005 typedef long long lld; int N, K, P, Q; lld M, X[MAXN], Y[MAXN]; struct Z{ lld a; int l, idx; bool operator < (const Z &ot)const{ return a < ot.a; } } A[MAXN]; int main() { int i, j, k; while (scanf("%d%lld", &N, &M) != EOF){ for (i=1;i<=N;i++){ scanf("%lld%d", &A[i].a, &A[i].l); A[i].idx = i; } sort(A+1, A+N+1); lld sum = 0; K = 0; for (i=N;i;i--){ sum += A[i].a; K++; if (sum >= M) break; } P = Q = 0; for (i=N;i;i--){ if (A[i].l) X[++P] = A[i].a, X[P] += X[P-1]; else Y[++Q] = A[i].a, Y[Q] += Y[Q-1]; } int ans = -1; for (i=0;i<=P&&i<=K;i++){ if (Q < K-i) continue; if (X[i]+Y[K-i] >= M) ans = i; } printf("%d %d\n", K, ans); int p = ans, q = K-ans; for (i=N;i;i--){ if (A[i].l && p){ p--; printf("%d ",A[i].idx); }else if (!A[i].l && q){ q--; printf("%d ",A[i].idx); } } puts(""); } }

E. Election of Mayor

선거구를 합칠 때 현재 시장이 이득을 보는 경우는 아래 두 가지 뿐이다.

1. 자신이 이긴 선거구와 자신이 진 선거구를 합쳐 이기는 경우
2. 자신이 진 선거구 두 개를 합쳐 지는 경우

살펴보면 두 가지 경우 모두, 전체적으로 자신이 지는 선거구 하나를 없애는 똑같은 효과를 보인다. 따라서, 최소 몇 개의 선거구를 합쳐야 최종적으로 전체 선거를 이기는지 바로 계산할 수 있다. 이제 실제로 선거구들의 득표 현황을 봤을 때 그것이 가능한지 확인하고, 가능하다면 어떤 선거구들을 합칠지 출력한다.

#include <stdio.h> #define MAXN 200005 int N, A[MAXN], B[MAXN], W, L, ans; bool win[MAXN], C[MAXN]; int main() { int i, j, k; scanf("%d", &N); for (i=1;i<=N;i++){ scanf("%d%d", A+i, B+i); if (A[i] > B[i]) win[i] = 1, W++; else L++; } if (W > L){ puts("0"); return 0; } for (i=1;i<N;i++){ if (!win[i] && !win[i+1]) C[i] = 1; else{ int c = win[i] + win[i+1]; if (c == 2) continue; if (A[i]+A[i+1] > B[i]+B[i+1]) C[i] = 1; } } ans = L-W+1; int cnt = 0; for (i=1;i<N;i++) if (C[i]) i++, cnt++; if (cnt < ans){ puts("-1"); return 0; } printf("%d\n", ans); for (i=1;i<N&&ans;i++) if (C[i]) ans--, printf("%d %d\n", i, i+1), i++; }

F. Ilya Muromets

연속한 $K$개의 목을 자를 수 있다. 두 번의 칼질을 할 수 있다. P[i] = 1~i까지 목들이 있을 때 한 번의 칼질로 얻을 수 있는 최대 값이라고 정의하고, Q[i] = i~N까지 목들이 있을 때 한 번의 칼질로 얻을 수 있는 최대 값이라고 정의하자. 그러면 답은 P[i]+Q[i+1] (for 0 ≤ i ≤ N)이 된다.

#include <stdio.h> #include <algorithm> using namespace std; #define MAXN 200005 int N, K; int A[MAXN], P[MAXN], Q[MAXN]; int main() { int i; scanf("%d%d", &N, &K); for (i=1;i<=N;i++) scanf("%d", A+i); int sum = 0; for (i=1;i<=N;i++){ sum += A[i]; if (i > K) sum -= A[i-K]; P[i] = max(sum, P[i-1]); } sum = 0; for (i=N;i;i--){ sum += A[i]; if (i+K <= N) sum -= A[i+K]; Q[i] = max(sum, Q[i+1]); } int ans = 0; for (i=0;i<=N;i++) ans = max(ans, P[i]+Q[i+1]); printf("%d\n", ans); }

G. FacePalm Accounting

크기가 $K$인 연속한 구간을 왼쪽부터 본다. 어떤 구간의 합이 음이 아닌 정수라고 하자. 그러면 그 구간 내에서 가장 오른쪽 값부터 감소 시키는 것이 전체적으로 좋음을 알 수 있다. 이를 이용해 오른쪽 부터 값을 감소시킨다. 그러면 총 시간복잡도 $O(N)$만에 문제를 해결할 수 있다.

#include <stdio.h> #define MAXN 200005 int N, K, M; int A[MAXN], P[MAXN]; int to(int n){ return P[n] == n ? n : (P[n] = to(P[n])); } int main() { int i, j; scanf("%d%d", &N, &K); for (i=1;i<=N;i++){ scanf("%d", A+i); P[i] = i; if (M > A[i]) M = A[i]; } int sum = 0, ans = 0; for (i=1;i<=N;i++){ sum += A[i]; if (i < K) continue; sum -= A[i-K]; if (sum < 0) continue; int v = sum+1; ans += sum+1; sum = -1; for (j=i;v;j--){ j = to(j); int m = A[j]-M; if (m >= v) A[j] -= v, v = 0; else{ v -= m, A[j] = M; P[j] = to(j-1); } } } printf("%d\n", ans); for (i=1;i<=N;i++) printf("%d ", A[i]); puts(""); }

I. Sale in GameStore

게임들을 가격이 싼 순서대로 정렬한 뒤, 가장 비싼 게임의 비용보다 같거나 작을 때 까지 살 수 있다. 주의해야할 것은 $N=1$인 경우 답이 2가 나오지 않게 조심한다.

#include <stdio.h> #include <algorithm> using namespace std; int N, A[2001]; int main() { int i; scanf("%d", &N); for (i=1;i<=N;i++) scanf("%d", A+i); sort(A+1, A+N+1); int sum = 0, ans = 1; for (i=1;i<N;i++){ sum += A[i]; if (sum > A[N]) break; ans++; } printf("%d\n", ans); }

K. Treeland

문제를 재귀적이게 생각할 수 있다. 어떤 노드에서 제일 먼 노드는 트리의 터미널 노드가 된다. 각 노드에서 제일 먼 노드들을 추려서 터미널 노드들을 구한다. 터미널 노드에서 가장 가까운 노드는 터미널 노드와 간선이 연결되어 있음이 자명하다. 이들을 간선으로 연결해준 뒤, 트리에서 구한 터미널 노드들을 제거한다. 이를 반복한다.

#include <stdio.h> #include <vector> using namespace std; int T, N, M; int w[2001][2001], P[2001]; bool V[2001]; int main() { int i, j, k; for (scanf("%d", &T);T--;){ scanf("%d", &N); for (i=1;i<=N;i++){ V[i] = 0; P[i] = N; for (j=1;j<=N;j++) scanf("%d", w[i]+j); } for (M=N;M>1;){ if (M == 2){ for (i=1;i<=N;i++) if (!V[i]) printf("%d ", i); puts(""); break; } vector <int> term; for (i=1;i<=N;i++) if (!V[i]){ while (P[i] > 0 && V[w[i][P[i]]]) P[i]--; if (P[i]) term.push_back(w[i][P[i]]); } for (int t: term) if (!V[t]){ V[t] = 1; M--; for (i=1;i<=N&&V[w[t][i]];i++); if (i <= N) printf("%d %d\n", t, w[t][i]); } } puts(""); } }

M. Variable Shadowing

문제에서 구현하라고 한 부분을 잘 코딩하면 되는 문제다. 언뜻보면 코딩이 복잡할 수 있지만 스택을 이용하면 비교적 쉽게 문제를 해결할 수 있다.

#include <stdio.h> #include <stack> using namespace std; int L, N, D[2501]; char buf[99], A[2501]; stack <int> stk[26]; struct Z{ Z(int y=0, int x=0): y(y), x(x) {} int y, x; } pos[2501]; int main() { int i, j; scanf("%d ", &L); for (i=1;i<=L;i++){ gets(buf); for (j=0;buf[j];j++){ A[++N] = buf[j]; pos[N] = Z(i, j+1); } } int dep = 0; for (i=1;i<=N;i++) if (A[i] != ' '){ if (A[i] == '{'){ dep++; } else if (A[i] == '}'){ for (j=0;j<26;j++) while (!stk[j].empty() && D[stk[j].top()] >= dep) stk[j].pop(); dep--; } else{ int t = A[i] - 'a'; D[i] = dep; if (!stk[t].empty()){ int v = stk[t].top(); printf("%d:%d: warning: shadowed declaration of %c, the shadowed position is %d:%d\n", pos[i].y, pos[i].x, A[i], pos[v].y, pos[v].x); } stk[t].push(i); } } }