Nexon Youth Programming Challenge(NYPC) 2022 Round 2-B 풀이

1. 비트문자열

특정 규칙으로 만들어지는 길이 $2^i$인 이진문자열 $S_i$가 있다. 구간 $[s, e]$가 있을 때, $S_i$의 $s$ 번째 문자부터 $e$ 번째 문자까지 문자 중에서 1의 개수를 구하는 문제다. 단, 하나의 입력 파일에 최대 20만 개의 테스트 케이스가 들어올 수 있어서 상당히 빠른 시간 안에 문제를 해결해야 한다.

 

문제 설명에 적힌 규칙과 다른 방식으로 $S_i$를 설명할 수 있다. $S_0$는 "0"이며, $1$ 이상인 $i$에 대해 $S_i$는 $S_{i-1}$에서 0/1을 뒤집은 것과 $S_{i-1}$을 이어 붙인 문자열이 된다. 즉, $S_1$은 "10"이며, $S_2$는 "10"에서 0/1을 뒤집은 "01"에 "10"을 이어 붙인 "0110"이 된다. $S_3$은 "0110"에서 0/1을 뒤집은 "1001"에 "0110"을 이어붙인 "10010110"이 된다.

 

$S_i$는 여러 특징이 있는데, 이 문제를 풀면서 필요한 특징은 두 가지이다. 하나는 $k > 0$인 정수 $k$에 대해 문자열 $S_i$의 $2k$ 번째 문자와 $2k-1$ 번째 문자는 항상 다르다는 특징이다. 이 특징을 이용하면 $s$ 번째 문자와 $e$ 번째 문자만 알면, 구간 $[s, e]$에 있는 1의 개수를 알 수 있다.

 

그러면 어떤 $x$에 대해, $S_i$에서 $x$ 번째 문자를 빠른 시간 안에 구하면 이 문제를 해결할 수 있다. 어떤 $x$에 대해 $S_i$의 $x$ 번째 문자와 $S_{i+1}$의 $x$ 번째 문자는 항상 다르다는 점을 이용하면 된다. 그러면 $i > 60$인 경우, $S_{60}$의 $x$ 번째 문자를 구하고, $i$의 홀짝성을 이용해서 $S_i$의 $x$ 번째 문자도 구할 수 있다.

 

말로 설명해보니 방법이 좀 복잡해 보이는데, 실제로는 간단하다. 아래 코드를 참고하자.

?

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;   bool get(lld K, lld x){     if (K == 0) return 0;     if (K > 60){         bool ret = get(60, x);         if (K%2 == 1) ret ^= 1;         return ret;     }     lld n = 1LL << K, m = n/2;     if (x > m) return get(K-1, x-m);     return get(K-1, x)^1; }   int main(){     cin.tie(0)->sync_with_stdio(0);     int T; cin >> T;     while (T--){         lld K, s, e; cin >> K >> s >> e;         lld ans = 0;         if (e%2 == 1) ans += get(K, e--);         if (s%2 == 0) ans += get(K, s++);         ans += (e-s+1)/2;         cout << ans << '\n';     } }

2. 정수 놀이

쿼리가 $Q$ 개 주어진다. 각 쿼리에 대해 양의 정수 $A$에 최소 몇 번의 연산을 적용하여 양의 정수 $B$를 만들 수 있는지를 구해야 한다. 적용할 수 있는 연산은 1) 정수에 1을 더한다, 2) 정수에 1을 뺀다, 3) 정수를 제곱한다, 4) 정수가 제곱 수라면 제곱근을 한다. 단, 연산 이후에도 양의 정수가 되는 경우에만 연산을 할 수 있다.

 

문제에서 주어진 네 종류의 연산은 서로 대칭이다. 따라서 문제를 양의 정수 $A$와 $B$가 주어졌을 때, 두 정수에 최소 횟수의 연산을 적용하여 같은 값으로 만드는 문제로 바꿀 수 있다.

 

$A$와 $B$ 중 큰 값의 수준을 하나씩 줄여가면서 답을 갱신해줄 것이다. 여기서 어떤 수의 수준을 줄인다는 것은 그 수를 가까운 제곱수로 만든 뒤, 제곱근 연산을 한다는 말이다. 일반성을 잃지 않고 $A \ge B$라고 하자. 현재 단계에서 가능한 답의 후보는 $|A-B|$이다. $A$를 가까운 제곱수로 만든 뒤, 제곱근을 구하면 $C$가 된다고 하자. 이때, 필요한 연산 횟수는 $|C^2-A|+1$이다. 그 이후 단계에서 가능한 답의 후보는 $|C^2-A|+1+|C-B|$가 된다. 이런 식으로 한 단계마다 큰 수의 수준을 하나씩 줄여가면서 답의 후보를 구하면, 그 후보들 중에 문제의 정답이 있다.

?

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

#include <bits/stdc++.h> using namespace std;   using lld = long long;   int isqrt(lld v){     int s = 1, e = 1e9, t = 0;     while (s <= e){         int m = s+e >> 1;         if ((lld)m*m <= v) s = m+1, t = m;         else e = m-1;     }     return t; }   lld solve(lld a, lld b){     if (a < b) return solve(b, a);     if (a == b) return 0;     lld ret = a-b;     lld k = isqrt(a);     if (a <= k*(k+1))         ret = min(ret, solve(k, b) + a - k*k + 1);     else         ret = min(ret, solve(k+1, b) + (k+1)*(k+1) - a + 1);     return ret; }   int main(){     cin.tie(0)->sync_with_stdio(0);     int T; cin >> T;     while (T--){         lld a, b; cin >> a >> b;         cout << solve(a, b) << '\n';     } }

3. 물풍선 애널리스트

무한한 2차원 격자판의 일부 칸에 물풍선이 놓여있다. 물풍선 $i$의 위치는 $(x_i, y_i)$이며 세기는 $p_i$이다. 물풍선은 십자 모양으로 터진다. $t_i$는 물풍선 $i$를 터트렸을 때, 연쇄 작용을 통해 모든 물풍선이 터지는지 여부를 나타낸다. $p_i$에 대한 정보를 잃어버린 상황에서 $t_i$의 정보를 가지고 $p_i$ 값들을 복원하는 문제다. 만약 가능한 답이 여러 가지인 경우, 그중 아무거나 출력한다.

 

만약 $t_i = 1$이라면, 즉, 물풍선 $i$를 터트렸을 때, 연쇄 작용을 통해 모든 물풍선이 터진다면, $p_i$ 값은 크면 클수록 좋다. 만약 $t_i = 0$이라면, 물풍선 $i$를 터트렸을 때 $t_j = 1$인 물풍선 $j$를 터트리면 안 된다. 그런 물풍선을 터트리지 않는 조건에서 $p_i$가 크면 클수록 좋다. 이렇게 $p_i$들 중 가장 큰 값들을 구하면 답이 된다. $t_i$ 값을 만족하는 $p_i$ 조합이 항상 존재하도록 입력이 주어지기 때문에, 이렇게 구한 $p_i$가 $t_i$ 조건을 만족하는지 따로 체크하지 않아도 된다. 한 가지 예외 처리가 필요하다. 만약 모든 $t_i$가 $0$이라면, $p_i$는 모두 1이 되어야 한다.

?

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

#include <bits/stdc++.h> using namespace std;   constexpr int MAX = 1e9;   int main(){     cin.tie(0)->sync_with_stdio(0);     int N; cin >> N;     struct Bomb{         int x, y, t, idx;     };     Bomb A[N+1];     int P[N+1];     bool all_zero = 1;     for (int i=1;i<=N;i++){         cin >> A[i].x >> A[i].y >> A[i].t;         A[i].idx = i; P[i] = MAX;         if (A[i].t) all_zero = 0;     }       if (all_zero){         for (int i=1;i<=N;i++) cout << "1\n";         return 0;     }       auto put_min = [](auto& a, auto b){         a = min(a, b);     };       sort(A+1, A+N+1, [](const Bomb& a, const Bomb& b){         return a.y != b.y ? a.y < b.y : a.x < b.x;     });     int last = 0;     for (int i=1;i<=N;i++){         if (A[i].t) last = i;         else if (last && A[last].y == A[i].y) put_min(P[A[i].idx], A[i].x-A[last].x-1);     }     last = 0;     for (int i=N;i;i--){         if (A[i].t) last = i;         else if (last && A[last].y == A[i].y) put_min(P[A[i].idx], A[last].x-A[i].x-1);     }       sort(A+1, A+N+1, [](const Bomb& a, const Bomb& b){         return a.x != b.x ? a.x < b.x : a.y < b.y;     });     last = 0;     for (int i=1;i<=N;i++){         if (A[i].t) last = i;         else if (last && A[last].x == A[i].x) put_min(P[A[i].idx], A[i].y-A[last].y-1);     }     last = 0;     for (int i=N;i;i--){         if (A[i].t) last = i;         else if (last && A[last].x == A[i].x) put_min(P[A[i].idx], A[last].y-A[i].y-1);     }       for (int i=1;i<=N;i++) cout << P[i] << '\n'; }

4. 멘토링 시스템

$N$ 명의 멘토가 있고, $N$ 명의 멘티가 있다. 멘토링이 가능한 멘토와 멘티 쌍들이 주어졌을 때, 1:1 매칭을 해줄 수 있으며, 그 방법이 유일한지 구하는 문제다.

 

이 문제는 이분그래프에서 완벽 매칭의 유일성을 묻는 문제다. 만약, Hopcroft-Karp 등의 방법을 통해서 최대 매칭을 구했다고 하자. 만약 최대 매칭이 완전 매칭이 아니라면, 즉, 매칭 수가 $N$이 아니라면 답은 "NO"다. 임의의 완전 매칭을 구했을 때, 이 완전 매칭이 유일한지 검사가 추가적으로 필요하다.

 

우선, 가장 먼저 떠오를 수 있는 방법으로는 간선의 순서를 랜덤하게 섞어서 여러 번 매칭을 구해서 구한 매칭이 모두 같은지 확인하는 방법이다. 매칭 알고리즘을 여러 번 돌리기 때문에 시간 초과가 날 수 있으며, 확률적으로 올바르지 않은 답을 구하게 된다. 이 방법으로는 꽤 낮은 확률로 이 문제를 풀 수 있다.

 

다른 방법으로, 이분그래프를 방향성 그래프로 만든 뒤, 임의로 구한 완전 매칭에 속한 간선의 방향을 뒤집는다. 이렇게 만들어진 방향성 그래프에서 사이클이 있는지 확인한다. 만약, 사이클이 있다면 다른 매칭도 존재할 수 있다. 싸이클이 존재하지 않는다면, 완전 매칭은 유일하다. 사이클의 존재 여부 확인은 위상 정렬을 통해 $O(V+E)$ 시간복잡도로 해결할 수 있다.

 

위의 방법은 이분 매칭으로 완전 매칭을 구해야 하므로, 이분 매칭 구현이 아주 빠르지 않은 이상 시간초과가 나올 수 있다. Hopcroft-Karp 알고리즘이 꽤나 빠른 이분매칭 알고리즘인데, $O(E \sqrt{V})$ 시간복잡도를 가진다. Hopcroft-Karp 알고리즘이 최악의 시간을 가지도록 하는 입력 데이터가 잘 알려져 있지 않아, 이 문제에서는 Hopcroft-Karp 알고리즘 1번 돌리는 것으로 시간초과가 나오지 않는다.

?

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

#include <bits/stdc++.h> using namespace std;   int main(){     cin.tie(0)->sync_with_stdio(0);     int N, M; cin >> N >> M;     vector<vector<int>> con(N+N+1);     for (int i=0;i<M;i++){         int a, b; cin >> a >> b;         con[a].push_back(b);     }       vector<int> used(N+1), matched(N+1), dist(N+1);     auto bfs = [&](){         queue<int> que;         fill(begin(dist), end(dist), 1e9);         for (int i=1;i<=N;i++) if (!used[i]) dist[i] = 0, que.push(i);         while (!que.empty()){             int q = que.front(); que.pop();             for (int t: con[q]){                 int m = matched[t];                 if (m && dist[m] == 1e9) dist[m] = dist[q]+1, que.push(m);             }         }     };       function<bool(int)> dfs = [&](int n) -> bool{         for (int t: con[n]){             int m = matched[t];             if (!m || dist[m] == dist[n]+1 && dfs(m)){                 used[n] = t; matched[t] = n;                 return 1;             }         }         dist[n] = 1e9;         return 0;     };       int cnt = 0;     for (;;){         bfs();         int flow = 0;         for (int i=1;i<=N;i++) if (!used[i] && dfs(i)) flow++;         if (!flow) break;         cnt += flow;     }       if (cnt < N) return puts("NO"), 0;       vector<int> indeg(N+N+1);     vector<vector<int>> ncon(N+N+1);     for (int i=1;i<=N;i++){         for (int j: con[i]){             if (used[i] == j) ncon[N+j].push_back(i), indeg[i]++;             else ncon[i].push_back(N+j), indeg[N+j]++;         }     }     int visited = 0;     queue<int> que;     for (int i=1;i<=N+N;i++) if (!indeg[i]) que.push(i);     while (!que.empty()){         int q = que.front(); que.pop();         visited++;         for (int t: ncon[q]){             if (!--indeg[t]) que.push(t);         }     }     if (visited < N+N) return puts("NO"), 0;       cout << "YES\n";     for (int i=1;i<=N;i++) cout << used[i] << '\n'; }

 

사실 이 문제는 완전 매칭이 가능한지 확인하고, 가능하다면 그 방법이 유일한지만 구하는 문제이므로 일반적인 이분매칭 알고리즘 없이 $O(V+E)$ 시간에 해결할 수 있다. 증명을 생략하고 방법만 설명하겠다. 주어진 이분그래프에서 차수가 1인 정점을 살펴보자. 차수가 1인 정점에 대해서 유일한 간선으로 연결된 정점과 매칭 해주는 과정을 반복한다. 만약, 원래 그래프에서 유일한 완전 매칭이 존재한다면 이 방법으로 유일한 완전 매칭을 찾을 수 있다.

?

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

#include <bits/stdc++.h> using namespace std;   int main(){     cin.tie(0)->sync_with_stdio(0);     int N, M; cin >> N >> M;     vector<vector<int>> con(N+N+1);     for (int i=0;i<M;i++){         int a, b; cin >> a >> b;         con[a].push_back(N+b);         con[N+b].push_back(a);     }       int cnt = 0;     int matched[N+N+1]{}, deg[N+N+1]{};     queue<int> que;     for (int i=1;i<=N+N;i++){         deg[i] = size(con[i]);         if (deg[i] == 1) que.push(i);     }     while (!que.empty()){         int q = que.front(); que.pop();         if (matched[q]){             for (int t: con[q]) if (!matched[t]){                 if (--deg[t] == 1) que.push(t);             }         }else{             for (int t: con[q]) if (!matched[t]){                 matched[q] = t;                 matched[t] = q;                 que.push(t);                 cnt++;             }         }     }     if (cnt < N) return puts("NO"), 0;     cout << "YES\n";     for (int i=1;i<=N;i++) cout << matched[i]-N << '\n'; }