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

<p data-ke-size="size16">문제 설명에 적힌 규칙과 다른 방식으로 $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"이 된다.</p>

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

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

<p data-ke-size="size16">말로 설명해보니 방법이 좀 복잡해 보이는데, 실제로는 간단하다. 아래 코드를 참고하자.</p>

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

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

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

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

<p data-ke-size="size16">만약 $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이 되어야 한다.</p>

<h3 data-ke-size="size23">4. 멘토링 시스템</h3>
<p data-ke-size="size16">$N$ 명의 멘토가 있고, $N$ 명의 멘티가 있다. 멘토링이 가능한 멘토와 멘티 쌍들이 주어졌을 때, 1:1 매칭을 해줄 수 있으며, 그 방법이 유일한지 구하는 문제다.</p>

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

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

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

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


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

PS 이야기

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

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

댓글