Atcoder Educational DP Contest
교육적인 DP 문제를 풀어보자
- 참고 사항
- A - Frog 1
- B - Frog 2
- C - Vacation
- D - Knapsack 1
- E - Knapsack 2
- F - LCS
- G - Longest Path
- H - Grid 1
- I - Coins
- J - Sushi
- K - Stones
- L - Deque
- M - Candies
- N - Slimes
- O - Matching
- P - Independent Set
- Q - Flowers
- R - Walk
- S - Digit Sum
- T - Permutation
- Z - Frog 3
- 문제 푼 순서
- 대회 링크: https://atcoder.jp/contests/dp
- 총 26 문제가 있는데 시간 날 때마다 풀어보도록 하자. 다 풀 수는 있겠지?
- 현재 $A\sim S$번까지 풀었는데 풀이를 보면 밑도 끝도 없이 $\operatorname{dp}$를 정의하고 시작한다. 예시로 I번 Coins 문제를 보면 $\operatorname{dp}[i][k]$를 $1$번부터 $i$번 동전까지 던졌을 때 앞면이 $k$개 나올 확률로 정의하고 시작한다
- 갑자기 $\operatorname{dp}[i][k]$가 튀어나와서 어색해 보이는데 여기엔 생략된 내용이 있다 (DP 문제를 많이 풀었다보니 그냥 당연하게 여겨버림). $\operatorname{dp}[i][k]$와 같이 정의한 이유는 여태까지 사용한 동전의 개수와 앞면이 나온 개수만이 상태 공간을 정의하는 데 유의미하기 때문이다. 생각해보자. $N$개의 동전을 던져 앞면이 더 많이 나올 확률을 알아야 한다. $N$번째 동전을 던지기 전에는 $N-1$개의 동전을 던졌을 것이며 앞면이 몇 개 나왔는지 알아야 문제의 정답을 구할 수 있다. 즉, 던진 동전 개수와 앞면이 몇 개 나왔는지만이 상태 공간을 결정하는 데 필요하다
- 상태 공간의 전이가 어떻게 이루어지는지도 살펴보자. $i$개의 동전을 사용해서 앞면이 $k$개 나오는 상황을 생각해보자. $i$번째 동전을 던지기 전에는 $i-1$개의 동전을 던졌을 것이다. 이때 $i$번째 동전을 던져 앞면이 나왔다면 $i-1$개의 동전을 던졌을 땐 앞면이 $k-1$개 나와야 하고 뒷면이 나왔다면 앞면이 $k$개 나와야 한다. 이러한 특성은 $\operatorname{dp}[i][k] = p_i \cdot \operatorname{dp}[i - 1][k - 1] + (1 - p_i)\cdot \operatorname{dp}[i - 1][k]$와 같은 점화식을 매우 자연스럽게 도출한다
- 이때 각 상태 공간을 노드, 전이를 간선으로 생각할 수 있으며 이는 DAG를 이루니 탑다운 또는 바텀업으로 $O(|V| + |E|)$에 해결할 수 있는 것이다
- $\operatorname{dp}[i]$를 개구리가 $i$번 돌까지 오는데 필요한 최소 비용이라고 하자. 개구리가 $i$번 돌에 위치하고 있다면 점프 이전에는 $i-1$번 또는 $i-2$번 돌에 위치했을 것이다
- 그러므로 $\operatorname{dp}[i] = \min(\operatorname{dp}[i - 1] + |h_{i-1} - h_i|,\, \operatorname{dp}[i - 2] + |h_{i-2} - h_i|)$이며 초깃값으로 $\operatorname{dp}[1] = 0, \operatorname{dp}[2] = |h_1 - h_2|$이다
- 정답은 $\operatorname{dp}[N]$이며 전체 알고리즘의 시간 복잡도는 $O(N)$이다
def cost(i, j):
return abs(array[i] - array[j])
def solution():
global array
N = int(input())
array = list(map(int, input().split()))
inf = float("inf")
dp = [inf] * N
dp[0] = 0
dp[1] = cost(0, 1)
for i in range(2, N):
dp[i] = min(dp[i - 1] + cost(i - 1, i), dp[i - 2] + cost(i - 2, i))
answer = dp[N - 1]
print(answer)
solution()
- Frog 1 문제에선 $2$가지 경우만 고려하면 됐다. 여기선 $K$개의 경우를 고려하자
- 전체 알고리즘의 시간 복잡도는 $O(NK)$이다
def cost(i, j):
return abs(array[i] - array[j])
def solution():
global array
N, K = map(int, input().split())
array = list(map(int, input().split()))
inf = float("inf")
dp = [inf] * N
dp[0] = 0
dp[1] = cost(0, 1)
for i in range(2, N):
for j in range(1, K + 1):
prev = max(i - j, 0)
dp[i] = min(dp[prev] + cost(prev, i), dp[i])
answer = dp[N - 1]
print(answer)
solution()
- $\operatorname{dp}[i][t]$를 $i$번째 날에 $a,b,c$ 중 $t$ 활동을 했을 때 얻을 수 있는 최대 행복 점수라고 하자
- 전날에 안 한 활동 중 하나를 골라서 했을 때 행복 점수가 더 큰 걸로 선택하면 된다. 따라서 점화식은 다음과 같다
- $\operatorname{dp}[i][a] = A[i] + \max(\operatorname{dp}[i - 1][b], \operatorname{dp}[i-1][c])$
- $\operatorname{dp}[i][b] = B[i] + \max(\operatorname{dp}[i - 1][a], \operatorname{dp}[i - 1][c])$
- $\operatorname{dp}[i][c] = C[i] + \max(\operatorname{dp}[i - 1][a], \operatorname{dp}[i - 1][b])$
- 정답은 $\max(\operatorname{dp}[N][a], \operatorname{dp}[N][b], \operatorname{dp}[N][c])$이며 전체 알고리즘의 시간 복잡도는 $O(N)$이다
def solution():
N = int(input())
A, B, C = [], [], []
for _ in range(N):
a, b, c = map(int, input().split())
A.append(a)
B.append(b)
C.append(c)
dp = [[0] * 3 for _ in range(N)]
dp[0] = [A[0], B[0], C[0]]
for i in range(1, N):
dp[i][0] = A[i] + max(dp[i - 1][1], dp[i - 1][2])
dp[i][1] = B[i] + max(dp[i - 1][0], dp[i - 1][2])
dp[i][2] = C[i] + max(dp[i - 1][0], dp[i - 1][1])
answer = max(dp[N - 1])
print(answer)
solution()
- 웰노운 배낭 문제이다. 배낭에 물건을 담는 경우의 수는 각 물건을 배낭에 넣거나 안 넣거나로 $2^N$이지만 배낭 용량은 $W$에 바운드 됨에 집중하자. 그럼 $i$번째 물건까지 고려했을 때 $1\sim W$ 무게별로 최대 가치를 저장함으로써 DP를 사용해 해결할 수 있게 된다
- 전체 알고리즘의 시간 복잡도는 $O(NW)$이며 무게를 역순으로 탐색하면 공간 복잡도는 $O(W)$가 된다
def solution():
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (W + 1)
for w, v in items:
for t in range(W, w - 1, -1):
dp[t] = max(dp[t - w] + v, dp[t])
answer = dp[W]
print(answer)
solution()
- $O(NW)$는 시간 초과이다. 대신 물건의 가치가 최대 $10^3$임을 이용하자
- 배낭에 담을 수 있는 물건의 가치 합 $V$는 최대 $\sum\limits_{i=1}^{N}v_i$이다. $1$과 $V$ 사이의 가치에 대해 해당 가치를 만드는 데 필요한 최소 배낭 용량을 기록하자. 그럼 이것이 $W$를 초과하지 않는 것 중 최대 가치가 정답이며 시간 복잡도는 $O(NV)$이다
def solution():
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
inf = float("inf")
V = sum(map(lambda x: x[1], items))
dp = [inf] * (V + 1)
dp[0] = 0
for w, v in items:
for t in range(V, v - 1, -1):
dp[t] = min(dp[t - v] + w, dp[t])
for v in range(V, 0, -1):
if dp[v] <= W:
print(v)
return
solution()
- 웰노운 문제이다. $\operatorname{dp}[i][j]$를 $s$의 $i$번째 문자까지, 그리고 $t$의 $j$번째 문자까지 고려했을 때 LCS의 길이라고 하자
- 만약, $s_i = t_j$라면 $\operatorname{dp}[i][j] = \operatorname{dp}[i - 1][j - 1] + 1$이다
- 그렇지 않다면 적어도 둘 중 하나는 LCS에 포함되지 않으므로 $\operatorname{dp}[i][j] = \max(\operatorname{dp}[i - 1][j], \operatorname{dp}[i][j - 1])$이다
- LCS의 길이는 구했으니 이를 역추적하자. $i = |s|, j = |t|$에서 시작해 둘 중 하나가 $0$이 될 때까지 역추적할 것이다. $\operatorname{dp}[i][j] = \operatorname{dp}[i - 1][j]$라면 $s_i$는 LCS에 포함되지 않으며 $i$를 $i-1$로 갱신하자. 반대로 $\operatorname{dp}[i][j] = \operatorname{dp}[i][j - 1]$라면 $j$를 $j-1$로 갱신하자. 둘 다 아니라면 $\operatorname{dp}[i][j] = \operatorname{dp}[i - 1][j - 1] + 1$인 것으로 $s_i =t_j$이니 이를 배열에 추가하고 $i$를 $i-1$로, $j$를 $j-1$로 갱신하자
- LCS의 맨 뒤부터 역추적했으므로 배열을 뒤집고 결합해야 LCS가 된다. 시간 복잡도와 공간 복잡도는 $O(|s|\cdot |t|)$이다
def solution():
s = input().rstrip()
t = input().rstrip()
n, m = len(s), len(t)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
s_i = s[i - 1]
for j in range(1, m + 1):
t_j = t[j - 1]
if s_i == t_j:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
trace = []
i, j = n, m
while i > 0 and j > 0:
s_i = s[i - 1]
if dp[i][j] == dp[i - 1][j]:
i -= 1
elif dp[i][j] == dp[i][j - 1]:
j -= 1
else:
trace.append(s_i)
i -= 1
j -= 1
answer = "".join(trace[::-1])
print(answer)
solution()
- $\operatorname{dp}[u]$를 $u$번 노드를 시작으로 할 때 얻을 수 있는 최장 경로의 길이라고 하자
- $u$번 노드에서 $v_1, v_2, \dots, v_k$번 노드로 향하는 간선이 있다고 하면 그래프에 사이클이 없으므로 $\operatorname{dp}[u] = 1 + \max\limits_{i \in \{1,2,\dots, k\}}\operatorname{dp}[v_i]$를 만족한다
- 초깃값으로 $u$번 노드의 진출차수가 $0$인 경우 $\operatorname{dp}[u] = 0$이다
- 정답은 $\max(\operatorname{dp})$이며 각 노드와 간선을 $O(1)$번만 확인하므로 전체 알고리즘의 시간 복잡도는 $O(N + M)$이다
import sys
sys.setrecursionlimit(10**5 + 2)
def dfs(graph, u, dp):
if dp[u] >= 0:
return dp[u]
lengths = []
for v in graph[u]:
length = dfs(graph, v, dp)
lengths.append(length)
dp[u] = 1 + max(lengths) if lengths else 0
return dp[u]
def solution():
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
x, y = map(int, input().split())
graph[x].append(y)
dp = [-1] * (N + 1)
for u in range(1, N + 1):
dfs(graph, u, dp)
answer = max(dp)
print(answer)
solution()
- $\operatorname{dp}[i][j]$를 $(1,1)$에서 $(i, j)$까지 이동하는 경우의 수라고 하자
- 오른쪽과 아래로만 이동이 가능하므로 직전엔 현재의 왼쪽 또는 위에 위치했을 것이다. 따라서 다음과 같은 점화식을 세울 수 있다
- $\operatorname{dp}[i][j] = \operatorname{dp}[i - 1][j] + \operatorname{dp}[i][j - 1]$, 단, $(i,j),(i-1, j), (i, j-1)$은 빈 공간이며 $\operatorname{dp}[0][\cdot]$과 $\operatorname{dp}[\cdot][0]$은 $0$이다
- 바텀업 방식으로 행은 $1$행부터, 행마다 열은 $1$열부터 순회하면 되며 초깃값으로 $\operatorname{dp}[1][1] = 1$이다
- 최종적으로 정답은 $\operatorname{dp}[H][W]$이며 전체 알고리즘의 시간 복잡도는 $O(HW)$이다
def solution():
wall = "."
mod = 10**9 + 7
H, W = map(int, input().split())
grid = [input().rstrip() for _ in range(H)]
dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
for r in range(H):
for c in range(W):
if grid[r][c] != ".":
continue
if r > 0 and grid[r - 1][c] == ".":
dp[r][c] += dp[r - 1][c]
if c > 0 and grid[r][c - 1] == ".":
dp[r][c] += dp[r][c - 1]
dp[r][c] %= mod
answer = dp[H - 1][W - 1]
print(answer)
solution()
- $\operatorname{dp}[i][k]$를 $1$번부터 $i$번 동전까지 던졌을 때 앞면이 $k$개 나올 확률이라고 하자
- 만약 $i$번 동전을 던져 앞면이 나온다면 $\operatorname{dp}[i][k] = p_i \cdot \operatorname{dp}[i - 1][k - 1]$이다 (단, $k > 0$)
- 그렇지 않고 $i$번 동전을 던져 뒷면이 나온다면 $\operatorname{dp}[i][k] = (1 - p_i)\cdot \operatorname{dp}[i - 1][k] $이다
- 따라서 $\operatorname{dp}[i][k] = p_i \cdot \operatorname{dp}[i - 1][k - 1] + (1 - p_i)\cdot \operatorname{dp}[i - 1][k]$이다 ($k=0$이면 앞의 항은 무시)
- 최종적으로 앞면이 뒷면보다 많이 나올 확률을 구해주면 정답이다
- 전체 알고리즘의 시간 복잡도는 $O\left(N^2\right)$이며 $k$를 역순으로 탐색하면 공간 복잡도는 $O(N)$이다
def solution():
N = int(input())
probs = list(map(float, input().split()))
dp = [0] * (N + 1)
dp[0] = 1
for i, p in enumerate(probs, start=1):
for k in range(i, -1, -1):
dp[k] *= (1 - p)
if k > 0:
dp[k] += p * dp[k - 1]
answer = sum(dp[(N + 1) // 2:])
print(answer)
solution()
- 앞 번호의 문제 중 가장 어려운 문제이다. 쉬운 버전의 문제를 먼저 풀어 인사이트를 얻고 풀이를 확장할 것이다
- 모든 접시에 초밥이 $1$개만 있다고 가정해보자. 그럼 $N$개의 초밥을 먹기 위해 주사위를 굴리는 횟수의 기댓값은 다음과 같다
- $\text{$N$개의 초밥을 먹기 위해 주사위를 굴리는 횟수의 기댓값} = \text{남은 $N$개의 초밥 중 초밥 $1$개를 먹기 위해 주사위를 굴리는 횟수의 기댓값} + \cdots + \text{남은 $1$개의 초밥 중 초밥 $1$개를 먹기 위해 주사위를 굴리는 횟수의 기댓값}$
- 즉, 초밥을 먹을 확률은 $N$개의 초밥 중 현재 $x$개가 남아있다고 할 때 $\frac{x}{N}$이다. 이를 먹는 데 성공할 때까지 시도할 것이니 주사위를 굴리는 횟수는 기하 분포를 따르게 돼어 기댓값은 확률의 역수가 된다
- 따라서 $N$개의 초밥을 먹기 위해 주사위를 굴리는 횟수의 기댓값은 $\frac{N}{N} + \frac{N}{N - 1} + \cdots + \frac{N}{1}$이다. 이건 사실 백준 쿠폰 문제와 동일하다
- 문제는 모든 접시에 $1$개의 초밥만 있는 게 아니라는 것이다. $2$개일 수도 있고 $3$개일 수도 있다. 일단 문제를 쉽게 만들고자 모든 접시에 초밥은 $1$개 또는 $2$개만 있다고 하자
- 처음에 주사위를 굴리면 $1$의 확률로 초밥을 먹는다. 이때 초밥이 $1$개 있는 접시일 수도 있고 $2$개 있는 접시일 수도 있다. 만약 운 좋게 $2$개 있는 접시를 골랐다면 다음번에도 $1$의 확률로 초밥을 먹을 수 있다. 그게 아니라면 $N-1$개의 초밥만 남아있으므로 $\frac{N - 1}{N}$의 확률로 초밥을 먹을 수 있다
- 즉, 주사위를 굴려 나온 번호의 접시에 초밥이 몇 개 있냐에 따라 다음에 초밥을 먹을 수 있는 확률이 달라진다
- 이를 추적하자. 초밥이 $1$개 있는 접시의 개수를 $x_1$이라 하고 $2$개 있는 접시의 개수를 $x_2$라 하고 $\operatorname{dp}[x_1][x_2]$를 모든 초밥을 먹기 위해 주사위를 굴리는 횟수의 기댓값이라 하자
- 초밥이 있는 접시를 고를 확률은 $\frac{x_1 + x_2}{N}$이다. 이때 초밥이 $1$개 있는 접시를 고를 확률은 $\frac{x_1}{x_1 + x_2}$이고 $2$개 있는 접시를 고를 확률은 $\frac{x_2}{x_1 + x_2}$이다
- 우선 초밥이 있는 접시를 고르고자 기댓값에 해당하는 $\frac{N}{x_1 + x_2}$번만큼 주사위를 굴려야 한다. 그리고 초밥이 몇 개 있는 접시냐에 이후 기댓값이 달라진다. 이때 초밥이 $2$개 있는 접시를 고르면 해당 접시엔 $1$개만 남게 되므로 초밥이 $1$개 있는 접시의 개수가 $1$ 증가함에 유의하자
- 따라서 $\operatorname{dp}[x_1][x_2] = \frac{N}{x_1 + x_2} + \frac{x_1}{x_1 + x_2} \cdot \operatorname{dp}[x_1 - 1][x_2] + \frac{x_2}{x_1 + x_2} \cdot \operatorname{dp}[x_1 + 1][x_2 - 1]$이 성립한다
- 이를 접시에 초밥이 최대 $3$개 있는 것까지 확장하면 점화식은 다음과 같다
- $\operatorname{dp}[x_1][x_2][x_3] = \frac{N}{x_1 + x_2 + x_3} + \frac{x_1}{x_1 + x_2 + x_3} \cdot \operatorname{dp}[x_1 - 1][x_2][x_3] + \frac{x_2}{x_1 + x_2 + x_3} \cdot \operatorname{dp}[x_1 + 1][x_2 - 1][x_3] + \frac{x_3}{x_1 + x_2 + x_3} \cdot \operatorname{dp}[x_1][x_2 + 1][x_3 - 1]$
- 초깃값으로 $\operatorname{dp}[0][0][0] = 0$이며 $x_1 > 0, x_2 = 0, x_3 = 0$인 경우 쿠폰 문제와 동일하게 처리하자
- 전체 알고리즘의 시간 복잡도와 공간 복잡도는 $O\left(N^3\right)$이며 $x_1 + x_2 + x_3 = N$이므로 $N^3$의 계수가 작아 제한 시간 안에 동작한다
def eat_sushi(x1, x2, x3, n, dp):
if dp[x1][x2][x3] >= 0:
return dp[x1][x2][x3]
if x2 == 0 and x3 == 0:
dp[x1][x2][x3] = n * compute_hamonic_number(x1)
return dp[x1][x2][x3]
s = x1 + x2 + x3
t = n
if x1 > 0:
t += x1 * eat_sushi(x1 - 1, x2, x3, n, dp)
if x2 > 0:
t += x2 * eat_sushi(x1 + 1, x2 - 1, x3, n, dp)
if x3 > 0:
t += x3 * eat_sushi(x1, x2 + 1, x3 - 1, n, dp)
t /= s
dp[x1][x2][x3] = t
return t
def compute_hamonic_number(n):
return sum(1 / k for k in range(1, n + 1))
def solution():
N = int(input())
array = list(map(int, input().split()))
dp = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0][0] = 0
xs = [0] * 3
for a in array:
xs[a - 1] += 1
x1, x2, x3 = xs
answer = eat_sushi(x1, x2, x3, N, dp)
print(answer)
solution()
- $\operatorname{dp}[i]$를 본인 차례에 돌이 $i$개 남았을 때 게임의 승패 여부라고 하자 ($1$이면 승리, $0$이면 패배)
- 더미에 최소 $a_1$개의 돌이 남아있어야 돌을 제거할 수 있므로 초깃값으로 $\operatorname{dp}[0] \sim \operatorname{dp}[a_1 - 1]$은 $0$이다
- 현재 차례에 몇 개의 돌을 제거해도 남은 돌의 개수가 $\text{P}$-포지션에 해당한다면 현재 차례의 돌의 개수는 $\text{N}$-포지션이다. 반대로 현재 차례에서 $\text{N}$-포지션을 만들 수 있는 방법이 적어도 하나 존재하면 현재 차례의 돌의 개수는 $\text{P}$-포지션이다 ($\text{P}$-포지션은 승리, $\text{N}$-포지션은 패배). 따라서 점화식은 다음과 같다
- $\operatorname{dp}[i] = \begin{cases}
\\
\, 0, & \text{if } i < a_1 \\[1.3em]
\, 0, & \text{if } \displaystyle\prod_{1\le j \le N, \, i \ge a_j} \operatorname{dp}[i - a_j] = 1 \\[0.5em]
\, 1, & \text{if } \displaystyle\prod_{1\le j \le N, \, i \ge a_j} \operatorname{dp}[i - a_j] = 0
\end{cases}$
- $\operatorname{dp}[K]$가 $1$이면 Taro가 승리하고 $\operatorname{dp}[K]$가 $0$이라면 Jiro가 승리한다. 전체 알고리즘의 시간 복잡도는 $K=10^5$이고 $a_N = N$인 최악의 경우 $O(NK)$이다
def solution():
N, K = map(int, input().split())
A = list(map(int, input().split()))
dp = [0] * (K + 1)
for i in range(A[0], K + 1):
if all(dp[i - a] for a in A if i - a >= 0):
dp[i] = 0
else:
dp[i] = 1
answer = "First" if dp[K] else "Second"
print(answer)
solution()
- 난생처음 보는 유형이다 (꽤 흥미로움). 각 플레이어의 목적이 서로 다름을 고려해줘야 한다
- $\operatorname{dp}[i][j]$를 $a_i \sim a_j$만 존재하는 상황에서 각 플레이어가 최적으로 플레이 했을 때 게임 종료시의 $X-Y$라고 하자. $j-i+1$은 구간의 길이 $l$로 만약 $N$과 $l$의 홀짝성이 같다면 Taro 차례이고 다르다면 Jiro 차례이다
- 누구 차례냐에 따라 목적이 다르기에 상태 전이가 달라진다. Taro는 $X-Y$를 최대화하고 Jiro는 $X-Y$를 최소화한다. 이를 고려한 점화식은 다음과 같다
- $\operatorname{dp}[i][j] = \begin{cases}
\, \max(\operatorname{dp}[i + 1][j] + a_i , \operatorname{dp}[i][j - 1] + a_j) & \text{if } N - l \text{ is even} \\ \\
\, \min(\operatorname{dp}[i + 1][j] - a_i , \operatorname{dp}[i][j - 1] - a_j) & \text{if } N - l \text{ is odd}
\end{cases}$
- 단, $l = j - i + 1$이고 초깃값은 다음과 같다. $\operatorname{dp}[i][i] = \begin{cases}
\, a_i & \text{if } N \text{ is odd} \\
\, -a_i & \text{if } N \text{ is even}
\end{cases}$
- 정답은 $\operatorname{dp}[1][N]$이며 전체 알고리즘의 시간 복잡도는 $O\left(N^2\right)$이다. 바텀업으로 구현할 때 구간의 길이가 작은 순으로 탐색해야 함을 잊지 말자
def solution():
N = int(input())
array = list(map(int, input().split()))
dp = [[None] * N for _ in range(N)]
for i in range(N):
if N % 2 == 1:
dp[i][i] = array[i]
else:
dp[i][i] = -array[i]
for length in range(2, N + 1):
for i in range(N - length + 1):
j = i + length - 1
if (N - length) % 2 == 0:
dp[i][j] = max(dp[i + 1][j] + array[i], dp[i][j - 1] + array[j])
else:
dp[i][j] = min(dp[i + 1][j] - array[i], dp[i][j - 1] - array[j])
answer = dp[0][N - 1]
print(answer)
solution()
- $\operatorname{dp}[i][k]$를 $i$번째 아이까지 $k$개의 사탕을 나누어줄 수 있는 경우의 수로 정의하자
- $\operatorname{dp}[i][k] = \sum\limits_{x=0}^{\min(a_i, k)}\operatorname{dp}[i - 1][k - x]$이고 $a_i$는 최대 $K$이므로 총 $O\left(NK^2\right)$이다. 이때 $N$은 최대 $100$, $K$는 최대 $10^5$이므로 시간 초과이다
- 그런데 정의에 의해 $\operatorname{dp}[i][k] = \operatorname{dp}[i][k - 1] - \operatorname{dp}[i - 1][k - a_i - 1] + \operatorname{dp}[i - 1][k]$가 성립한다 (나열해보면 당연한데 알아차리기 은근 어려웠다)
- 따라서 $O(NK)$에 문제를 해결할 수 있다. 정답은 $\operatorname{dp}[N][K]$이며 초깃값으로 $\operatorname{dp}[0][0] = 1$이다
def solution():
mod = 10**9 + 7
N, K = map(int, input().split())
array = list(map(int, input().split()))
dp_prev = [0] * (K + 1)
dp_prev[0] = 1
for a in array:
dp_curr = [0] * (K + 1)
for k in range(K + 1):
dp_curr[k] = dp_curr[k - 1] + dp_prev[k]
if k - 1 >= a:
dp_curr[k] -= dp_prev[k - a - 1]
dp_curr[k] %= mod
dp_prev = dp_curr
answer = dp_prev[K]
print(answer)
solution()
- 파일 합치기 문제와 동일한 웰노운 구간 DP 문제이다 (처음 접하면 어렵다)
- 슬라임을 합칠 때 인접한 두 슬라임만 합칠 수 있다. 따라서 임의의 합쳐진 슬라임은 연속된 구간의 슬라임을 합친 꼴이 된다
- $\operatorname{dp}[i][j]$를 $i$번째 슬라임부터 $j$번째 슬라임을 하나의 슬라임으로 합칠 때 발생하는 비용의 최솟값이라 하자. 그럼 점화식은 다음과 같다
- $\operatorname{dp}[i][j] = \sum\limits_{l = i}^{j} a_l + \min\limits_{i \le k < j}\{\operatorname{dp}[i][k] + \operatorname{dp}[k + 1][j]\}$
- 초깃값으로 $\operatorname{dp}[i][i] = 0$이다
- 누적 합을 $O\left(N^2\right)$에 전처리 해두면 $i$번째 슬라임부터 $j$번째 슬라임을 합친 슬라임의 크기를 $O(1)$에 알 수 있다. 임의의 $\operatorname{dp}[i][j]$를 결정하는 게 $O(N)$이며 가능한 $(i,j)$ 상태의 개수는 $O\left(N^2\right)$이므로 전체 알고리즘의 시간 복잡도는 $O\left(N^3\right)$이다
- 바텀업 구현시 길이($=j-i+1$)를 $2$부터 $N$까지 오름차순으로 순회해야 됨에 주의하자. 정답은 $\operatorname{dp}[1][N]$이다
from itertools import accumulate
def solution():
inf = float("inf")
N = int(input())
array = list(map(int, input().split()))
prefix_sums = [*accumulate(array, initial=0)]
dp = [[inf] * N for _ in range(N)]
for i in range(N):
dp[i][i] = 0
for length in range(2, N + 1):
for i in range(N - length + 1):
j = i + length - 1
size = prefix_sums[j + 1] - prefix_sums[i]
for k in range(i, j):
dp[i][j] = min(dp[i][k] + dp[k + 1][j] + size, dp[i][j])
answer = dp[0][N - 1]
print(answer)
solution()
- $1$번부터 $i-1$번 남자까지 매칭됐다고 했을 때 이제 $i$번 남자와 적합한 여자를 매칭시켜보자. 현재까지 매칭된 여자 상태의 비트마스크를 $b$라 할 때 여태까지 매칭된 쌍의 수는 $i-1$이므로 $\operatorname{bitcount(b)} = i-1$인 경우만 고려해야 한다 ($\operatorname{bitcount(b)}$는 $b$의 $1$ 개수). 따라서 $0$부터 $2^N - 2$까지의 가능한 $b$에 대해 $i = \operatorname{bitcount(b)} + 1$로 설정하면 된다
- $\operatorname{dp}[b]$를 여자 매칭 상태의 비트마스크가 $b$일 때 가능한 매칭 경우의 수라고 하자. $i$번 남자와 적합한 여자 번호가 $i_1, \dots, i_m$일 때 $b$의 $i_k$번째 비트가 이미 $1$이라면 그 여자와는 매칭시킬 수 없다. 그렇지 않다면 매칭 가능하므로 $\operatorname{dp}[b \operatorname{|} 2^{i_k - 1}]$에 $\operatorname{dp}[b]$를 더해주자 (단, $\operatorname{|}$는 bitwise OR)
- 초깃값으로 $\operatorname{dp}[0] = 1$이며 정답은 $\operatorname{dp}[2^N - 1]$이다
- 전체 알고리즘의 시간 복잡도는 $O\left(N 2^N\right)$이며 공간 복잡도는 $O\left(2^N\right)$이다
def solution():
mod = 10**9 + 7
N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
max_bitmask = 2**N - 1
dp = [0] * (max_bitmask + 1)
dp[0] = 1
for b in range(max_bitmask):
if dp[b] == 0:
continue
i = bin(b).count("1") + 1
compatible = matrix[i - 1]
for j in range(N):
b_next = b | (1 << j)
if not compatible[j] or b_next == b:
continue
dp[b_next] += dp[b]
dp[b_next] %= mod
answer = dp[max_bitmask]
print(answer)
solution()
- 루트 노드를 $1$번 노드로 칭하자 (어차피 동일한 트리이므로 뭐든 상관없다)
- $\operatorname{dp}_b[u]$를 $u$번 노드가 검은색일 때 가능한 서브트리의 경우의 수라고 하자 ($\operatorname{dp}_w[u]$는 $u$가 흰색인 경우)
- $u$번 노드가 검은색이면 그의 자식 노드는 모두 흰색이어야 한다. 자식끼리는 인접해 있지 않으니 색깔은 서로 독립이다. 따라서 $v_i$를 $u$의 $i$번째 자식이라 할 때 $\operatorname{dp}_b[u] = \prod\limits_{i=1}^{k} \operatorname{dp}_w[v_i]$이다 ($u$번 노드의 자식은 총 $k$개로 가정)
- 반대로 $u$번 노드가 흰색이면 자식 노드의 색깔은 상관없으므로 $\operatorname{dp}_w[u] = \prod\limits_{i=1}^{k} (\operatorname{dp}_b[v_i] + \operatorname{dp}_w[v_i])$이다. 초깃값으로 $u$번 노드가 리프 노드인 경우 $\operatorname{dp}_b[u] = 1, \operatorname{dp}_w[u] = 1$이다
- 정답은 $\operatorname{dp}_b[1] + \operatorname{dp}_w[1]$이며 이를 $10^9+7$로 나눈 나머지를 출력해야 함을 잊지 말자
import sys
sys.setrecursionlimit(10**5 + 2)
def dfs(tree, node, parent, dp_black, dp_white, mod):
dp_black[node] = 1
dp_white[node] = 1
for child in tree[node]:
if child == parent:
continue
dfs(tree, child, node, dp_black, dp_white, mod)
dp_black[node] *= dp_white[child]
dp_black[node] %= mod
dp_white[node] *= (dp_black[child] + dp_white[child]) % mod
dp_white[node] %= mod
def solution():
N = int(input())
tree = [[] for _ in range(N + 1)]
for _ in range(N - 1):
x, y = map(int, input().split())
tree[x].append(y)
tree[y].append(x)
mod = 10**9 + 7
root, none = 1, 0
dp_black, dp_white = [0] * (N + 1), [0] * (N + 1)
dfs(tree, root, none, dp_black, dp_white, mod)
answer = (dp_black[root] + dp_white[root]) % mod
print(answer)
solution()
- $\operatorname{dp}[i]$를 $i$번째 꽃이 마지막으로 남아 있을 때 아름다움 합의 최댓값이라 하자. 남은 꽃들의 높이는 단조 증가여야 하므로 $\operatorname{dp}[i] = \max\limits_{1 \le j <i} \{\operatorname{dp}[i] \cdot I(h_j \le h_i)\} + a_i$가 성립한다
- 이를 단순하게 처리하면 $O\left(N^2\right)$이고 $N$이 최대 $2\times 10^5$이므로 TLE이다. 하지만 세그먼트 트리를 사용하면 최댓값 쿼리와 원소 갱신을 $O(\log N)$에 수행할 수 있어 총 $O(N \log N)$에 해결할 수 있다 (높이별로 아름다움 합의 최댓값을 저장하는 세그먼트 트리를 만든 뒤 스위핑하면 된다)
class SegmentTree:
def __init__(self, size_or_array, op, e):
self._op = op
self._e = e
is_int = isinstance(size_or_array, int)
n = size_or_array if is_int else len(size_or_array)
self._size = 1 << (n - 1).bit_length()
self._tree = [self._e] * (self._size << 1)
if not is_int:
self._build(size_or_array)
def _build(self, array):
for i, a in enumerate(array, start=self._size):
self._tree[i] = a
for i in range(self._size - 1, 0, -1):
self._tree[i] = self._op(self._tree[i << 1], self._tree[i << 1 | 1])
def get(self, index):
return self._tree[index + self._size]
def update(self, index, value):
i = index + self._size
self._tree[i] = value
while i > 1:
i >>= 1
self._tree[i] = self._op(self._tree[i << 1], self._tree[i << 1 | 1])
def query(self, left, right):
l = left + self._size
r = right + self._size
f_l = self._e
f_r = self._e
while l <= r:
if l & 1:
f_l = self._op(f_l, self._tree[l])
l += 1
if ~r & 1:
f_r = self._op(self._tree[r], f_r)
r -= 1
l >>= 1
r >>= 1
return self._op(f_l, f_r)
def solution():
N = int(input())
heights = list(map(int, input().split()))
beauties = list(map(int, input().split()))
tree = SegmentTree(N + 1, max, 0)
for h, a in zip(heights, beauties):
mx = tree.query(1, h)
tree.update(h, mx + a)
answer = tree.query(1, N)
print(answer)
solution()
- $\operatorname{dp}[i][j][d]$를 $i$번 정점이 source이고 $j$번 정점이 sink인 길이 $d$의 경로 개수로 정의하자. 그럼 점화식은 다음과 같다
- $\operatorname{dp}[i][j][d] = \sum\limits_{k=1}^{N}\operatorname{dp}[i][k][d - 1] \cdot a_{k, j}$, 이를 나이브하게 계산하면 $O\left(N^3 K\right)$이다
- 그런데 위 점화식은 행렬 곱셈의 정의와 같다 ($d=0$일 때 $\operatorname{dp}$는 단위 행렬). 따라서 $\operatorname{dp}[i][j][d] = G^{d}[i][j]$이며 행렬 제곱은 분할 정복을 이용해서 최악의 경우에도 $O\left(N^3 \log K\right)$에 계산할 수 있다
def matpow(A, power, mod):
if power == 0:
return I
if power == 1:
return matmul(A, I, mod)
half = matpow(A, power // 2, mod)
A_p = matmul(half, half, mod)
if power % 2 == 1:
A_p = matmul(A_p, A, mod)
return A_p
def matmul(A, B, mod):
n, m = len(A), len(B[0])
matrix = [[0] * m for _ in range(n)]
for i, row_vec in enumerate(A):
for j, col_vec in enumerate(zip(*B)):
matrix[i][j] += dot_product(row_vec, col_vec) % mod
matrix[i][j] %= mod
return matrix
def dot_product(vec1, vec2):
return sum(map(lambda x, y: x * y, vec1, vec2))
def solution():
global I
mod = 10**9 + 7
N, K = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(N)]
I = [[0] * i + [1] + [0] * (N - i - 1) for i in range(N)]
matrix = matpow(G, K, mod)
answer = sum(map(sum, matrix)) % mod
print(answer)
solution()
- 브루트 포스는 $O(K \log K)$로 안 해봐도 시간 초과이다. 대신 자릿수 관점에서 접근해보자
- 맨 앞자리부터 $i$번째 자리(선행 $0$ 포함)까지 확정됐을 때 수가 $K$보다 작아졌는지 여부(이후 자리와 관계없이)와 $D$로 나눈 나머지가 같다면 $i+1$번째 자리 입장에선 동일한 수로 취급할 수 있다
- 따라서 이를 메모이제이션 하자. 참고로 앞자리부터 고려하는 이유는 뒷자리부터 고려하면 앞의 자리에 따라 $K$보다 커질 수 있기 때문에 이후 자리를 고려하는 게 까다롭기 때문이다
- $f(i,\, r,\, \text{is\_less})$를 $i$번째 자리까지의 자릿수 합을 $D$로 나눈 나머지가 $r$이고 $K$보다 작은지 여부가 $\text{is\_less}$일 때 이를 만족하는 수의 개수로 정의하자. 그럼 점화식은 다음과 같다
- $f(i + 1,\, (r + d) \bmod D,\, \text{is\_less} \lor (d < K[i + 1])) \mathrel{+}= f(i,\, r,\, \text{is\_less})$. $\text{is\_less} = \text{T}$이면 $d=0\sim 9$이고 $\text{is\_less} = \text{F}$이면 $d=0\sim K[i + 1]$이다
- base case로 $f(0,\, 0,\, \text{F})=1$이며 $f(\operatorname{digit}(K), 0, \text{T}) + f(\operatorname{digit}(K), 0, \text{F}) - 1$이 정답이 된다. $f(\operatorname{digit}(K), 0, \text{F})$는 $K$가 조건을 만족하는지 확인하는 용도이고 $1$을 빼는 건 $0$ 때문이다
- $10$진법을 사용하므로 전체 알고리즘의 시간 복잡도는 $O(10D\log K)$이다. $10^9 + 7$로 나눈 나머지를 출력해야 함에 유의하자
from itertools import product
def count(K, D, mod):
n_digits = len(K)
dp_prev = [[0] * 2 for _ in range(D)]
dp_prev[0][0] = 1
for i in range(n_digits):
k_i = int(K[i])
dp_curr = [[0] * 2 for _ in range(D)]
for r, is_less in product(range(D), range(2)):
c = dp_prev[r][is_less]
if c == 0:
continue
limit = 9 if is_less else k_i
for d in range(limit + 1):
n_r = (r + d) % D
n_is_less = is_less or d < k_i
dp_curr[n_r][n_is_less] += c
dp_curr[n_r][n_is_less] %= mod
dp_prev = dp_curr
return (sum(dp_prev[0]) - 1) % mod
def solution():
mod = 10**9 + 7
K = input().rstrip()
D = int(input())
answer = count(K, D, mod)
print(answer)
solution()
- 문제를 읽어보면 이것도 DP인가 하는 생각이 든다 (어떻게 풀어요?). 일단 브루트 포스는 $O(N \cdot N!)$이라 답이 없다
- 상태 공간을 한정시키자. 여태까지 사용한 수와 마지막 수가 같다면 확장하는 경우의 수도 같다. 그럼 비트마스크 DP로 풀 수 있지만 $N$이 너무 커서 답이 없는 건 마찬가지다
- 여기서 중요한 관찰이 하나 필요한데 $s$는 대소 관계만 명시할 뿐이지 수를 특정하는 건 아니라는 것이다. 즉, 주어지는 수열이 서로 다른 $N$개의 원소이기만 하면 동일한 $s$에 대해 경우의 수도 동일하다. 이에 착안해 문제를 풀자
- $i$번째 원소로 무엇을 사용할지 정하려면 $i-1$번째 원소가 무엇인지 알아야 한다. 예컨대 $p_{i-1} < p_i$라고 해보자. $p_{i-1}$이 뭔지 알아야 $p_{i-1}$보다 크면서 사용하지 않은 수 중 하나를 $p_i$로 정할 수 있다
- 근데 $p_{i-1}$을 알고자 하는 이유는 사용 가능한 $p_i$의 개수를 확정하기 위함이다. 따라서 꼭 $p_{i-1}$을 알 필요 없이 $p_{i-1}$보다 크면서 사용하지 않은 수의 개수만 알아도 충분하다
- $\operatorname{dp}[i][k]$를 수열의 $i$번째 원소까지 결정됐고 $p_i$보다 큰 수가 $k$개 남아있는 부분 수열의 개수로 정의하자. $p_{i-1} < p_{i}$이고 $p_{i-1}$보다 큰 수가 $s$개 남았다면 $p_i$로 선택 가능한 수는 $s$개이며 그중 작은 순으로 $x$번째 수를 선택했다면 $p_i$보다 큰 수는 $s - x$개 남게 된다
- 참고로 $i$번째 원소까지 고려했고 $p_{i-1}$보다 큰 수가 $s$개 남았다면 작은 수는 $N - i - s + 1$개 남아있다. 따라서 남아있는 큰 수의 개수만 추적해도 충분하며 이를 고려해 점화식을 정의하면 다음과 같다
- $\operatorname{dp}[i][k] = \begin{cases}
\, \sum\limits_{s=k+1}^{N - i + 1}\operatorname{dp}[i - 1][s], & \text{if } p_{i-1} < p_i \\
\, \sum\limits_{s=0}^{k}\operatorname{dp}[i - 1][s], & \text{if } p_{i-1} > p_i
\end{cases}
\qquad (0 \le k \le N - i)$
- 점화식이 은근 까다로워서 좀 더 자세히 알아보자. 기본적으로 $0 \le k \le N - i$를 만족해야 한다 (남은 수가 최대 $N-i$개)
- $p_{i-1} < p_i$인 경우 $p_{i}$보다 큰 수는 $p_{i-1}$보다 크다. 그리고 $p_{i-1}$보다 큰 수 중 하나를 $p_i$로 고를 것이므로 $s \ge k + 1$를 만족해야 한다. $i-1$번째 원소까지 확정된 시점에서 남은 수는 $N-i+1$개이므로 $s$는 최대 $N-i+1$이다. 따라서 $k + 1 \le s \le N-i+1$이다
- $p_{i-1} > p_i$인 경우 $p_{i-1}$보다 큰 수는 $p_{i}$보다 크다. 따라서 $s > k$라면 모순이다. 기본적으로 $s$는 $0$ 이상, $N-i+1$ 이하이므로 제약을 적용하면 $0 \le s \le k$이다
- base case로 $\forall k \in \{0,1,\dots, N-1\},\;\operatorname{dp}[1][k] = 1$이고 그 외는 $0$이다
- 상태 공간의 크기가 $O\left(N^2\right)$이고 각 상태 전이에 $O(N)$이라 총 $O\left(N^3\right)$이다. 처음에 비하면 장족의 발전이지만 $N$이 최대 $3000$이라 TLE이다
- DP를 정방향으로 정의하면 편하지만 그렇지 않고 역방향으로 정의한 이유는 누적 합 테크닉을 사용해 시간 복잡도를 줄이기 위함이다 (전이가 연속된 상태와 이루어짐에 착안)
- $\operatorname{dp}[i]$의 모든 상태는 $\operatorname{dp}[i - 1]$의 구간 합으로 정의된다. 따라서 매 $i$마다 누적 합을 $O(N)$에 전처리 해두면 상태 전이를 $O(1)$에 수행할 수 있으므로 전체 알고리즘의 시간 복잡도는 $O\left(N^2\right)$이 된다
from itertools import accumulate
def solution():
mod = 10**9 + 7
N = int(input())
s = input().rstrip()
dp_prev = [1] * N + [0]
for i in range(2, N + 1):
dp_curr = [0] * (N + 1)
p = [*accumulate(dp_prev)]
is_less_symbol = s[i - 2] == "<"
for k in range(N - i + 1):
if is_less_symbol:
count = p[N - i + 1] - p[k]
else:
count = p[k]
dp_curr[k] = count % mod
dp_prev = dp_curr
answer = dp_prev[0]
print(answer)
solution()
- $\operatorname{dp}[i]$를 개구리가 $i$번 돌까지 오는 데 필요한 비용의 최솟값으로 정의하자. 그럼 점화식은 다음과 같다
- $\operatorname{dp}[i] = \min\limits_{j < i} \{\operatorname{dp}[j] + (h_j - h_i)^2 + C\}$. 이를 나이브하게 계산하면 $O\left(N^2\right)$으로 시간 초과이다
- 식을 정리해보자. $\operatorname{dp}[i] = \min\limits_{j < i} \{-2h_j h_i + h^2_j + \operatorname{dp}[j]\} + h^2_i + C$인데 문제 조건에 따라 $h$가 단조성을 띄므로 컨벡스 헐 트릭을 이용하여 $O(N)$에 해결할 수 있다 (기울기는 단조감소, 쿼리는 단조증가)
- $\operatorname{dp}[i]$를 계산함에 있어 $h_i$를 $x$로 치환해서 생각해보자. 그럼 $\min\limits_{j < i} \{-2h_j h_i + h^2_j + \operatorname{dp}[j]\}$ 부분은 $y = -2h_j x + h^2_j + \operatorname{dp}[j]$ 꼴의 일차 함수 중에서 $x$에 $h_i$를 대입했을 때 $y$가 가장 작은 걸 찾는 것과 같다
- 원래라면 최솟값을 찾는 데 $O(N)$이지만 $h$가 단조성을 띄어 이분 탐색으로 $O(\log N)$에 찾는 게 Convex Hull Trick이다 (최솟값을 가지는 직선들의 형태가 컨벡스 헐처럼 생겨서 이런 이름이 붙었다고 한다~). 이 문제에선 기울기와 쿼리 모두 $h$의 단조함수라 $O(\log N)$이 아닌 $O(1)$에 최솟값을 찾을 수 있다 (정확히는 $N$개의 쿼리를 처리하는 데 $O(N)$이 걸려서 쿼리당 amortized $O(1)$이다)
- (기울기, 절편)을 원소로 가지는 deque을 관리하자. 첫 번째 직선이 최소 $y$를 가지도록 관리할 것이다. 새로운 $h_i$가 입력되면 첫 번째 직선과 두 번째 직선을 비교해서 첫 번째 직선의 $y$가 더 작을 때까지 popleft를 수행하자 (쿼리가 단조성을 띄므로 가능, 한 번 최소가 아니게 되면 앞으로도 최소가 아님)
- 이제 첫 번째 직선을 가지고 $\operatorname{dp}[i]$를 계산한 뒤 기울기가 $-2h_i$이고 절편이 $h^2_i + \operatorname{dp}[i]$인 직선을 deque에 추가하자. 이때 기울기가 단조감소함에 집중하자. 현재 deque에 직선이 $k$개 있을 때 $k-1$번째 직선과 $k$번째 직선의 교점의 $x$ 좌표를 $x_{k-1,k}$와 같이 표현할 때 만약 $x_{k-1, i} \le x_{k-1, k}$라면 $k$번째 직선은 더 이상 필요하지 않다. 왜냐하면 쿼리가 $x_{k-1,k}$보다 작은 경우 최소 $y$를 계산하는 데 $k-1$번째 직선을 사용했었고 그렇지 않다면 이제 새로 들어온 $i$번 직선을 사용할 것이기 때문이다 (생각해보면 당연함)
- 모든 직선은 $1$번만 deque에 추가되고 최대 $1$번만 삭제되므로 Convex Hull Trick을 사용해 $O(N)$에 문제를 해결할 수 있다
from collections import deque
def f(line, x):
m, b = line
return m * x + b
def solution():
inf = float("inf")
N, C = map(int, input().split())
h = list(map(int, input().split()))
dp = [inf] * N
dp[0] = 0
lines = deque([(-2 * h[0], h[0]**2)])
for i in range(1, N):
h_i = h[i]
while len(lines) >= 2 and f(lines[1], h_i) <= f(lines[0], h_i):
lines.popleft()
dp[i] = f(lines[0], h_i) + h_i**2 + C
m_i = -2 * h_i
b_i = h_i**2 + dp[i]
while len(lines) >= 2:
m_1, b_1 = lines[-2]
m_2, b_2 = lines[-1]
if (m_1 - m_2) * (b_i - b_1) > (m_1 - m_i) * (b_2 - b_1):
break
lines.pop()
lines.append((m_i, b_i))
answer = dp[N - 1]
print(answer)
solution()
| No. | 문제 | 날짜 |
|---|---|---|
| 1 | A | 2026-08-03 |
| 2 | B | 2026-08-03 |
| 3 | C | 2026-08-03 |
| 4 | D | 2026-08-03 |
| 5 | E | 2026-08-03 |
| 6 | G | 2026-08-03 |
| 7 | H | 2026-08-03 |
| 8 | I | 2026-08-03 |
| 9 | K | 2026-08-04 |
| 10 | F | 2026-08-06 |
| 11 | N | 2026-08-06 |
| 12 | O | 2026-08-06 |
| 13 | P | 2026-08-10 |
| 14 | L | 2026-08-11 |
| 15 | J | 2026-08-12 |
| 16 | Q | 2026-09-19 |
| 17 | M | 2026-09-19 |
| 18 | R | 2026-09-20 |
| 19 | S | 2026-09-20 |
| 20 | Z | 2026-09-28 |
| 21 | T | 2026-09-29 |