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$ 번째 문자도 구할 수 있다.

 

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

#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|$가 된다. 이런 식으로 한 단계마다 큰 수의 수준을 하나씩 줄여가면서 답의 후보를 구하면, 그 후보들 중에 문제의 정답이 있다.

#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이 되어야 한다.

#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번 돌리는 것으로 시간초과가 나오지 않는다.

#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인 정점에 대해서 유일한 간선으로 연결된 정점과 매칭 해주는 과정을 반복한다. 만약, 원래 그래프에서 유일한 완전 매칭이 존재한다면 이 방법으로 유일한 완전 매칭을 찾을 수 있다.

#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'; }