<div id="readability-page-1" class="page"><div><h3 data-ke-size="size23">1214 A. 조약돌 순서</h3>
<p data-ke-size="size16">처음에 $[1, 2, 3, ..., K]$이 적혀있는 크기 $K$인 배열 $A$가 있다. $i = 1$부터 시작하여 $A_i$와 $A_{i+1}$의 값을 바꾼다. 그리고 $i$를 $1$ 증가시킨다. 만약 $i = K-1$이라면 다음 $i$의 값은 $K$가 아니라, $1$이 된다. 바꾸는 작업을 $N$ 번 하였을 때, 최종 배열의 상태를 구하는 문제다.</p>

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

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

<p data-ke-size="size16">D[i][j] = 문자열의 길이 $i$인 접두사에서 상태가 $j$일 때 제거해야 하는 문자의 최소 개수라고 정의하자.</p>
<p data-ke-size="size16">상태 $j$는 만약 모든 문자가 짝이 맞는다면 $j = 0$, 맨 마지막 문자를 제외한 모든 문자가 짝이 맞는다면 $j$는 맨 마지막 문자로 정의한다.</p>

<p data-ke-size="size16">문제에서 요구하는 답은 D[N][0]이 되며, 이 DP 배열은 시간복잡도 $O(N)$만에 구할 수 있다.</p>

<h3 data-ke-size="size23">1214 C / 1519 A. 빙고</h3>
<p data-ke-size="size16">$N \times M$ 크기의 빙고판이 있다. 칸에 적힌 수는 알 수 없고, 불러지는 수도 알 수 없다. $i$ 번째 행을 완성하면 $A_i$점을 획득하며, $j$ 번째 열을 완성하면 $B_j$점을 획득한다. 사회자가 번호를 $K$ 개 부를 때, 얻을 수 있는 최대 점수를 구하는 문제다.</p>

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

<h3 data-ke-size="size23">1214 D / 1519 B. 야찌</h3>
<p data-ke-size="size16">$1$ 이상 $6$ 이하의 수가 적힌 $N$ 개의 카드가 있는 카드 더미가 있다. 그리고 5장의 종이가 있다. 각 턴마다 카드 더미 위에서 카드 5장을 뽑아 순서대로 종이에 적는다. 그리고 최대 한 번 수를 지울 종이를 고르고, 카드 더미에서 카드를 다시 뽑아 지운 종이 위에 수를 적을 수 있다. 만약, 종이 5장에 적힌 수가 모두 같다면 야찌다. 카드 더미에 대한 정보가 주어졌을 때, 가능한 야찌의 최대 횟수를 구하는 문제다.</p>

<p data-ke-size="size16">D[i] = 카드 더미에서 총 $i$ 장의 카드를 뽑았을 때, 할 수 있는 야찌의 최대 횟수라고 정의하자.</p>

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

<h3 data-ke-size="size23">1214 E. 삼각</h3>
<p data-ke-size="size16">정점 $N$ 개와 양방향 간선 $M$ 개로 이루어진 그래프가 주어진다. 각 간선에는 길이가 있다. 정점 $S$가 주어진다. 정점 $S$에서 시작하여 어떤 정점 $A$로 이동했다가, 다른 정점 $B$로 이동하고, 다시 정점 $S$로 돌아오는 경로 중에 정점 $S$를 중간에 방문하지 않으면서 가장 길이가 짧은 경로를 구하는 문제다.</p>

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

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

<h3 data-ke-size="size23">1519 C. 덧셈 프로그램</h3>
<p data-ke-size="size16">크기 $N$인 정수 배열 $A$가 있고, $M$ 개의 명령어로 구성된 프로그램이 있다. 명령어는 $A_i$에 $A_j$를 더하는 꼴을 한다. 이 프로그램을 총 $L$ 번 실행하는데, 각 실행마다 배열의 초기값이 다를 수 있다. 각 실행마다 프로그램이 종료되는 시점에서 $A_1$의 값을 구하는 문제다.</p>

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

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

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

<p data-ke-size="size16">풀이의 아이디어는 간단하다. 어떤 $x$ 좌표에 대해 적절한 점은 연속된 구간으로 표현된다. 각 점 집합에 대해 독립적으로 적절한 점의 $y$ 좌표 구간을 구하고, 교집합을 구하면 된다.</p>

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

<h3 data-ke-size="size23">1519 E. 지름길</h3>
<p data-ke-size="size16">정점 $N$ 개와 양방향 간선 $M$ 개로 이루어진 그래프가 주어진다. 각 간선에는 길이가 있다. 정점 $S$와 정점 $T$가 주어진다. 정점 $S$에서 정점 $i$로 가는 최단 거리와 정점 $i$에서 정점 $T$로 가는 최단 거리가 유지되도록 최소 개수의 간선만 남기는 문제다.</p>

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

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

<p data-ke-size="size16">풀이의 원리를 이해했다면, 남겨야하는 간선을 구하는 것은 간단하다. 첨부된 코드를 참고하자.</p>
</div></div>

PS 이야기

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)$ 시간복잡도에 해결할 수 있다.
더보기
#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)$만에 구할 수 있다.
더보기
#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)$이다.
더보기
#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$이므로, 구현에 따라 시간초과가 날 수도 있다. 아래 첨부된 코드는 비트마스크를 이용한 전처리 작업으로 최대한 상수를 줄였다.
더보기
#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$ 개라는 것도 증명할 수 있다. 이 점을 이용하여, 서브태스크를 해결할 수 있다.
더보기
#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)$이다.
더보기
#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)$이다.
더보기
#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})$이다.
 
풀이의 원리를 이해했다면, 남겨야하는 간선을 구하는 것은 간단하다. 첨부된 코드를 참고하자.
더보기
#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';
}

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

댓글