5월쯤에 이런 글을 쓴 적이 있다.
한 달에 푼 모든 다이아 문제를 다 쓰는게 생각보다 고된 작업이라는 것을 깨닫게 되었는데, 그래서 재미있었던 문제만 적기로 했다.
27599. Parmigiana With Seafood
https://www.acmicpc.net/problem/27599
기범이와 셋을 돌때 푼 문제다.
일단 이분탐색의 아이디어를 적용하면 다음과 같이 문제를 환원할 수 있다.
- 트리에 $0$ 또는 $1$이라는 숫자가 적혀 있을 때, A와 B가 서로 리프를 제거하는 것을 반복할 때 A가 $1$을 하나라도 지울 수 있을까?
이것저것 관찰할게 좀 많다. 우선 1이 써진 정점이 적어도 하나 있다고 가정하자.
1. 1이 리프면 A가 승리한다.
2. $N$이 짝수면 A가 승리한다.
1이 써진 정점이 리프면 1에 의해 A가 승리한다.
1이 써진 정점이 리프가 아닐 경우, 이 정점을 $u$라 하자. $u$는 적어도 두 개의 정점과 이웃하다. A의 전략은 B와 상관없이, $u$가 리프가 되었다면 이를 제거하고, 그렇지 않다면 $u$를 리프로 만들지 않는 정점을 제거하면 된다. $N$이 짝수이므로 A가 $u$의 이웃을 하나 빼고 전부 지워서 리프로 만들 수 있는 경우는 없다.
3. 1이 써진 두 정점이 인접해 있다면 A가 승리한다.
1이 써진 두 정점을 $u$와 $v$라 하자. A는 B의 행동과 상관없이 $u$나 $v$가 리프면 해당 정점을 제거하고, 아니면 $u, v$ 모두가 리프가 되지 않는 정점을 제거하면 된다. 그렇게 하지 못 하는 상황은 남은 정점이 4개이고, $u$와 $v$에 리프가 하나씩 붙어있는 상황이다. 이때 어떤 정점을 제거하더라도 A는 $u$나 $v$를 제거할 수 있다.
4. 1이 써진 두 정점의 거리가 홀수인 것이 있다면 A가 승리한다.
3의 일반화된 내용이다.
A는 2와 같은 전략을 취하면 된다. A가 $u$나 $v$를 리프로 만들어야만 하는 상황은 남은 트리가 path이고 01(u)00001(v)0와 같은 상황이므로, $u$나 $v$를 리프로 만들어 B가 이를 제거하더라도, 남은 1을 A가 먹을 수 있다.
사실 2, 3, 4의 근본적인 원리는 몇 개의 1로 이루어진 서브트리를 잡았을 때, A와 B의 전략은 이 서브트리의 1들을 리프로 만들지 않도록 하는 것이다. A의 경우에는 리프로 만들면 B한테 빼앗기고, B의 경우는 리프로 만들면 A가 바로 승리한다.
따라서 이를 확장하여, 다음과 같은 관찰을 할 수 있다.
5. 1, 2의 경우가 모두 아닐 때, A가 승리할 조건은 다음과 동치이다.
- 1이 써진 정점들의 집합의 부분집합 $S$를 고르자. 주어진 트리의 서브트리 $T$를 $S$를 모두 포함하고, $T$에서 $S$가 리프가 아니게 되는 최소 크기의 서브트리라 하자. $N-|T|$가 홀수인 $S$가 존재한다.
<= 방향은 앞선 논리들에 의해 자명하다. A는 $T$를 유지시키려 하면 되고, $T$를 제외한 모든 정점이 제거되었을 때 B의 차례고, B가 하나의 리프라도 제거하면 1이 써진 정점이 리프가 되므로 A가 승리한다.
=> 방향도 비슷한데, B는 1이 리프라면 1을 제거하고, 아니라면 1을 리프로 만들지 않는 아무 정점을 제거하면 된다. 만약 A가 1을 제거하는 일이 생긴다면 위 조건에 모순이다.
따라서, 조건을 만족하는 집합 $S$가 있는지 판정하면 된다. 솔직히 여기서부터는 방법이 많을 것 같은데, 난 그냥 트리디피 돌렸다.
27601. Library Game
https://www.acmicpc.net/problem/27601
바로 위 문제와 같은 셋이다. 시간이 끝나기 직전에 내가 이거 짜면 맞는거 아님? 을 시전했고, 짜는 도중에 기범이가 증명해줬다. 내니까 바로 맞았다.
다음 관찰이 필요하다.
1. $ab > m$인 $a, b$에 대해, 길이가 $a$ 이상인 구간이 $b$개 이상 있으면 B가 승리한다.
B의 전략은 A가 길이가 $a$ 이상인 구간을 배치하려고 시도할 때 $a$의 배수인 아무 책을 답하는 것이다. 그러면 비둘기집의 원리에 의해 한 위치가 두 번 이상 선택된다.
2. 1의 역도 성립한다.
A의 전략은 구간 길이 내림차순으로 해당 구간이 배치될 수 있는 가장 좁은 구간에 배치하는 것이다. 길이 $a$인 구간을 배치할 때에는 현재까지 총 $m/b$개 미만의 구간을 배치했을 것이고, 그렇다면 길이 $a$인 구간을 배치할 수 있는 위치가 적어도 하나 있다.
18438. LCS 5.
https://www.acmicpc.net/problem/18438
클래스에 있어서 풀어봤는데, 풀고 나서 나만 모르는 웰노운이라는 것을 알게 되었다.
LCS 문제와 거의 같은데, 메모리 제한이 작아 O(NM) 크기의 dp table을 선언하는 것이 불가능하다.
분할 정복을 통해 time complexity를 늘리고 space complexity를 줄일 수 있다.
$s$와 $t$의 lcs를 구해야 한다고 하자. lcs에서 $s$의 앞쪽 절반이 $t$에서 몇 개의 prefix와 매칭되는지, $s$의 뒤쪽 절반이 $t$에서 몇 개의 suffix와 매칭되는지는 일반적인 lcs의 길이를 구하는 알고리즘으로 $O(|s||t|)$ time complexity, $O(|t|)$의 space complexity에 구할 수 있다.
길이를 구했으면 $s$와 $t$를 절반씩 쪼갤 수 있고, 각각을 재귀함수로 lcs를 구하면 된다.
32998. 정기 모임 6
https://www.acmicpc.net/problem/32998
나는코더다 송년대회의 정기모임 시리즈 중 6번째 문제이다. 정기 모임 5는 내 때에 적당한 난이도의 문제로 출제되었는데, 이번 송년대회에서는 가장 어려운 문제로 출제되었다.
문제에서 등장하는 정점들의 집합은 다음 세 종류 중 하나이다. 즉, 아래 집합들은 교집합 연산에 대해 닫혀있다.
- $\emptyset$
- 정점 $u$와 정수 $d$에 대하여, $u$에서 거리가 $d$ 이하인 정점의 집합
- 두 인접한 정점 $u$와 $v$, 정수 $d$에 대하여, $u$와 $v$에서 거리가 모두 $d$이하인 정점의 집합
따라서 각 쿼리에 대해 해야 할 것은 집합을 위 형태로 나타내고, 집합의 크기를 구하면 된다.
두 과정 모두 구현량이 상당하다. 집합을 구하는건 위 집합을 관리하는 세그트리를 만들면 되고, 크기를 구하는건 센트로이드 분할을 쓰는데, 사실 집합의 크기를 간선의 길이 합으로 나타낼 수 있고, 이는 기울기가 1인 일차함수에 계단함수를 곱한 것의 합들로 나타낼 수 있다. 이걸 잘 짜면 맞는다.
33079. 흑백 설곽
https://www.acmicpc.net/problem/33079
49점 풀이 (7점이 배정된 서브태스크 전부)
$N$이 짝수일 경우, 단순히 보이는 흰색 모자 수 mod 2를 적는 것으로 가능하다. $N-1$명의 종이를 취합하면 빠진 사람의 모자는 홀수번 세어지고, 나머지 $N-1$명의 모자는 짝수 번 세어져 자신을 제외한 $N-1$명으로부터 받은 종이 합을 2로 나눈 것이 1이라면 흰색, 0이라면 검은색이다.
$N=3k+2$일 때도 위와 같은 전략을 쓸 수 있는데, 이번엔 mod 2 대신 mod 3을 적으면 된다. 자신의 모자는 $3k+1$번 세어지고, 나머지의 모자는 $3k$번 세어져 가능하다.
만점 풀이
뭔가 만점 풀이가 흰색 모자 수와 관련이 있는 수를 적으면 될 것이라는 강력한 추측을 할 수 있다. 즉, 어떤 함수 $f : \mathbb{Z} \rightarrow \{ 0, 1, 2\}$가 존재하여 $f$에 보이는 모자 개수를 적어서 넣으면 될 것 같다는 느낌이 든다. 그래서 나이브로 모든 $f$를 다 해봤더니, 옳은 전략이 있어서 이걸 출력했고 맞았다. (뭔가 좀 불편한데, 그냥 넘어가자)
28168. Painting Grid
https://www.acmicpc.net/problem/28168
WLOG $n \le m$이라 하자.
Pigeonhole principle에 의해 $m > 2^n$이면 일치하는 column이 생길 수밖에 없고, 모순이다.
또한, $N$과 $M$ 모두 홀수이면 정확히 절반만큼 $1$을 채워넣는 것 또한 불가능하므로, 이런 경우를 제외하자.
첫 몇 개의 열로 모든 행들이 구분되도록 해 주고, 남은 열들을 잘 채워넣는 전략을 쓸 수 있다.
나는 다음과 같은 방법을 사용했다.
- 첫 $2 \log N$개 정도의 열에 대하여, $2i$번째 열에는 각 행에 대하여 $i$번째 비트가 켜져 있으면 1, 아니면 0을 배치했고, $2i+1$번째 열에는 $2i$번째 열과 완전히 반대로 배치했다.
- 다음 열들에 대해서는 앞서 배치하지 않은 종류의 열들을 모아서, 짝수 번째 열에는 이런 열들을 배치하고, 홀수 번째에는 이전 열을 반전한 형태를 배치했다.
이렇게 하면 정확히 절반만 1이고, 문제에서 명시한 조건을 만족한다.
여기까지만 보면 간단한 문제인 것 같지만, 이것저것 예외처리가 많다. $m$이 홀수인 경우, $n, m$이 모두 작은 경우 등등의 처리가 필요하다.
31227. 별 보러 가자
https://www.acmicpc.net/problem/31227
모든 주어진 좌표를 $(a, b)$에서 $(a+b, a-b)$ 형태로 생각하면, 두 정점의 거리를 $\max(x_1 - x_2, y_1 - y_2)$로 생각할 수 있다. 그러면 한 구간의 대푯값은 두 개의 별을 골랐을 때 $x$값의 차, $y$값의 차의 최댓값이다.
따라서, 문제를 다음과 같이 생각할 수 있다.
- $N$개 별들의 pair를 고르자. 각각의 pair에서 $x$값의 차, $y$값의 차 중 최댓값을 선택할 때 모든 pair에 대해 이것의 합을 최대화하라. (하나의 값을 pair로 묶을 수도 있다)
그런데 $abs(x_i - x_j)$는 그냥 $x_i - x_j$로 생각해도 된다. 왜냐하면 음수가 되는 쌍이 있다면 절댓값이 같은 양수가 되는 쌍도 있는데, 어차피 최댓값만 중요하기 때문이다. 그래서 다음과 같은 형태의 dp식을 세울 수 있다.
$dp_{i, j}$를 $i$개의 별만 생각할 때 여기서 $j$개의 pair를 골랐을 때 대푯값의 합의 최대라 하자.
$dp_{i, j} = \max_{k < i} \{dp_{k-1, j-1} + \max \{ x_i-x_k, x_k-x_i, y_i-y_k, y_k-y_i\} \}$
이는 naive하게 짜면 $O(M^3)$에 동작하나, $dp_{i, j-1}-x_i$ 등의 prefix maximum 등을 관리하면 $O(NM)$으로 줄일 수 있다.