Wonseok Shin | 7월 3주차 Weekly PS

Back to : ps-weekly

Contents

Recent Updates
Rounds
Problems

July 11 - July 18, 2021

이 글에 구현코드 링크가 없더라도 PS 레포 링크 에 가서 대회 단위로 들어가면 보통 올려놓은 코드를 볼 수 있습니다.

Recent Updates

2021 SCPC 라운드 1은 뭐 무난히 통과했습니다.

Rounds

(팀연습) 서강대학교 2020 SPC Div.1 (Champion)

포스팅 링크 에 포스팅했습니다.

(대회) SCPC 2021 Round 1

포스팅 링크 에 포스팅했습니다.

(Atcoder) Atcoder Beginner Round 210

라운드 링크
582등, -9 (1844 -> 1835).
D번 DP문제를 못 풀어서 레이팅을 좀 깎아먹었습니다. 대신 E번 (수학..이라긴 좀 애매하고 잘 모르겠습니다) 을 풀어서 본전은 친듯 합니다.

Problems

이번에는 DP 연습을 하기로 했습니다. 백준 번호를 적어놨으므로 문제설명은 가급적 생략합니다.

IOI 2009-4, Raisins (BOJ 5463 건포도)

난이도 Gold 1
IOI에 이런 문제가 나온적 있는지는 몰랐습니다. 무슨 20세기 대회도 아니고 2009년에..?
거의 straightforward한 DP로 해결이 가능합니다.
- dp[r1][c1][r2][c2] 를 직접 $[r1, c1] \times [r2, c2]$ 사각형의 DP값이라고 정의하면,
- 이제 이 값은 모든 가로/세로 컷을 직접 확인하면 됩니다.
- 구현 코드 가 상당히 간단하므로 확인하면 도움이 될것 같습니다. 레포에서 IOI를 찾아가면 됩니다.
시간 복잡도는 $O(n^4)$ 칸 DP를 칸당 $O(n)$ 시간에 채우는 것이므로 $O(n^5)$ 입니다.

서강대학교 SPC 2015-1F, 몬스터 (BOJ 11573)

난이도 Gold 1
마찬가지로 dp[i][j][k] 를 빨간색 노란색 파란색이 $i, j, k$ 마리 남은 상황이라고 생각하면 됩니다.
이때, Random choice에 의해 빨간색과 노란색이 만날 확률은 $\frac{ij}{ij + jk + ki}$ 입니다.
이렇게 각 state transition의 확률을 구해서, 확률을 탑다운 DP로 찾아주면 됩니다.
어떤 특정 종의 몬스터가 아예 없어지면 두 종류 중에는 항상 이기는 쪽이 정해져 있으므로 확률이 (1, 0, 0) 형태로 나옵니다. 이를 베이스 케이스로 쓰면 됩니다.
대칭성을 잘 이용하면 $n^3$ 개의 실수값만으로 계산할수 있는것 같은데, 저는 $p_1, p_2, p_3$ 을 struct로 묶어서 돌렸습니다.

연세대학교 2018-C 나무 위의 입자 (BOJ 15669)

난이도 Platinum 5
정점 U, V에 대해, 편의상 depth(u) < depth(v) 라고 합시다.
이때, v의 ‘위에서’ 하나, ‘아래서’ 하나를 골라서 그 거리가 홀수/짝수가 되는 정점쌍 개수를 세는 문제입니다.
- 가장 쉬운 방법은, dp[i] 에 i를 루트로 하는 서브트리에서 깊이가 홀수/짝수인 점의 개수를 미리 세 놓고
- 거리가 짝수이려면 v 아래 서브트리에서 짝수 깊이, v 아래가 아닌 곳에서 짝수 깊이
- 또는 둘다 홀수 깊이인 노드들의 개수의 곱입니다.
역시 코드가 조금더 보기 쉬운 문제입니다. 모든 정보는 DFS를 돌리면서 Tree DP 할 수 있어서 $O(n)$ 에 해결 가능합니다.

연세대학교 2018-L 연세워터파크 (BOJ 15678)

난이도 Platinum 5
핵심은 $D_i = \max_{i - d \leq j < i} (D_j + A_i)$ 라는 DP식이고,
이 식에서 $A_i$는 이미 정해져 있으므로 $[i - d, i)$ 구간의 최댓값을 빨리 구할수 있으면 됩니다.
Deque DP Optimization이라는 방법을 적용하는 기본 연습문제입니다. 이 방법은 언젠가 따로 소개하겠습니다.
$n$ 이 작아서 세그먼트 트리로 $O(n \log n)$ 에도 풀 수 있습니다.

IOI 2002-4, Batch Scheduling (BOJ 5498)

난이도 Platinum 3
지문이 굉장히 이해하기 어렵습니다.
T 의 부분합을 TS, F의 부분합을 FS 라고 생각하겠습니다.
뒤에서부터 역순으로 Batch를 만들면서 오는 식으로 생각합니다.
- Batch 블록 하나가 i, i+1, ... j 구간을 커버한다면, t + s + (TS[j] - TS[i-1]) 에 (FS[j] - FS[i-1]) 에 곱해야 하는데, 각 블록의 시작점 t를 도저히 계산할 방법이 없습니다.
이 문제를 해결하기 위해, 앞 블록에서의 소모 시간을 뒷 블록에 계속 더해 주는 식으로, (s + (TS[j] - TS[i-1])) * (FS[n] - FS[i-1]) 로 계산해서 더해주면 모든 블록을 더했을때 결과가 같습니다.
따라서 다음 DP식을 생각합니다. $D_i = \min_{i \leq j} (D_j + (s + TS_{j} - TS_{i-1}) (FS_{n} - FS_{i-1}))$ 이 식은 그냥 계산하면 $O(n^2)$ 라서, 더 줄이고 싶습니다.
여기서, $j$와 무관한 항을 다 min 밖으로 빼서 정리하면, $D_j + TS_{j} \times u_i$ 들의 minimum을 빠르게 계산하는 문제가 됩니다 ($u_i$는 $i$에 의해 결정되는 상수값)
- 이러한 DP를 Convex Hull Trick으로 빠르게 처리할 수 있음이 알려져 있습니다. $TS_{j}$의 성질을 매우 잘 이용해서 스택에 잘 왔다갔다하는 $O(n)$ 풀이도 가능하고…
- Li-Chao Tree같은 놀라운 (이제 리차오는 별로 놀라운까지는 아닙니다) 자료구조를 박으면 $O(n \log n)$ 에 풀 수 있습니다.
- Li-Chao Tree에 대해서는 kjp4155님의 소멤 글 이 잘 알려져 있고, 무지성 복붙 가능한 최고의 코드입니다.
- ICPC에도 몇번 나온 자료구조인만큼 하나 가지고 있으면 좋을듯 합니다
이와는 별론으로, 이 문제는 무려 20년 전의 문제라서 $O(n)$ 이 정해이면서 ($n \log n$ 까지는 허용했고) $n$이 1만밖에 안 됩니다. 요즘에 나온다면 500만이나 최소 100만으로 내지 않았을까요? 500만 리차오는 불가능할거고, 100만 리차오는 잘 모르겠습니다.
슬프게도, 이것 때문에 $O(n^2)$의 나이브한 DP가 100ms대로 통과합니다. 세월의 흐름이 느껴지기도 하면서, 동시에 만약 지금보다 컴퓨터가 다시 10배 빨라져서 지금 $O(n^2)$ 가 안 뚫리는 문제들이 다 뚫리게 되면 기존 문제들을 온라인저지 상에서 리마스터할 필요가 있을수도 있겠다, 하는 (저와는 별로 상관없는 일이지만) 생각도 들게 하네요.

JOI 2009-4 散歩 (BOJ 5573 산책)

난이도 Platinum 4
이번주에 제가 포스팅하는 문제중 가장 어려웠습니다.
$N-1$ 번째의 보드 상태를 알고 있다면, $N$번째는 직접 시뮬레이션해서 도착할 수 있습니다.
특정 칸에 지금까지 도달한 횟수를 안다면, 그 칸의 상태를 알 수 있습니다.
$(1, 1)$ 을 밟는 횟수는 $N-1$번입니다.
어떤 칸을 밟는 횟수가 $K$번이면, 계속 오른쪽과 아래가 왔다갔다하므로 그중 절반은 오른쪽으로, 절반은 아래로 내려가게 됩니다.
- 단, $K$가 홀수이면 0번째에 어느 방향이었는지를 보고 한번 더가면 됩니다.
- 즉, dp[i][j+1], dp[i+1][j] 에 dp[i][j]/2 를 (필요하다면 1만큼 더) 더해주면 됩니다.
이 아이디어가 굉장히 떠올리기 힘들었습니다. 역시 DP는 어렵네요.