2017년 대학생 프로그래밍 경시대회 풀이

문제 링크

D. Happy Number

문제에 적혀 있는 함수 $f$가 있다. $f(f(f(...f(n))))$을 했을 때, 1이 되는지를 구하는 문제다.

입력으로 주어지는 수는 최대 1,000,000,000인데, 큰 수가 주어진다하더라도 $f(n)$의 결과값은 작다. 때문에 이 문제는 함수 $f$를 구현하고 결과값이 1이 되는지만 확인하는 간단한 문제가 된다.

#include <bits/stdc++.h> using namespace std; int N; int main() { set <int> vis; scanf("%d", &N); while (N > 1){ if (vis.count(N)){ puts("UNHAPPY"); return 0; } vis.insert(N); int nxt = 0; for (int v=N;v;v/=10) nxt += (v%10)*(v%10); N = nxt; } puts("HAPPY"); }

C. Game Map

N개의 정점과 M개의 간선으로 이루어진 무방향성 그래프가 주어진다. 임의의 정점에서 시작하여 방문하는 정점의 차수(degree)가 증가하도록 이동하는 경로 중에서 가장 긴 경로의 길이를 구하는 문제다.

아래와 같은 DP배열을 생각하자.

D[i] = 임의의 시작점에서 정점 i까지 오는 경로 중에서 가장 긴 경로의 길이.

차수가 낮은 정점부터 차례대로 DP 값을 뿌려주거나, DP 값을 계산하면 올바르게 DP 값을 구할 수 있다.

정점을 차수 순서대로 정렬해야하므로, 시간복잡도는 $O(N \lg N + M)$이 된다.

#include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define pb push_back int N, M; int D[MAXN], deg[MAXN]; int order[MAXN]; vector <int> con[MAXN]; int main() { scanf("%d%d", &N, &M); for (int i=1;i<=M;i++){ int a, b; scanf("%d%d", &a, &b); deg[++a]++; deg[++b]++; con[a].pb(b); con[b].pb(a); } for (int i=1;i<=N;i++) order[i] = i; sort(order+1, order+N+1, [](const int &a, const int &b){ return deg[a] < deg[b]; }); for (int i=1;i<=N;i++) D[i] = 1; for (int i=1;i<=N;i++){ int n = order[i]; for (int t: con[n]) if (deg[n] < deg[t]) D[t] = max(D[t], D[n]+1); } int ans = 0; for (int i=1;i<=N;i++) ans = max(ans, D[i]); printf("%d\n", ans); }

F. Philosopher's Walk

문제에서 주어진 그림처럼 재귀적으로 문양을 그린다. 문양의 크기 n과 순서 m이 주어졌을 때, 문양을 그리면서 m번째로 방문한 칸의 좌표를 구하는 문제다.

이 문제는 문양을 직접 2차원 배열에 그리지 않되, 재귀함수를 잘 짜서 문양을 그리는 로직을 작성하면 해결할 수 있다. 재귀함수의 구성이나, 자세한 테크닉은 코드를 참고하자. 시간복잡도는 $O(\lg N)$이다.

#include <bits/stdc++.h> using namespace std; int N, M; void get(int n, int m, int sx=1, int sy=1, vector <int> order={0, 2, 3, 1}) { int h = n/2, k = h*h; if (m < 1 || m > n*n) return; if (n == 1){ printf("%d %d\n", sx, sy); return; } get(h, m, sx+(order[0]&1)*h, sy+(order[0]&2)/2*h, {order[0], order[3], order[2], order[1]}); get(h, m-k, sx+(order[1]&1)*h, sy+(order[1]&2)/2*h, order); get(h, m-k*2, sx+(order[2]&1)*h, sy+(order[2]&2)/2*h, order); get(h, m-k*3, sx+(order[3]&1)*h, sy+(order[3]&2)/2*h, {order[2], order[1], order[0], order[3]}); } int main() { scanf("%d%d", &N, &M); get(N, M); }

H. Rock Paper Scissors

길이가 N인 가위바위보 문자열과 길이가 M인 가위바위보 문자열이 주어진다. 길이가 M인 가위바위보 문자열을 원하는 시점에서 시작하여, 최대한 많은 승수를 쌓는 문제다. 길이가 M인 가위바위보 문자열이 오른쪽으로 삐져나가도 괜찮다.

길이가 N인 가위바위보 문자열의 각 문자를 이기는 문자로 바꾼다. 즉, 'R'은 'P'로, 'P'는 'S'로, 'S'는 'R'로 바꾼다. 그러면 이제 문제는 길이가 N인 전체 문자열이 있고, 길이가 M인 패턴 문자열이 있고, 패턴과 가장 많은 문자가 겹치는 순간을 찾는 문제가 된다.

문자의 종류수가 3 종류라는 것을 감안했을 때, FFT를 이용하여 각 문자 종류마다 패턴이 어느 위치에 갔을 때 겹치는 칸의 수를 구할 수 있다. 이를 합산하면 문제가 해결된다. 시간복잡도는 $O(N \lg N)$이다.

#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() typedef complex<double> base; 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)); } int N, M; int code[128]; char A[MAXN], B[MAXN]; int main() { code['R'] = 0, code['P'] = 1, code['S'] = 2; scanf("%d%d%s%s", &N, &M, A, B); vector <int> total(N+M, 0); for (int i=0;i<N;i++) A[i] = (code[A[i]]+1)%3; for (int i=0;i<M;i++) B[i] = code[B[i]]; for (int i=0;i<3;i++){ vector <int> a(N+M, 0), b(M, 0), res; for (int j=0;j<N;j++) a[j] = (A[j] == i); for (int j=0;j<M;j++) b[j] = (B[M-j-1] == i); multiply(a, b, res); for (int j=0;j<N+M;j++) total[j] += res[j]; } int ans = 0; for (int i=M-1;i<N+M;i++) ans = max(ans, total[i]); printf("%d\n", ans); }

K. Untangling Chain

원점에서 시작하여 임의의 거리를 이동하고 90도 회전을 반복한다. 회전 방향들이 주어졌을 때, 이동 거리를 잘 정해 경로를 선으로 그렸을 때 교차하지 않도록하는 문제다.

여러 가지 방법이 가능한데, 알고 있는 방법 중 가장 간단한 방법을 코드로 첨부한다. 모든 입력 데이터에 대해 답은 존재하며, 방법은 귀납법으로 증명 가능하다. 증명 방향은 이동이 진행되면 될수록 앞으로 움직이는 정사각형 영역의 이 한 단계씩 줄어들고 그 영역을 벗어나지 않는다. 시간복잡도는 $O(N)$이다.

#include <bits/stdc++.h> using namespace std; #define MAXN 10004 int N; int A[MAXN]; int main() { scanf("%d", &N); for (int i=1;i<=N;i++) scanf("%*d%d", A+i); for (int i=1;i<=N;i++) printf("%d ", A[i] == A[i+1] ? N-i+1 : 1); puts(""); }

B. Connect3

두 사람이 4x4 크기의 격자판에서 번갈아가면서 3목을 진행한다. 단, 돌을 놓을 때는 맨 밑바닥에 놓거나, 놓으려는 자리 밑에 돌이 있어야지만 놓을 수 있다. 이 때 후공이 특정 위치에 돌을 놓는 순간 이기게 되는 경우의 수를 구하는 문제다.

기본적으로 돌을 놓기 위해서는 맨 밑바닥에 놓거나 놓으려는 자리 밑에 돌이 있어야한다. 때문에 가능한 경우의 수를 간략하게 계산하면, 최대 $(2^5-1)^4 = 923,521$가지 밖에 되지 않는다. 그리고 4x4 게임판 상태 표현은 $0$이상 $3^{16} = 43,046,721$미만의 정수 하나로 할 수 있다. 이러한 수를 살펴보면 이 문제는 간단히 brute force하여 해결할 수 있는 문제라는 것을 알 수 있다.

#include <bits/stdc++.h> using namespace std; const int ALL = 43046721; // 3^16 int TP[16] = {1}; int S, Y, X, ans; char vis[ALL], chkvis[ALL], cache[ALL]; inline int to_num(int y, int x){ return (y-1)*4+(x-1); } const int dy[]={0, 1, 1, 1}, dx[]={1, 1, 0, -1}; inline int check(int now) { char &ret = cache[now]; if (chkvis[now]) return ret; chkvis[now] = 1; int A[5][5] = {0, }; for (int i=1;i<=4;i++) for (int j=1;j<=4;j++){ int t = to_num(i, j); A[i][j] = now / TP[t] % 3; } for (int i=1;i<=4;i++) for (int j=1;j<=4;j++) if (A[i][j]){ for (int d=0;d<4;d++){ int y = i, x = j, cnt = 0; for (;;){ if (y > 4 || x < 1 || x > 4 || A[i][j] != A[y][x]) break; cnt++; y += dy[d], x += dx[d]; } if (cnt > 2) return ret = A[i][j]; } } return ret = 0; } void dfs(int now, int turn) { if (vis[now]) return; vis[now] = 1; int A[5][5] = {0, }; for (int i=1;i<=4;i++) for (int j=1;j<=4;j++){ int t = to_num(i, j); A[i][j] = now / TP[t] % 3; } for (int j=1;j<=4;j++){ for (int i=1;i<=4;i++) if (!A[i][j]){ int t = to_num(i, j); int nxt = now + TP[t] * turn; int w = check(nxt); if (w){ if (w == 2 && i == Y && j == X) ans++; break; } dfs(nxt, 3-turn); break; } } } int main() { for (int i=1;i<16;i++) TP[i] = TP[i-1]*3; scanf("%d%d%d", &S, &Y, &X); dfs(TP[to_num(1, S)], 2); printf("%d\n", ans); }

G. Rectilinear Regions

오른쪽으로 내려가거나, 오른쪽으로 올라가는 '계단' 모양의 선 L과 U가 주어진다. 두 선에 의해 생기는 닫힌 직사각형 영역 중 선 L의 부분이 밑에 있고, 선 U의 부분이 위에 있는 직사각형 영역의 갯수와 면적 합을 구하는 문제다. 주어지는 꼭지점들의 X좌표는 서로 다르고, Y좌표 또한 서로 다르다.

각 선의 꼭지점 부분이 X좌표 순서대로 주어진다. 이를 이용해 plane sweeping을 진행하면 어렵지 않게 해결할 수 있다. 코드의 모양은 Merge Sort의 merge 과정과 유사하다. 시간복잡도는 $O(N)$이다.

#include <bits/stdc++.h> using namespace std; #define MAXN 25003 typedef long long lld; int N, M; int X1[MAXN], Y1[MAXN], X2[MAXN], Y2[MAXN]; int C; lld A; int main() { scanf("%d%d", &N, &M); scanf("%d", Y1); for (int i=1;i<=N;i++) scanf("%d%d", X1+i, Y1+i); scanf("%d", Y2); for (int i=1;i<=M;i++) scanf("%d%d", X2+i, Y2+i); lld tmp = 0; bool has_closed = Y1[0] > Y2[0]; for (int i=1,j=1,prv=-1;i<=N||j<=M;){ if (j > M || i <= N && X1[i] < X2[j]){ if (prv >= 0 && Y1[i-1] < Y2[j-1]) tmp += (lld)(Y2[j-1]-Y1[i-1])*(X1[i]-prv); if (Y1[i] > Y2[j-1]){ if (has_closed && tmp) A += tmp, C++; tmp = 0; has_closed = 1; } prv = X1[i++]; }else{ if (prv >= 0 && Y1[i-1] < Y2[j-1]) tmp += (lld)(Y2[j-1]-Y1[i-1])*(X2[j]-prv); if (Y1[i-1] > Y2[j]){ if (has_closed && tmp) A += tmp, C++; tmp = 0; has_closed = 1; } prv = X2[j++]; } } printf("%d %lld\n", C, A); }

I. Slot Machines

길이가 N인 수열이 주어진다. 이 수열의 왼쪽 $k$개의 원소를 제외하면 왼쪽에서부터 주기 $p$를 갖는다. 이 때, $k+p$가 최소가 되는 $k$, $p$를 구하는 문제다. 만약 $k+p$가 최소인 경우가 여러가지라면, $p$가 최소가 되는 경우를 찾으면 된다. 단, $p > 0$이다.

편의상 설명에서는 수열 대신 문자열을 사용하겠다. 수열의 수가 하나의 문자가 된 것일 뿐 달라지는 것은 전혀 없다.

우선, 입력으로 들어온 수열을 좌우반전시키고 KMP 알고리즘을 이용해서 실패함수 $f$의 값을 구하자.

입력으로 문자열 "EDBACBACBA"가 주어졌고, 이를 좌우반전시킨 문자열 "ABCABCABDE"가 있다고 하자. $8$번째 문자의 실패함수 $f(8)=5$라는 것은 4번째 문자와 1번째 문자가 같고, 5번째 문자와 2번째 문자가 같고, ..., 8번째 문자와 5번째 문자가 같다는 것을 의미한다. 이는 입력으로 들어온 문자열의 $k$, $p$ 값 후보로 $k=2$, $p=3$이 가능하다는 것이고, 또한 $k=2$일 때 가장 작은 $p$가 됨도 알 수 있다. 이 경우 $k+p = 10 - f(8) = 5$라는 것이고 문제에서 $k+p$ 값을 최소화하라고 하였으니, $N - f(i)$ 중 제일 작은 값을 찾으면 된다. 시간복잡도는 $O(N)$이다.

#include <bits/stdc++.h> using namespace std; #define MAXN 1000006 int N; int A[MAXN], P[MAXN]; int main() { scanf("%d", &N); for (int i=N;i;i--) scanf("%d", A+i); int ans = N, p = 1; for (int i=2,k=0;i<=N;i++){ while (k && A[k+1] != A[i]) k = P[k]; if (A[k+1] == A[i]) k++; P[i] = k; if (ans > N-P[i]) ans = N-P[i], p = i-P[i]; } printf("%d %d\n", ans-p, p); }

L. Vacation Plans

최대 3명의 사람이 서로 다른 방향성 그래프에 살고 있다. 각 사람은 첫 날 자신이 속한 연결그래프의 1번 도시에 살고 있다. 각 사람은 날이 지날 때마다, 자신이 있는 정점의 호텔에 머물 것인지, 아니면 인접한 다른 정점으로 이동할 것인지 정할 수 있다. 호텔에 머무는데 특정 비용이 들고, 간선을 통해 이동할 때 특정 비용이 있다. 각 그래프에는 한 개의 공항이 있는데 세 사람이 모두 같은날 공항에 도착하기 위한 비용합의 최소값을 구하는 문제다.

편의상 항상 3명의 사람이 있다고 하자. 만약 입력으로 들어온 사람의 수가 2명인 경우에는, 가상의 3번째 사람과 그래프를 만들어, 3번째 그래프의 정점 개수는 1개이며, 공항은 1번 정점에 있고, 1번 정점의 호텔 비용이 0이라고 생각하면 된다. 또한 호텔에 머무는 것을 self edge로 표현할 수 있다. 그러면 호텔에 머무는 선택지를 self edge를 통해 간선 이동을 하는 것으로 볼 수 있어서 좀 더 문제가 단순해진다.

사람들에게 번호를 0번부터 매기자. 그리고 $i$번 사람이 있는 그래프의 정점 개수를 $N_i$, 간선 개수를 $M_i$라고 하자.

[Dijkstra 풀이]

사람들이 각 날 동시에 움직이는 것이 아니라, 0번 사람부터 2번 사람까지 차례대로 움직인다고 생각하자. 이제 아래와 같은 DP 배열을 생각해보자.

D[i][j][k][l] = 어떤 날, 0번 사람은 i번 정점에, 1번 사람은 j번 정점에, 2번 사람은 k번 정점에 있고, 이제 l번 사람이 이동할 차례일 때 여태까지 지불한 비용합의 최소값

DP 배열의 상태 개수 $V = N_0 \times N_1 \times N_2 \times 3$이다. 현재 상태에서 다음 상태로 이동 가능한 경우 방향성 간선으로 표시했을 때 간선의 수 $E = (N_0N_1N_2(M_0+M_1+M_2))$이다. 이제 DP 배열의 내용을 Dijkstra 알고리즘을 이용하여 계산하면 시간복잡도 $O((E+V) \lg V)$에 해결할 수 있다. 실행시간은 1초 시간제한에 약 0.8초 정도 나온다.

#include <bits/stdc++.h> using namespace std; #define pb push_back #define sz(v) ((int)(v).size()) typedef long long lld; int P, N[3], T[3]; lld D[51][51][51][3]; vector <int> con[3][51], conv[3][51]; int main() { scanf("%d", &P); for (int i=0;i<P;i++){ int m; scanf("%d%d", N+i, &m); for (int j=1;j<=N[i];j++){ int v; scanf("%d", &v); con[i][j].pb(j); conv[i][j].pb(v); } while (m--){ int a, b, c; scanf("%d%d%d", &a, &b, &c); con[i][a].pb(b); conv[i][a].pb(c); } scanf("%d", T+i); } for (int i=P;i<3;i++){ con[i][1].pb(1); conv[i][1].pb(0); N[i] = T[i] = 1; } for (int i=1;i<=N[0];i++) for (int j=1;j<=N[1];j++) for (int k=1;k<=N[2];k++) for (int l=0;l<3;l++) D[i][j][k][l] = 1e18; struct Z { int a, b, c, d; lld v; bool operator < (const Z &ot)const{ return v > ot.v; } }; priority_queue <Z> que; D[1][1][1][0] = 0; que.push({1, 1, 1, 0, 0}); while (!que.empty()){ Z q = que.top(); que.pop(); int t = q.d; vector <int> a = {q.a, q.b, q.c}; for (int i=sz(con[t][a[t]]);i--;){ auto b = a; b[t] = con[t][a[t]][i]; int v = conv[t][a[t]][i]; lld &d = D[b[0]][b[1]][b[2]][(q.d+1)%3]; if (d > q.v+v) d = q.v+v, que.push({b[0], b[1], b[2], (q.d+1)%3, q.v+v}); } } printf("%lld\n", D[T[0]][T[1]][T[2]][0]); }

[Bellman Ford 풀이]

정답이되는 날까지 걸리는 최대 기간은 $X = N_0 \times N_1 \times N_2$보다 작다. 이를 이용하여, 아래와 같은 DP 배열을 생각해보자.

D[x][i][j] = x일째 i번 사람이 j번 정점에 있을 때 최소 비용

0이상 $X$미만인 모든 x에 대해 D[x][0][T[0]]+D[x][1][T[1]]+D[x][2][T[2]]의 최소값을 구하면 답이 된다. 이 때, T[i]는 i번 사람이 있는 그래프에서 공항의 위치다. 실제로 코딩할 때, 3차원 배열이 아닌 toggling 기법을 이용하여 2차원 배열로 구현할 수 있다. 시간복잡도는 $O(N_0N_1N_2(M_0+M_1+M_2))$이며, 실행시간은 1초 시간제한에 약 0.2초 정도 나온다.

#include <bits/stdc++.h> using namespace std; #define pb push_back #define sz(v) ((int)(v).size()) typedef long long lld; int P, N[3], T[3]; lld D[3][51]; struct EDGE { int a, b, c; }; vector <EDGE> E[3]; int main() { scanf("%d", &P); for (int i=0;i<P;i++){ int m; scanf("%d%d", N+i, &m); for (int j=1;j<=N[i];j++){ int v; scanf("%d", &v); E[i].pb({j, j, v}); } while (m--){ int a, b, c; scanf("%d%d%d", &a, &b, &c); E[i].pb({a, b, c}); } scanf("%d", T+i); } for (int i=P;i<3;i++){ E[i].pb({1, 1, 0}); N[i] = T[i] = 1; } for (int i=0;i<3;i++) for (int j=2;j<=N[i];j++) D[i][j] = 1e18; const int MAX_MOVE = N[0] * N[1] * N[2]; lld ans = 1e18; for (int i=0;i<MAX_MOVE;i++){ lld sum = 0; for (int j=0;j<3;j++) sum += D[j][T[j]]; if (ans > sum) ans = sum; for (int j=0;j<3;j++){ vector <lld> t(N[j]+1, 1e18); for (const auto &e: E[j]) t[e.b] = min(t[e.b], D[j][e.a]+e.c); for (int k=1;k<=N[j];k++) D[j][k] = t[k]; } } printf("%lld\n", ans); }

E. How Many to Be Happy

N개의 정점과 M개의 간선으로 이루어진 그래프가 주어진다. 각 간선에 대해 자신을 포함한 MST가 존재하기 위해 제거해야되는 간선의 최소 개수의 합을 구하는 문제다.

a번 정점과 b번 정점을 연결하는 가중치 c인 간선이 있다고 하자. 이 간선을 포함한 MST가 존재하기 위한 필요충분조건은 a번 정점과 b번 정점을 연결하는 경로 중 가중치가 c보다 작은 간선으로만 이루어진 경로가 없는 것이다. 이 때, 제거해야하는 간선의 최소 개수는 가중치가 c보다 작은 간선들만 있는 새로운 그래프를 만들고, 그 그래프에서 a번 정점과 b번 정점 사이의 minimum cut이 된다.

Minimum cut은 maximum flow로 구할 수 있으며, maximum flow를 구하는 여러 알고리즘이 존재한다. 대부분의 maximum flow 알고리즘은 시간복잡도 상으로는 시간초과가 나올 것 같아보이지만, 이 문제에서는 간단한 Ford-Fulkerson 방법으로도 빠른 시간안에 통과한다. 첨부한 코드는 내가 알고 있는 실험적으로 제일 빠른 maximum flow 코드다.

#include <bits/stdc++.h> using namespace std; #define MAXN 109 #define MAXM 509 #define MAXE 1004 #define pb push_back int N, M; struct EDGE { int a, b, c; } edge[MAXM]; int E; int to[MAXE], flow[MAXE]; vector <int> cone[MAXN]; int dist[MAXN], cnt[MAXN]; void add_edge(int a, int b) { cone[a].pb(E); to[E] = b; flow[E++] = 1; cone[b].pb(E); to[E] = a; flow[E++] = 1; } void bfs(int b) { for (int i=1;i<=N;i++) dist[i] = N; queue <int> que; dist[b] = 0; que.push(b); while (!que.empty()){ int q = que.front(); que.pop(); for (int e: cone[q]){ int t = to[e], f = flow[e^1]; if (f && dist[t] > dist[q]+1) dist[t] = dist[q]+1, que.push(t); } } for (int i=0;i<=N;i++) cnt[i] = 0; for (int i=1;i<=N;i++) cnt[dist[i]]++; } vector <int> pathe; int dfs(int n, int dest) { if (n == dest) return 1; for (int e: cone[n]){ int t = to[e], f = flow[e]; if (!f || dist[t]+1 != dist[n]) continue; pathe.pb(e); int k = dfs(t, dest); if (k) return k; pathe.pop_back(); } int tmp = dist[n]; dist[n] = N; for (int e: cone[n]){ int t = to[e], f = flow[e]; if (f && dist[n] > dist[t]+1) dist[n] = dist[t]+1; } cnt[dist[n]]++; if (!--cnt[tmp]) return -1; return 0; } int mincut(int a, int b, int c) { int ret = 0; E = 0; for (int i=1;i<=N;i++) cone[i].clear(); for (int i=1;edge[i].c<c;i++) add_edge(edge[i].a, edge[i].b); bfs(b); while (dist[a] < N){ pathe.clear(); int k = dfs(a, b); if (k < 0) break; if (!k) continue; for (int e: pathe) flow[e]--, flow[e^1]++; ret++; } return ret; } int main() { scanf("%d%d", &N, &M); for (int i=1;i<=M;i++){ int a, b, c; scanf("%d%d%d", &a, &b, &c); edge[i] = {a, b, c}; } sort(edge+1, edge+M+1, [](const EDGE &a, const EDGE &b){ return a.c < b.c; }); int ans = 0; for (int i=1;i<=M;i++) ans += mincut(edge[i].a, edge[i].b, edge[i].c); printf("%d\n", ans); }

A. Broadcast Stations

N개의 정점으로 이루어진 트리가 주어진다. 정점에는 기지국을 놓을 수 있는데, 세기가 s인 기지국을 놓게 되면 자기 자신을 포함하여 거리 s이내의 정점에 신호가 간다. 적당히 기지국을 배치하여, 모든 정점이 신호를 수신하면서 세기 s의 합이 최소가 되도록 하는 문제다.

[제곱시간 풀이]

우선 트리를 1번 정점이 루트인 루트가 있는 트리로 만들자. 그리고 다음과 같은 두 개의 DP 배열을 생각하자.

D[i][j] = i가 루트인 서브트리에서 i번 정점에서 남는 신호 세기가 j인 경우 세기 합의 최소값

E[i][j] = i가 루트인 서브트리에서 i번 정점에서부터 j 단계 동안 신호를 수신하지 못한 정점이 있는 경우 세기 합의 최소값

이 때 DP 값을 계산하는 것은 비교적 어렵지 않게 가능하다. 이 문제에서 허들인 것은 언뜻보면 시간복잡도가 $O(N^3)$이 되어서 시간초과가 날 것 같다는 부분이다. 시간복잡도를 정확히 계산해보면, 각 정점 i에 대해 필요한 시간복잡도는 $O(\deg(i) \times N)$이 되고, 모든 i에 대해 이를 더하면 총 시간복잡도는 $O(N^2)$이 된다.

#include <bits/stdc++.h> using namespace std; #define MAXN 5003 #define pb push_back int N; int D[MAXN][MAXN], E[MAXN][MAXN]; vector <int> con[MAXN]; void dfs(int n, int from) { vector <int> sum(N+1, 0); // Pre-compute for (int t: con[n]) if (t != from){ dfs(t, n); for (int i=0;i<=N;i++) sum[i] += E[t][i]; } // Initialize for (int i=0;i<=N;i++) D[n][i] = E[n][i] = N; // Calculation for (int t: con[n]) if (t != from){ for (int i=1;i<=N;i++) D[n][i-1] = min(D[n][i-1], D[t][i]+(sum[i-1]-E[t][i-1])); } for (int i=1;i<=N;i++) E[n][i] = min(E[n][i], sum[i-1]); for (int i=1;i<=N;i++) D[n][i] = min(D[n][i], sum[i]+i); // Monotonize for (int i=N;i--;) D[n][i] = min(D[n][i], D[n][i+1]); E[n][0] = D[n][0]; for (int i=1;i<=N;i++) E[n][i] = min(E[n][i], E[n][i-1]); } int main() { scanf("%d", &N); for (int i=1;i<N;i++){ int a, b; scanf("%d%d", &a, &b); con[a].pb(b); con[b].pb(a); } dfs(1, 0); printf("%d\n", D[1][0]); }

[선형시간 풀이]

선형시간 풀이에 접근하기 위해서는 다음과 같은 lemma가 필요하다.

lemma) 트리에서 임의의 지름을 구하고, 그 지름 위에 있는 정점들에만 기지국을 놓아도 최적해를 구할 수 있다.

풀이 준비 중.

J. Strongly Matchable

풀이 준비 중.