Nexon Youth Programming Challenge(NYPC) 2022 본선 풀이

1214 A. 조약돌 순서

처음에 $[1, 2, 3, ..., K]$이 적혀있는 크기 $K$인 배열 $A$가 있다. $i = 1$부터 시작하여 $A_i$와 $A_{i+1}$의 값을 바꾼다. 그리고 $i$를 $1$ 증가시킨다. 만약 $i = K-1$이라면 다음 $i$의 값은 $K$가 아니라, $1$이 된다. 바꾸는 작업을 $N$ 번 하였을 때, 최종 배열의 상태를 구하는 문제다.

 

값을 바꾸는 횟수 $N$이 최대 $10^{18}$로 굉장히 크다. 바꾸는 작업을 $K \times (K-1)$ 번 하면 배열이 원래 상태로 돌아오고, 바꾸는 작업을 $K-1$ 번하면 맨 왼쪽에 있던 값이 맨 오른쪽으로 가는 것을 알 수 있다. 이 점을 이용하여, $O(K)$ 시간복잡도에 해결할 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#include <bits/stdc++.h> using namespace std;   using lld = long long;   int main(){     cin.tie(0)->sync_with_stdio(0);     int K; lld N;     cin >> K >> N; N %= (lld)K*(K-1);     int A[K+1];     for (int i=1;i<=K;i++) A[i] = i;     int S = N/(K-1); N %= K-1;     rotate(A+1, A+1+S, A+K+1);     int i = 1;     while (N--){         swap(A[i], A[i+1]);         i = i+1 < K ? i+1 : 1;     }     for (int i=1;i<=K;i++) cout << A[i] << ' ';     cout << '\n'; }

1214 B. 짝 맞는 문자열

A, B, C로 이루어진 길이 $N$인 문자열이 주어진다. 이 문자열에서 최소 개수의 문자를 제거하여 같은 문자가 두 개씩 반복되게 하는 문제다. 즉, 제거할 문자를 모두 제거한 후, $1$ 이상인 $i$에 대해 $2i-1$ 번째 문자와 $2i$ 번째 문자가 같아야 하며, 이 둘이 같으면 짝이 맞는다고 하자.

 

D[i][j] = 문자열의 길이 $i$인 접두사에서 상태가 $j$일 때 제거하고 남은 문자의 최대 개수라고 정의하자.

상태 $j$는 만약 모든 문자가 짝이 맞는다면 $j = 0$, 맨 마지막 문자를 제외한 모든 문자가 짝이 맞는다면 $j$는 맨 마지막 문자로 정의한다.

 

문제에서 요구하는 답은 D[N][0]이 되며, 이 DP 배열은 시간복잡도 $O(N)$만에 구할 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include <bits/stdc++.h> using namespace std;   int main(){     cin.tie(0)->sync_with_stdio(0);     string S; cin >> S;     int N = size(S);     int D[N+1][4];     for (int i=0;i<=N;i++) for (int j=0;j<4;j++) D[i][j] = -1;     auto put_max = [](auto& a, auto b){         a = max(a, b);     };     D[0][0] = 0;     for (int i=0;i<N;i++){         for (int j=0;j<4;j++) put_max(D[i+1][j], D[i][j]);         if (D[i][0] >= 0) put_max(D[i+1][S[i]-'A'+1], D[i][0]+1);         if (D[i][S[i]-'A'+1] >= 0) put_max(D[i+1][0], D[i][S[i]-'A'+1]+1);     }     cout << D[N][0] << '\n'; }

1214 C / 1519 A. 빙고

$N \times M$ 크기의 빙고판이 있다. 칸에 적힌 수는 알 수 없고, 사회자가 부르는 수도 알 수 없다. $i$ 번째 행을 완성하면 $A_i$점을 획득하며, $j$ 번째 열을 완성하면 $B_j$점을 획득한다. 사회자가 번호를 $K$ 개 부를 때, 얻을 수 있는 최대 점수를 구하는 문제다.

 

$r$ 개의 행을 먼저 완성한다고 하자. 그러면 불러야 하는 수의 개수는 $r \times M$개다. 그 뒤로 열만 완성한다고 했을 때, 완성시킬 수 있는 열의 최대 개수는 $\lfloor\frac{K - r \times M}{N-1}\rfloor$로 정해진다. 획득할 수 있는 점수가 높은 행들과 열들을 우선적으로 완성하는 것이 제일 좋다. $0$ 이상 $N$ 미만인 모든 $r$에 대해 완성시킬 수 있는 열의 개수를 구하고, 점수를 계산하여, 그중 가장 높은 점수를 구하여 문제를 해결할 수 있다. 단, $K = N \times M$인 경우에 대한 예외 처리가 필요하다. 시간복잡도는 $O(N+M)$이다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include <bits/stdc++.h> using namespace std;   using lld = long long;   int main(){     cin.tie(0)->sync_with_stdio(0);     int N, M; lld K; cin >> N >> M >> K;     int A[N+1], B[M+1];     for (int i=1;i<=N;i++) cin >> A[i];     for (int i=1;i<=M;i++) cin >> B[i];     sort(A+1, A+N+1, greater<int>());     sort(B+1, B+M+1, greater<int>());       lld P[N+1]{}, Q[M+1]{};     for (int i=1;i<=N;i++) P[i] = P[i-1]+A[i];     for (int i=1;i<=M;i++) Q[i] = Q[i-1]+B[i];       if (K == (lld)N*M){         lld ans = 0;         for (int i=1;i<=N;i++) ans += A[i];         for (int i=1;i<=M;i++) ans += B[i];         cout << ans << '\n';         return 0;     }       lld ans = 0;     for (int rows=0;rows<N;rows++){         if ((lld)M*rows > K) break;         int cols = (K-(lld)M*rows) / (N-rows);         ans = max(ans, P[rows]+Q[cols]);     }     cout << ans << '\n'; }

1214 D / 1519 B. 야찌

$1$ 이상 $6$ 이하의 수가 적힌 $N$ 개의 카드가 있는 카드 더미가 있다. 그리고 5장의 종이가 있다. 각 턴마다 카드 더미 위에서 카드 5장을 뽑아 순서대로 종이에 적는다. 그리고 최대 한 번 수를 지울 종이를 고르고, 카드 더미에서 카드를 다시 뽑아 지운 종이 위에 수를 적을 수 있다. 만약, 종이 5장에 적힌 수가 모두 같다면 야찌다. 카드 더미에 대한 정보가 주어졌을 때, 가능한 야찌의 최대 횟수를 구하는 문제다.

 

D[i] = 카드 더미에서 총 $i$ 장의 카드를 뽑았을 때, 할 수 있는 야찌의 최대 횟수라고 정의하자.

 

문제에서 요구하는 답은 $\max(D_i)$이다. 한 턴에 뽑을 수 있는 카드의 최대 개수는 10장이므로, $O(N)$ 시간에 DP를 구현할 수 있다. 다만, $N$의 최대값이 $10^6$이므로, 구현에 따라 시간초과가 날 수도 있다. 아래 첨부된 코드는 비트마스크를 이용한 전처리 작업으로 최대한 상수를 줄였다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

#include <bits/stdc++.h> using namespace std;   int main(){     cin.tie(0)->sync_with_stdio(0);     int N; string S;     cin >> N >> S;     int A[N+1];     for (int i=1;i<=N;i++) A[i] = S[i-1]-'0';     bool can[11][1024]{};     vector<int> info[11][1024];     for (int i=5;i<=10;i++){         for (int msk=0;msk<1<<i;msk++){             auto& _info = info[i][msk];             int arr[i];             for (int j=0;j<i;j++) arr[j] = msk>>j&1;             int cnt = 0;             for (int j=0;j<5;j++) if (arr[j]) cnt++;             int discard = i-5;             for (int j=0;j<5;j++) if (!arr[j] && size(_info) < discard) _info.push_back(j+1);             for (int j=0;j<5;j++) if (arr[j] && size(_info) < discard) _info.push_back(j+1);             cnt = min(cnt, 5-discard);             for (int j=5;j<i;j++) if (arr[j]) cnt++;             if (cnt == 5) can[i][msk] = 1;         }     }     vector<int> D(N+1, -1);     pair<int, int> from[N+1];     D[0] = 0;     for (int i=0;i<N;i++) if (D[i] >= 0){         for (int num=1;num<7;num++){             int msk = 0;             for (int j=1;j<=10;j++){                 if (i+j > N) break;                 if (A[i+j] == num) msk ^= 1<<j-1;                 if (j >= 5){                     if (D[i+j] < D[i]+can[j][msk]){                         D[i+j] = D[i]+can[j][msk];                         from[i+j] = make_pair(j, msk);                     }                 }             }         }     }     int ans = -1, t;     for (int i=1;i<=N;i++) if (ans < D[i]){         ans = D[i];         t = i;     }     vector<vector<int>> path;     while (t > 0){         auto [len, msk] = from[t];         path.push_back(info[len][msk]);         t -= len;     }     reverse(begin(path), end(path));     cout << ans << '\n' << size(path) << '\n';     int turn = 0;     for (auto& arr: path){         cout << "Turn " << ++turn << '\n';         if (arr.empty()) cout << "0\n";         else{             cout << "1\n" << size(arr);             for (int v: arr) cout << ' ' << v;             cout << '\n';         }     } }

1214 E. 삼각

정점 $N$ 개와 양방향 간선 $M$ 개로 이루어진 그래프가 주어진다. 각 간선에는 길이가 있다. 정점 $S$가 주어진다. 정점 $S$에서 시작하여 어떤 정점 $A$로 이동했다가, 다른 정점 $B$로 이동하고, 다시 정점 $S$로 돌아오는 경로 중에 정점 $S$를 중간에 방문하지 않으면서 가장 길이가 짧은 경로를 구하는 문제다.

 

이 문제 풀이의 핵심 아이디어는 서로 인접한 정점 두 개를 정점 $A$와 정점 $B$만 답의 후보로 두어도 문제에서 요구하는 답을 올바르게 구한다는 점이다. 즉, 입력으로 주어진 정점 $S$에서 각 정점으로 가는 최단 거리를 구한 뒤, 정점 $a$와 정점 $b$를 연결하는 길이 $c$인 간선이 있다면, 정점 $S$에서 정점 $a$로 오는 최단 거리 값 + 정점 $S$에서 정점 $b$로 오는 최단 거리 값 + $c$를 구하고, 그중 가장 작은 값을 구하면 정답을 구할 수 있다. 시간복잡도는 $O(N + M \lg N)$이다.

 

문제 풀이와 크게 상관 없는 관찰 중, 답이 되는 싸이클에 포함된 간선의 개수는 최대 $4$ 개라는 것도 증명할 수 있다. 이 점을 이용하여, 서브태스크를 해결할 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include <bits/stdc++.h> using namespace std;   using lld = long long;   constexpr lld inf = 4e18;   int main(){     cin.tie(0)->sync_with_stdio(0);     int N, M, S; cin >> N >> M >> S;     vector<vector<pair<int, int>>> con(N+1);     for (int i=1;i<=M;i++){         int a, b, c; cin >> a >> b >> c;         con[a].emplace_back(b, c);         con[b].emplace_back(a, c);     }     vector<lld> dist(N+1, inf);     priority_queue<pair<lld, int>> pq;     dist[S] = 0; pq.emplace(0, S);     while (!pq.empty()){         auto [d, n] = pq.top(); pq.pop();         if (dist[n] != -d) continue;         for (auto [t, v]: con[n]){             if (dist[t] > dist[n]+v)                 dist[t] = dist[n]+v, pq.emplace(-dist[t], t);         }     }     lld ans = inf;     for (int i=1;i<=N;i++){         for (auto [j, d]: con[i]){             if (i == S || j == S) continue;             ans = min(ans, dist[i]+dist[j]+d);         }     }     cout << ans << '\n'; }

1519 C. 덧셈 프로그램

크기 $N$인 정수 배열 $A$가 있고, $M$ 개의 명령어로 구성된 프로그램이 있다. 명령어는 $A_i$에 $A_j$를 더하는 꼴을 한다. 이 프로그램을 총 $L$ 번 실행하는데, 각 실행마다 배열의 초기값이 다를 수 있다. 각 실행마다 프로그램이 종료되는 시점에서 $A_1$의 값을 구하는 문제다.

 

크기 $N$인 정수 배열 $B$를 생각하자. $B$의 초기값은 $B_1 = 1$이고, 나머지는 $0$이다. 배열 $B$에서 입력으로 주어진 프로그램의 명령어를 반대로 실행한다. 명령어의 순서도 반대가 되어야 하고, $A_i$에 $A_j$를 더하는 명령어가 있다면, $B_j$에 $B_i$를 더하자. 실행 이후의 $B_i$ 값은 주어진 프로그램에서 $A_i$의 초기값이 최종적으로 $A_1$에 몇번 더해졌는지를 나타낸다.

 

이를 이용하여 각 프로그램 실행마다, 프로그램이 종료되는 시점에서 $A_1$의 값을 빠르게 구할 수 있다. 초기값이 $0$이 아닌 $A_i$의 총개수를 $K$라고 했을 때, 시간복잡도는 $O(M+L+K)$이다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

#include <bits/stdc++.h> using namespace std;   using lld = long long;   constexpr int MOD = 1e9 + 7;   int main(){     cin.tie(0)->sync_with_stdio(0);     int N, M, L; cin >> N >> M >> L;     int X[M+1], Y[M+1];     for (int i=1;i<=M;i++) cin >> X[i] >> Y[i];     int A[N+1]{};     A[1] = 1;     for (int i=M;i;i--){         A[Y[i]] += A[X[i]];         if (A[Y[i]] >= MOD)             A[Y[i]] -= MOD;     }     for (int i=1;i<=L;i++){         int n; cin >> n;         int ans = 0;         for (int j=0;j<n;j++){             int a, b; cin >> a >> b;             ans = (ans+(lld)A[a]*b)%MOD;         }         cout << ans << '\n';     } }

1519 D. 적절한 점

$x$ 좌표가 $1$ 이상 $W$ 이하이며, $y$ 좌표가 $1$ 이상 $H$ 이하인 2차원 정수 좌표 공간이 있다. 여기에 $K$ 개의 점 집합이 있다. 그리고 각 집합에 대해 $C_i$ 값이 입력으로 주어진다. 적절한 점이란, 모든 $i$에 대해 점 집합 $i$에서 그 점보다 $x$ 좌표가 같거나 작고, 그 점보다 $y$ 좌표가 같거나 작은 점의 개수가 정확히 $C_i$가 되는 점을 말한다. 이때, 적절한 점의 개수를 구하는 문제다.

 

풀이의 아이디어는 간단하다. 어떤 $x$ 좌표에 대해 적절한 점은 연속된 구간으로 표현된다. 각 점 집합에 대해 독립적으로 적절한 점의 $y$ 좌표 구간을 구하고, 교집합을 구하면 된다.

 

좌표 압축과 자료 구조를 이용하여 빠른 시간복잡도로 구현할 수 있다. 전체 점의 개수를 $N$이라고 했을 때, 풀이의 시간복잡도는 $O(N \lg N)$이다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

#include <bits/stdc++.h> using namespace std;   using lld = long long;   int W, H, K;   int main(){     cin.tie(0)->sync_with_stdio(0);     cin >> W >> H >> K;     vector<tuple<int, int, int>> A;     A.emplace_back(1, 0, 0);     A.emplace_back(W+1, 0, 0);     for (int i=1;i<=K;i++){         int n; cin >> n;         for (int j=0;j<n;j++){             int x, y; cin >> x >> y;             A.emplace_back(x, y, i);         }     }     sort(begin(A), end(A));       struct PointSet{         map<int, int> val = {{1, 0}};         int bound, cnt = 0, pivot = 0, nxt;         void add(int y){             val[y]++;             if (!pivot) pivot = y, nxt = H+1;             if (y <= pivot) cnt++;             auto it = val.find(pivot);             while (cnt > bound && it != val.begin()){                 cnt -= it->second;                 it--;             }             while (cnt < bound){                 auto nxt = it; nxt++;                 if (nxt == val.end() || cnt+nxt->second > bound)                     break;                 cnt += nxt->second;                 it = nxt;             }             pivot = it->first;             it++;             nxt = it == val.end() ? H+1 : it->first;         }     };     PointSet ps[K+1];     for (int i=1;i<=K;i++){         int v; cin >> v;         ps[i].bound = v;     }       priority_queue<pair<int, int>> P, Q;     int S[K+1], E[K+1];     for (int i=1;i<=K;i++){         if (!ps[i].bound) S[i] = 1, E[i] = H+1;         else S[i] = 1, E[i] = 0;         P.emplace(S[i], i);         Q.emplace(-E[i], i);     }     auto update = [&](int i, int s, int e){         if (S[i] == s && E[i] == e) return;         S[i] = s; E[i] = e;         P.emplace(S[i], i);         Q.emplace(-E[i], i);     };     lld ans = 0;     int prv = 0;     for (auto [x, y, i]: A){         if (prv && prv != x){             while (S[P.top().second] != P.top().first) P.pop();             while (E[Q.top().second] != -Q.top().first) Q.pop();             int s = P.top().first;             int e = -Q.top().first;             if (s < e) ans += (lld)(e-s)*(x-prv);         }         prv = x;         if (!i) continue;         ps[i].add(y);         if (ps[i].cnt == ps[i].bound) update(i, ps[i].pivot, ps[i].nxt);         else update(i, 1, 0);     }     cout << ans << '\n'; }

1519 E. 지름길

정점 $N$ 개와 양방향 간선 $M$ 개로 이루어진 그래프가 주어진다. 각 간선에는 길이가 있다. 정점 $S$와 정점 $T$가 주어진다. 정점 $S$에서 정점 $i$로 가는 최단 거리와 정점 $i$에서 정점 $T$로 가는 최단 거리가 유지되도록 최소 개수의 간선만 남기는 문제다.

 

이 문제 풀이에 대한 접근은 최단 거리 트리(Shortest-path tree)를 생각해보면 된다. 정점 $S$에 대한 최단 거리 트리와 정점 $T$에 대한 최단 거리 트리가 원래 그래프와 동일하도록 최소 개수의 간선만 남기면 된다. 이 점을 생각해보면, 문제에서 요구하는 답은 최대 $2(N-1)$이라는 것을 알 수 있다.

 

최소 개수의 간선을 남겨야하므로, 최대한 많은 간선이 정점 $S$에 대한 최단 거리 트리와 정점 $T$에 대한 최단 거리 트리에 동시에 존재하는 것이 유리하다. 두 최단 거리 트리에 모두 존재할 수 있는 간선 후보들을 구한 뒤, 그 후보 중에서 동시에 존재할 수 있는 간선의 최대 개수를 구하면 된다. 동시에 존재할 수 있는 간선의 최대 개수는 이분 그래프에서 최대 매칭을 통해 구할 수 있다. 최대 매칭의 개수가 $F$라고 하면, 답은 $2(N-1) - F$가 된다. 이분 매칭은 Hopcroft-Karp 알고리즘을 구하는 것이 가장 빠르며 이 문제를 해결하는 전체 시간복잡도는 $O(N + M \sqrt{N})$이다.

 

풀이의 원리를 이해했다면, 남겨야하는 간선을 구하는 것은 간단하다. 첨부된 코드를 참고하자.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

#include <bits/stdc++.h> using namespace std;   using lld = long long;   constexpr lld inf = 1e18;   int main(){     cin.tie(0)->sync_with_stdio(0);     int N, M, S, T; cin >> N >> M >> S >> T;     vector<pair<int, int>> con[N+1];     tuple<int, int, int> edges[M+1];     for (int i=1;i<=M;i++){         int a, b, c; cin >> a >> b >> c;         con[a].emplace_back(b, c);         con[b].emplace_back(a, c);         edges[i] = {a, b, c};     }     lld D[2][N+1];     auto dijkstra = [&](int st, lld dist[]){         fill(dist+1, dist+N+1, inf);         priority_queue<pair<lld, int>> que;         dist[st] = 0; que.emplace(0, st);         while (!que.empty()){             auto [d, n] = que.top(); que.pop();             if (dist[n] != -d) continue;             for (auto [t, v]: con[n]){                 if (dist[t] > dist[n]+v){                     dist[t] = dist[n]+v;                     que.emplace(-dist[t], t);                 }             }         }     };     dijkstra(S, D[0]);     dijkstra(T, D[1]);       int selectedA[N+1]{}, selectedB[N+1]{};     vector<pair<int, int>> bcon[N+1];     for (int i=1;i<=M;i++){         auto [a, b, c] = edges[i];         int p = 0, q = 0;         if (D[0][a]-D[0][b] == c) p = a;         if (D[0][b]-D[0][a] == c) p = b;         if (D[1][a]-D[1][b] == c) q = a;         if (D[1][b]-D[1][a] == c) q = b;         if (p && q) bcon[p].emplace_back(q, i);         if (p) selectedA[p] = i;         if (q) selectedB[q] = i;     }       bool used[N+1]{}; int match[N+1]{}, matchE[N+1]{}, dist[N+1];     auto bfs = [&](){         fill(dist+1, dist+N+1, 1e9);         queue<int> que;         for (int i=1;i<=N;i++) if (!used[i]) que.push(i);         while (!que.empty()){             int q = que.front(); que.pop();             for (auto [t, _]: bcon[q]){                 if (int m = match[t]; m && dist[m] == 1e9)                     dist[m] = dist[q]+1, que.push(m);             }         }     };     function<bool(int)> dfs = [&](int n){         for (auto [t, e]: bcon[n]){             if (int m = match[t]; !m || dist[m] == dist[n]+1 && dfs(m)){                 used[n] = 1;                 match[t] = n;                 matchE[t] = e;                 return 1;             }         }         dist[n] = 1e9;         return 0;     };     int matched = 0;     for (;;){         bfs();         int flow = 0;         for (int i=1;i<=N;i++) if (!used[i] && dfs(i)) flow++;         if (!flow) break;         matched += flow;     }       int K = 2*(N-1)-matched;     cout << K << '\n';       for (int i=1;i<=N;i++) if (match[i])         selectedA[match[i]] = selectedB[i] = matchE[i];     bool edge_used[M+1]{};     for (int i=1;i<=N;i++) edge_used[selectedA[i]] = edge_used[selectedB[i]] = 1;     for (int i=1;i<=M;i++) if (edge_used[i]) cout << i << ' ';     cout << '\n'; }