Problem Solving Diary #15

KOI 2023 2차 대회 문제들을 풀었다. 초/중/고등부에서 서로 다른 문제는 7개였다.

BOJ 28323. 불안정한 수열

어떤 구간 $[l, r]$에 대해 그 안에 있는 수들의 홀짝성이 모두 같다면 이 구간에서는 수를 최대 하나밖에 뽑을 수 있다. 따라서 홀짝성이 같은 인접한 수들은 하나만 남겨도 문제가 없고, 이렇게 합치고 난 뒤 모든 인접한 수들을 고를 수 있고, 이때 남은 수의 개수가 답이 된다. 즉, 첫 수를 고르고, 그 이후로 홀짝성이 바뀔 때마다 고르는 게 최적이다.

BOJ 28324. 스케이트 연습

맨 마지막부터 보면서, $i$번 위치에서 속도는 $i+1$번 위치 속도에서 1 늘릴 수 있으면 늘리고, 아니면 최대 제한으로 설정하는 것이 최적이다. 따라서 단순한 순회 한 번으로 $\mathcal{O}(N)$에 문제를 해결할 수 있다.

BOJ 28325. 호숫가의 개미굴

각 방에 대해 방과 쪽방 중 한쪽에 개미를 모두 넣는 것이 항상 최적이다.

$DP[a][b][c]$를 $1$번 방부터 $a$번 방까지의 정보를 정했고, $1$번 방은 $b=0$이면 방, $b=1$이면 쪽방에 개미가 가득 차 있고, $i$번 방은 $c=0$이면 방, $c=1$이면 쪽방에 개미가 가득 차 있다고 하자. 이 DP는 $\mathcal{O}(N)$에 계산 가능하고, 답을 구할 때는 $\max(DP[n][0][1], DP[n][1][0], DP[n][1][1])$을 구하면 된다.

BOJ 28326. 고기 파티

좌표 압축을 한 뒤 세그먼트 트리를 만들고, 어떤 고기가 $[l, r]$ 구간의 꼬치에 꽂힐 수 있다면, 해당 구간을 나타내는 노드에 vector 같은 걸 만들어 전부 push 해 놓자. 이후 꼬치를 끼울 때는 해당 x좌표를 포함하는 로그 개의 구간의 벡터를 모두 합치고 목록을 얻어낸 뒤 해당 벡터를 모두 비울 수 있다. 하나의 수가 세그먼트 트리 벡터에 들어가는 횟수는 최대 $\mathcal{O}(\log N)$개이므로, 전체 문제도 $\mathcal{O}(N \log N)$에 풀 수 있다. (로그제곱인지 로그인지 조금 헷갈리는데, 로그가 맞는 것 같다)

BOJ 28327. 지그재그

Subtask 2 (13점)

먼저 $f(N, 1, N)$을 $O(N)$에 찾는 방법을 알아보자. 이 방법을 이용하면 나머지 값도 똑같이 구해서 전체 문제를 $O(N^4)$에 해결할 수 있다. 어떤 수열에서 지그재그 수열을 가장 길게 뽑는 방법은 모든 수를 뽑은 뒤, $a_{i-1} < a_i < a_{i+1}$ 혹은 $a_{i-1} > a_i > a_{i+1}$ 인 $a_{i}$들을 제거하는 것이다. 즉, $a_{i-1} < a_i > a_{i+1}$이거나 $a_{i-1} > a_i < a_{i+1}$인 $i$의 개수가 답과 같다. (단, $a_0$과 $a_{n+1}$은 우리에게 유리한 값을 아무거나 집어넣어도 된다고 생각하자.)

Subtask 5 (100점)

$g(x-1)$을 기반으로 $g(x)$의 값을 찾는 방법을 생각해 보자.

모든 $[y, z]$ 구간에 대해 값 $x$가 추가됨으로 인해 $f(x, y, z)$가 변하는 경우를 생각해 보자. 일단 $A_i=x$인 $i$의 값을 $p$라 하자. $p \notin [y, z]$면 값이 변하지 않음이 자명하다. $p \in [y, z]$라면, $A_p$는 무조건 양옆 값보다 큰 극댓값이 된다.

$x$를 하나씩 늘려가면서, $[1, N]$ 구간에 대해 $A_i \le x$인 값들의 위치를 set을 통해 관리하자. 이 set을 $S$라 하고, 그 원소를 $S_1, \cdots, S_L$이라고 하자. $f(x, 1, N)$은 다음 조건을 만족하는 $i$의 개수와 같다. $(1 \le i \le L)$

• $i=1$ 혹은 $i=L$ (Type 1)
• $S_{i-1} > S_i < S_{i+1}$ 혹은 $S_{i-1} < S_i > S_{i+1}$ $(2 \le i \le L-1)$ (Type 2)

따라서, 위 조건을 만족하는 $i$의 개수를 모든 $[y, z]$ 쌍에 대해 빠르게 셀 수 있으면 문제가 쉽게 해결된다. Type 1과 Type 2로 나누어서 생각하는 것이 편리하다.

Type 1과 Type 2 각각에 대해 set에 원소를 추가하면서 양옆으로 인접한 원소 등을 이용해 계산할 수 있다. 여기서부터는 단순한 계산과 Casework이고, 자세한 설명은 생략한다. 전체 문제는 $O(N \log N)$에 풀 수 있다.

BOJ 28328. 잔디밭의 개미굴

어떤 쌍 $(i, j)$가 평화로운 쌍이 아니라는 것은, 모든 최적해가 방 $i$와 $j$에 동시에 개미가 들어가야 한다는 것을 나타낸다. 다시 말하면, 모든 최적해에 방 $i$가 들어가면서, 모든 최적해에 방 $j$가 들어가야 한다는 것이다. 따라서, 모든 최적해에 들어가는 방의 수를 찾으면 된다. 이런 방 집합을 찾은 뒤 $S$라고 하자. 이때 답은 $\binom{N}{2} - \binom{|S|}{2}$이다.

별다른 추가 조건이 없을 때 최대 개미 수를 구하는 것은 DP로 쉽게 할 수 있다. 여기서 방 $x$에 필수적으로 개미가 들어가야 하는지를 확인하기 위해서는, 방 $x$에 개미가 들어가지 않는다고 가정하고 주변의 모든 서브트리에 대한 답을 합쳤을 때 원래 문제의 답이 되는지를 확인하면 된다. DP를 트리에서 양방향으로 하는 테크닉을 사용하면 전체 문제를 $O(N)$ 에 해결할 수 있다.

BOJ 28329. 바보 자물쇠

이 문제는 옛날에 문제를 보고 풀이를 찾은 적이 있어서 구현만 했다.