2020년 선린인터넷고등학교 교내 프로그래밍 대회들의 풀이
작년 하반기에 선린인터넷고등학교에서 개최되는 여러 정보 경시 대회에 김준원, 권욱제님 등과 함께 출제했던 적이 있습니다. 이 대회들에는 여러 교육적인 문제가 많이 있었으나, 잘 정리된 풀이는 아직 없는 것 같아서 이 참에 정리해봤습니다.
1. 2020 선린 정보 알고리즘경시대회
문제는 https://www.acmicpc.net/category/detail/2294 에서 풀어볼 수 있습니다.
A. 헛간 청약
지문을 잘 읽으면 해결할 수 있는 문제다. 정답은 $\min(N, \lfloor W/L \rfloor \times \lfloor H/L \rfloor)$ 이다. 정답이 최대 $N$ 임에 유의하여 해결해야 합니다.
B. 소-난다!
비트마스킹을 이용하여 $2^N$개의 집합을 모두 순회하며 크기가 $M$인지, 합이 소수인지 체크해주면 되는 간단한 구현 문제입니다.
C. 수업
이 문제는 그리디 알고리즘을 이용하여 접근해볼 수 있으나, 틀린 풀이를 내기 또한 쉬운 문제입니다. 수강생들을 키 역순으로 정렬한 후, std::set 과 같은 자료구조를 이용하여 다음을 반복적으로 수행합니다:
- $i$ 번째 수강생을 크기가 $k_i$ 미만인 팀 중 가장 크기가 큰 팀에 넣는다.
증명은 간단히 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
multiset<ll> S;
int N;
pair<int, int> A[500005];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
for (int i=0; i<N; i++){
cin >> A[i].first >> A[i].second;
}
sort(A, A+N);
reverse(A, A+N);
for (int i=0; i<N; i++){
int v = A[i].second;
auto it = S.lower_bound(v);
if (it == S.begin()) S.insert(1);
else{
--it;
int val = (*it) + 1;
S.erase(it);
S.insert(val);
}
}
cout << S.size() << endl;
}
D. 소 운전한다.
그래프를 1층과 2층, 두 개로 복사해놓을 수 있습니다. 여기에 몇 개의 간선을 추가해서 모델링를 해야하는데, 일단 어떤 고정된 큰 수 $X$ 하나를 정해놓읍시다. ($X$는 별 의미는 없고, 음수 가중치 간선이 없도록 하기 위해 필요합니다.)
각 간선 $(x, y, t, k)$에 대해 1층의 $x$에서 2층의 $y$로 가는, 그리고 1층의 $y$에서 $2$층의 $x$로 가는, $X + t - k$ 길이의 간선을 추가해줍시다. 그러면, 돈까스를 먹는 행위가 1층에서 2층으로 올라가는 연산에 대응되게 됩니다.
1층의 1번 도시에서 2층의 2, 3, …, $V$ 번 도시 까지의 최단 경로를 다익스트라 알고리즘을 한 번 돌려서 구할 수 있습니다. 여기에서 각각 $X$를 빼 주면 문제의 답이 됩니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N, M;
const int P = 100000;
const ll S = 1E9;
const ll INF = 1E18;
vector<pair<ll, int>> adj[200005];
ll dist[200005];
priority_queue<pair<ll, int>> pq;
void add_edge(int u, int v, ll w){
adj[u].push_back({w, v});
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
while (M--){
int u, v, t, k;
cin >> u >> v >> t >> k;
add_edge(u, v, t);
add_edge(v, u, t);
add_edge(P+u, P+v, t);
add_edge(P+v, P+u, t);
add_edge(u, P+v, S+t-k);
add_edge(v, P+u, S+t-k);
}
for (int i=1; i<=P+N; i++) dist[i] = INF;
dist[1] = 0;
pq.push({0, 1});
while (!pq.empty()){
ll _; int u;
tie(_, u) = pq.top(); pq.pop(); _ = -_;
if (_ > dist[u]) continue;
for (auto p: adj[u]){
ll w; int v;
tie(w, v) = p;
ll dist_v = dist[u] + w;
if (dist_v < dist[v]){
pq.push({-dist_v, v});
dist[v] = dist_v;
}
}
}
for (int i=2; i<=N; i++) cout << dist[i+P] - S << '\n';
}
E. 친구
인접하게 앉았으나 서로 좋아하지 않는 학생 쌍의 수를 $X$라고 합시다. $X$에 대한 귀납법으로 항상 가능함을 증명할 수 있습니다.
$X > 0$인 상황에서 반드시 $X$를 감소시킬 수 있음을 보이면 됩니다. $i$ 번째 자리에 앉은 학생을 $a(i)$ 라고 합시다. 두 학생 $a(i), a(i+1)$이 서로 좋아하지 않는다고 합시다. $a(i)$를 제외한 $N-1$명의 학생 중 $a(i)$가 좋아하는 사람의 수가 $N/2$ 이상이고, 자신의 다음번에 앉은 학생 이 $a(i+1)$을 좋아하는 학생의 수도 $N/2$ 이상입니다. 그러면, 비둘기집의 원리에 의해 다음을 만족하는 $a(j)$를 잡을 수 있습니다:
- $a(j)$가 $a(i)$를 좋아하고, $a(j+1)$이 $a(j)$를 좋아한다.
그러면, $a(i) a(i+1) \cdots a(j) a(j+1)$의 배치를 $a(i) a(j) a(j-1) \cdots a(i+1) a(j+1)$로 $a(i+1), \cdots, a(j)$ 구간의 자리 배치를 뒤집어줍시다. 그러면, $X$가 감소하게 됩니다.
이러한 사실은 Ore’s theorem 이라는 이름으로 알려져 있는데, 적당히 교육적이라 생각해서 냈습니다.
F. 실험
Typical하게 2-SAT으로 구현할 수 있는 문제이나, 이를 아무 생각 없이 구현하면, $O(N^2)$의 clause가 생깁니다. 결국, clause를 더 적게 쓰는 동등한 논리식을 찾아야 합니다.
이를 위해, 저희는 변수 $x_1, x_2, \cdots, x_k$ 중 1개 이하만 참이다. 는 조건을 2-SAT clause로 나타내는 방법을 살펴볼 것입니다. 가장 기본적인 방법으로는, 모든 $i < j$에 대해 $\bar x_i \lor \bar x_j$ 를 넣어줄 수 있습니다. 하지만, 이렇게 하면 $O(k^2)$개의 clause를 사용하게 됩니다. 이를 $O(k)$개의 clause로 줄이기 위해, 저희는 새로운 변수 $y_1, y_2, \cdots, y_k$ 를 도입할 것입니다. 다음과 같은 조건을 추가합시다:
- $y_i \implies y_{i+1}$
- $x_i \implies y_i$
- $y_i \implies \bar x_{i+1}$
위 두 개의 조건에 의해 $y_i \iff (x_1 \lor x_2 \lor \cdots \lor x_i)$ 의 관계가 성립하게 됩니다. 그래서 마지막 조건은 최대 하나의 $x_i$만 참이 되도록 만들어줍니다. 이 테크닉은 여러 곳에서 유용하게 쓰일 수 있는 2-SAT의 응용이기 때문에 알아두면 좋을 것입니다.
2. 2020 천하제일 코딩대회
문제는 https://www.acmicpc.net/category/detail/2377 에서 읽어볼 수 있습니다.
A. Amy, Soup is Salty!
문제에서 요구하는 바를 BFS로 구현하여 해결하는 문제입니다. $N$이 매우 작기 때문에, 무한한 cycle이 생기지는 않아 걱정하지 않아도 됩니다. 시각 $T$에 방문하는 노드들을 참조하여 시각 $T+1$에 방문할 노드들을 결정해주는 식으로 할 수 있습니다.
B. Bessie’s Revolution
이 문제는 2차원 그리드에서 절점을 찾는 문제입니다. 절점을 찾는 알고리즘이 잘 알려져 있으며, 해당 알고리즘을 적용하면 해결할 수 있습니다. 하지만, 이 문제 역시도 $N$이 매우 작기 때문에, 모든 정점을 제거해보면서 컴포넌트가 분리되는지 확인해보는 방법 또한 충분히 가능합니다.
C. C = 15
다음과 같은 정보들을 전처리 해놨다고 가정합시다.
- 각 정점 $u$를 루트로 하는 서브트리의 가중치 합
- 각 정점 $u$에서 그 왼쪽 자식을 통과해서 내려가는 경로의 최대 가중치 합
- 각 정점 $u$에서 그 오른쪽 자식을 통과해서 내려가는 경로의 최대 가중치 합
- 각 정점 $u$에서 부모 정점을 통과해서 올라가는 경로의 최대 가중치 합
먼저, 두 리프 $l, r$ 사이에 족보의 힘을 사용했을 때 트리의 지름을 구하는 방법을 생각해봅시다. 족보의 힘을 사용하여 만든 정점이 지름에 포함되지 않는다면, 족보의 힘을 사용한게 무의미합니다. 고로, 지름에 반드시 포함된다고 가정할 수 있습니다.
$l, r$ 에서 $lca(l, r)$까지 각각 올라가며 합쳐진 노드의 가중치를 구할 수 있습니다. 이는 앞서 전처리한 정보 중 첫 번째를 이용하면 쉽게 할 수 있습니다.
이후, 합쳐진 노드를 포함하는 지름이 어떻게 생겼나 생각해보면, 왼쪽 아래로 시작해서 뻗어나가는 경로, 위로 시작해서 뻗어나가는 경로, 오른쪽 아래로 시작해서 뻗어나가는 경로, 이렇게 세 가지 경우가 있습니다. 3개의 경우 각각에 대해 전처리 해놓은 정보 중 2, 3, 4번째를 이용하여 가장 긴 것들을 구해줄 수 있고, 3개의 경우 중 가장 큰 두 개의 합이 U를 포함하는 지름이 됩니다.
이제, 실제 문제를 해결해야 하는데, 이는 투포인터를 이용하여 $l$과 $r$을 잘 관리해주면 됩니다.
D. Darius님 한타 안 함?
문제에 주어진 조건을 그대로 구현하면 되는 매우 쉬운 문제입니다.
int main(){
int K, D, A; char c;
cin >> K; cin >> c; cin >> D; cin >> c; cin >> A;
if (D == 0 || K+A < D) cout << "hasu" << endl;
else cout << "gosu" << endl;
}
E. Ezreal 여눈부터 가네 ㅈㅈ
이 문제의 경우에는, 수학적인 지식을 이용하는 간단한 풀이도 있으나, 의도된 풀이는 동적 계획법이다. $D(i, j, k)$의 3차원 배열에 전체 자릿수($i$), 3으로 나눈 나머지 $(j)$, 5의 배수인지의 여부(=1의 자리, $k$) 를 저장하여 관리해주면 쉽게 해결할 수 있다.
F. Facebook
$a$번 사용자, $b$번 사용자와 동시에 친구인 이용자 수를 빠르게 구할 수 있으면 된다. $v_i$ 를 사용자 $i$와 친구인지의 여부를 담은 binary vector라고 하자. 우리가 구하려는 것은 두 벡터에 and 연산을 한 결과물에서 켜진 비트 수와 같다.
고로, 벡터들을 여러 개의 정수 변수에 쪼개 담는 형태로 관리해주면, 하나의 쿼리를 $O(n/w)$ ($w$: 정수 변수의 비트 수; $w = 32$ or $w = 64$) 정도 시간에 처리해줄 수 있다. 특정 언어에서는 내장 라이브러리에서 이러한 기능을 지원하며 (예: std::bitset) 이를 이용하면 구현이 간단하다.
전체 시간 복잡도는 $O(n^2 / w)$ 가 된다.
bitset<2000> bs[2000];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
for (int i=0; i<N; i++){
string S; cin >> S;
for (int j=0; j<N; j++) if (S[j] == '1') bs[i].set(j);
}
cin >> Q;
while (Q--){
int i, j;
cin >> i >> j;
--i; --j;
auto res = bs[i] & bs[j];
cout << res.count() << '\n';
}
}
G. Gum색
지문이 다소 복잡하지만, 문제에서 요구하는 사항을 그대로 구현하면 되는 문제이다. 한 가지 구현을 간단하게 해줄 수 있는 방법으로는, 각 키워드에 대한 답을 미리 전처리 해놓을 수 있다.
H. Haven
이 대회에서 가장 어려운 문제이다. 한 마디로 요약하자면, XOR MST가 특정 모양을 가지게 하는 배열을 만들어내는 문제이다.
트리에서 적당한 간선을 잡고, 잘라보자. 그러면, 정점 집합의 두 개로 나뉘게 되는데, 양쪽 정점 집합 중 한 곳에 맨 앞 비트를 켜고, 나머지에 맨 앞 비트를 끈다고 해보자. 그러면, 양쪽의 정점 집합을 가르는 간선은 MST를 만드는 과정에서 맨 마지막에 추가되게 된다.
이러한 관찰을 이용하면, 분할-정복 기법을 이용하여 접근할 수 있다. $f(T, k)$를 $T$의 각 정점을 $2^{k+1} - 1$ 이하의 수들로 채우는 함수라 하자.
- $T$에서 “좋은 간선” $e$를 잡아서, 끊자. $T - e$의 각 컴포넌트를 $T_1, T_2$ 라 부르자.
- $f(T_1, k-1)$, $f(T_2, k-1)$을 호출하자.
- $T_1$의 모든 정점에 $2^{k}$를 더해준다.
- 이제, $T_1$과 $T_2$를 잇는 간선들 중 가장 싼 것이 크루스칼 알고리즘에 의해 추가될 것이 명백하다. 우리가 잘랐던 간선 $e$ 가 그러한 간선이 되도록 정점들의 가중치를 “잘” adjust 해주자.
여기에서, 재귀 호출의 횟수가 너무 깊어지지 않기 위해서는, 끊을 간선을 잘 정해줘야 한다. 그런데, 입력으로 주어지는 트리의 차수는 최대 3이다. 이 성질에 의해 끊었을 때 생기는 두 컴포넌트의 크기의 차가 너무 크지 않은 간선이 반드시 존재함이 보장된다.
I. I번은 쉬운 문제
요약하면, 유향 그래프가 주어지고, 정점 집합의 부분집합 $S$가 주어질 때, $S$의 정점들 중 최소 개수만을 택하여 모든 정점으로의 경로가 존재하도록 하는 문제이다.
그래프가 DAG인 상황부터 생각해보자. In-degree가 0인 정점 가운데 $S$에 포함되지 않는 정점이 존재하면, 답이 존재하지 않는다. 아니라면, In-degree가 0인 정점을 모두 택하는 것이 답이 될 것이다.
일반적인 상황으로 와보자. 그래프를 SCC로 나누고, SCC를 정점으로 보게 되면 DAG가 되고, 앞서 DAG인 경우와 같이 쉽게 해결해줄 수 있다.
J. John’s Math Problem
주어지는 수를 $a_1 a_2 \cdots a_N$이라 할 때, $a_i$가 답에 더해지는 횟수를 생각해보자.
일단, $a_i$ 앞에 있는 수들이 어떻든 상관은 없으므로, 기본적으로 $2^{i-1}$가지 경우가 있을 것이다. 이제, $a_i$ 앞의 수들은 무시하고 생각하자. 그러면, $a_i \times 10^k$ 가 답에 더해지는 경우의 수는 ${N-i \choose k}$가 있을 것이다. 이항정리에 의해, $a_i$는 총 $11^{N-i}$번 더해진다고 할 수 있다.
결국, 이 문제의 답은, $\sum a_i \times 2^{i-1} \times 11^{N-i}$가 되는데, 분할-정복에 기반한 빠른 거듭제곱을 이용하면 $O(N \log N)$에, 2와 11의 거듭제곱 값들을 미리 잘 전처리 해놓으면 $O(N)$에 문제를 해결할 수 있습니다.
K. Kaisar - 생존
역으로 각 정점이 LCA로 나타나는 횟수를 구해보자. 어느 정점 $u$가 LCA로 나타나는 횟수는
- $u$ 의 두 자식을 고르는 경우의 수 (= 서브트리 크기의 제곱)에서
- $u$의 자식이 LCA로 나타나는 횟수를 뺀 값과 같다.
따라서, 깊이가 깊은 정점부터 차례로 답을 구해나가면 된다.