Atcoder Educational DP Contest 풀이 요약

A. Frog 1

문제 요약: 다음 칸 또는 그 다음 칸으로 점프할 수 있고, 그때 비용은 높이 차일때 칸 $1$에서 칸 $N$으로 이동하는 최소 비용

풀이:

점프 하나를 간선 하나로 해석하면 dp 점화식 ```dp[i] = min(dp[i-1] + abs(h_{i}-h_{i-1}), dp[i-2] + abs(h_{i}-h_{i-2}))```를 얻을 수 있습니다. top down으로 구현하면 $i-2$가 음수가 될 수 있음에 유의해야 하며 bottom up으로 구현하면 $N$보다 큰 padding을 마련해야 합니다. 

 

B. Frog 2

문제 요약: A번 문제에서 한 번에 점프할 수 있는 거리가 최대 $K$인 문제

풀이:

A와 동일하게 해결하면 됩니다. 업데이트 간선의 개수는 $NK$개입니다.

 

C. Vacation

문제 요약: $i$번째 날에 A,B,C를 하면 얻을 수 있는 행복도는 각각 $a_i, b_i, c_i$이고 이틀 연속으로 같은 행동을 할 수 없을 때 행복도의 최댓값

풀이:

```dp[i][j]```를 $i$번째 날에 $j$번 일을 했을 때의 행복도의 최댓값을 관리하게 하면 ```dp[i]```는 ```dp[i-1]```에만 의존하므로 $i$를 증가시키면서 업데이트하면 됩니다. 업데이트 간선의 개수는 $6(N-1)$개입니다.

슬라이딩 윈도우를 통해 해결할 수도 있습니다.

 

D. Knapsack 1

문제 요약: 비용이 $w$이고 가치가 $v$인 물건을 비용이 $W$ 이하가 되게 고를 때 가치 합의 최대

풀이:

일반적인 0-1 knapsack 문제는 다항 시간 내에 풀 수 없음이 알려져 있습니다. 하지만 $W$의 값은 다항 크기가 아니므로 이를 이용해야 합니다.

```dp[i][j]```를 $1$번 물건부터 $i$번 물건까지 이용해 비용이 $i$인 선택을 할 때 최대 가치라고 하면 비용이 $w$이고 가치가 $v$인 물건을 추가로 선택하면 ```dp[i+1][j+w]```에 ```dp[i][w]+v```인 경우가 추가되는 것과 같습니다. 이를 ```max```로 관리하면 ```dp[N]```에 전체 최적해를 가지게 됩니다. 업데이트 간선의 개수는 최대 $WN$개입니다. 한편 ```dp[i]```는 ```dp[i-1]```에만 의존합니다. 따라서 첫 번째 인덱스를 슬라이딩 윈도우로 관리할 수도 있고, $j$ 인덱스의 업데이트 방향이 증가하는 방향이므로 큰 인덱스부터 관리하면 크기 $W$인 배열 하나만으로 해결할 수 있습니다.

 

E. Knapsack 2

문제 요약: 비용이 $w$이고 가치가 $v$인 물건을 비용이 $W$ 이하가 되게 고를 때 가치 합의 최대

풀이:

D번과 다른 점은 $W$의 상한이 커진 대신 $v$의 하한이 작아졌습니다. 파라메트릭 서치와 같은 테크닉으로 dp 식을 뒤집어 생각하면 D번에서는 어떤 용량을 가지는 가치의 최댓값을 구했다면 여기서는 어떤 가치를 가지는 용량의 최솟값을 관리하면 될 것 같습니다. 

 

같은 방식으로 ```dp[i][j]```를 $i$번 물건까지 사용해 가치가 $j$가 되게 하는 조합의 용량 합 최소값으로 두면 ```dp[i+1][j+v]```에 ```dp[i][j]+w```를 업데이트하는 것과 같고 min 업데이트를 이용해 구할 수 있습니다. ```dp[0][j]```에서 $j$가 0이 아니면 불가능하므로 min의 항등원인 무한대로 초기화해서 구해야 함에 유의해야 합니다. 마찬가지로 업데이트 간선의 개수는 최대 $N\sum v$이고 $i$의 의존성을 이용해 크기 $\sum v$인 배열만으로 해결할 수 있습니다.

 

F. LCS

문제 요약: 두 문자열의 최장 공통부분수열

풀이:

두 문자열의 길이가 각각 $i$,$j$인 접두사의 LCS를 구하는 dp를 구현하면 됩니다. 이는 각각 $i$,$j$번째 문자를 추가하는 경우로, 두 문자가 같으면 ```dp[i][j] = dp[i-1][j-1]+1```, 다르면 ```dp[i][j] = max(dp[i-1][j], dp[i][j-1])```임을 이용하면 격자 모양의 dag를 얻을 수 있습니다. 업데이트 간선의 개수는 최대 $2|s||t|$개 있습니다.

 

G. Longest Path

문제 요약: Unweighted directed acyclic graph에서 가장 긴 경로의 길이

풀이:

dp 식을 바로 써보면 ```dp[v] = max(dp[u]+1: (u,v) \in E)```입니다. 1번 정점에서 출발하는 것이 고정되어 있으므로 $O(M)$에 해결할 수 있습니다. connected component에서 ```E>=V-1```임을 이용하면 $O(N+M)$으로 쓰지 않아도 됨을 알 수 있습니다.

 

H. Grid 1

문제 요약: 장애물이 있는 격자에서 수직인 두 방향만 이용해서 이동할 수 있는 경우의 수

풀이:

이동 가능한 방향으로 간선을 그리면 dag를 쉽게 얻을 수 있습니다. 어떤 칸에 도달하기 위해서 직전에 방문했어야 하는 칸은 많아야 두 개입니다. 직전에 방문했어야 하는 두 칸에 도착하는 경로의 수를 각각 알고 있으면 두 경로 개수의 합이 이 칸에 도착하는 경로의 수입니다. 업데이트 간선의 개수는 최대 $2HW$입니다.

 

I. Coins

문제 요약: 1이 나올 확률이 각각 $p$인 독립시행 결과 1이 나온 횟수마다의 확률

풀이:

확률론적으로 접근하면 확률이 각각 독립이므로 시행을 한 번 더 하는 경우를 각각 곱의 법칙으로 구할 수 있습니다. ```dp[i][j]```를 $i$번 시행까지 마쳤을 때 $j$번의 1이 나올 확률로 두면 확률 $p$인 시행을 추가하는 경우는 ```dp[i+1][j] = dp[i][j-1]*p + dp[i][j]*(1-p)```임을 확률론적으로 얻을 수 있습니다. dp 상태는 ```i>=j```인 경우 뿐이므로 업데이트 간선의 개수는 최대 ${N^{2}}$개입니다.

 

J. Sushi

문제 요약: $N$개의 접시 위에 초밥이 각각 최대 3개 올려져 있고 접시를 균등하게 뽑아 그 위에 초밥을 먹을 때 모두 먹기까지 시도 횟수의 기댓값

풀이:

모든 접시는 동등하므로 $0$,$1$,$2$,$3$개의 초밥이 올려진 접시의 개수를 각각 $a$,$b$,$c$,$d$라고 뭉뚱그려도 됩니다. 이때 $a+b+c+d$가 항상 $N$이므로 이중 세 개의 값만 가지고 현재 초밥의 개수를 명확하게 구현할 수 있습니다. 이제 ```dp[b][c][d]```를 이 상태에서 초밥을 모두 먹기까지 시도 횟수의 기댓값으로 두면 ```dp[b][c][d] = 1 + dp[b][c][d] * a/N + dp[b-1][c][d] * b/N + dp[b+1][c-1][d] * c/N + dp[b][c+1][d-1] * d/N```가 성립해야 한다는 것을 알 수 있습니다. 우변의 ```dp[b][c][d]```를 넘겨 정리하면 ```dp[b][c][d] = (1 + dp[b-1][c][d] * b/N + dp[b+1][c-1][d] * c/N + dp[b][c+1][d-1] * d/N) * N/a```가 되어 dp식을 얻은 것을 알 수 있습니다. acyclic인 것은 ```b+c+d```의 값이 작은 상태, ```b+c+d``` 값이 같고 ```d```값이 작은 상태, ```b+c+d```와 ```d``` 값이 같고 ```c```값이 작은 상태로 부터만 오기 때문에 세 값을 축으로 격자를 그려보면 알 수 있습니다.

업데이트 간선의 개수는 최대 $3(b+c+d)(c+d)d$입니다.

 

K. Stones

문제 요약: $K$개의 돌에서 $a$개의 돌을 지울 수 있을 때 승리하는 플레이어

풀이:

$a$가 양쪽 모두에게 동등하므로 내가 패배하는 상태를 상대에게 주는 것이 내가 승리하는 것과 동치입니다. ```dp[i]```를 남은 돌의 개수가 $i$일 때 승리할 수 있는지 여부를 담은 부울린 dp로 잡으면 ```dp[i] = not and(dp[i-a])```입니다. 업데이트 간선의 개수는 최대 $NK$개입니다.

 

L. Deque

문제 요약: 덱의 앞 또는 뒤에서 제거해 제거한 수 만큼 점수를 얻어 점수 차를 최대로 하는 게임을 할 때 최대 점수차

풀이:

$X-Y$를 최소화 하는 것과 $Y-X$를 최대화 하는 것이 완전히 동일합니다. 또한 $X+Y$가 고정되어 있으므로 $X$를 알면 $Y$를 알 수 있기 때문에 각자 자신의 점수를 최대화 하는 것과 동치임을 알 수 있습니다.

```dp[l][r]```을 $l$번째 원소부터 $r$번째 원소로 게임할 때 얻을 수 있는 $X-Y$의 최댓값으로 두면 ```dp[l][r] = max(a_l - dp[l+1][r], a_r - dp[l][r-1])```임을 확인할 수 있습니다. 하나를 제거한 상태가 되면 더 작은 게임을 선후공이 바뀐 채로 게임하는 것과 같기 때문에 상대가 최대화한 값의 부호를 뒤집어 내가 최대화한 값을 얻을 수 있습니다. 업데이트 간선 개수는 $O(N^2)$개입니다.

 

M. Candies

문제 요약: $N$명의 어린이에게 $K$개의 사탕을 나누어 줄 때 $a$ 이하로 나누어주는 경우의 수

풀이:

$K$의 값이 크지 않기 때문에 $K$를 인덱스로 잡아 dp하려는 생각을 할 수 있습니다. ```dp[i][j]```를 $i$번째 어린이까지 사탕을 나누어 주고 $j$개가 남는 경우의 수라고 하면 ```dp[i][j] = sum(dp[i-1][j+k]: j+k<=K)```가 됩니다. $dp[i]$가 $dp[i-1]$에만 의존하므로 누적 합을 이용한 정적 구간 합을 통해 $O(NK)$에 dp 테이블을 전부 채울 수 있습니다. dp 배열을 재배열하는 경우 점 업데이트 구간 쿼리를 쓰게 되므로 세그먼트 트리를 이용할 수도 있고, 이 경우 $O(NKlgK)$의 시간과 $O(K)$의 공간으로 해결할 수 있습니다.

 

N. Slimes

문제 요약: 이웃한 두 슬라임을 합칠 때 합친 크기 만큼 비용이 들 때 모든 슬라임을 합치는 데 드는 최소 비용

풀이:

이웃한 슬라임만 합칠 수 있으므로 구간을 합치는 것으로 이해해도 됩니다. ```dp[l][r]```을 $l$번째 슬라임부터 $r$번째 슬라임까지 합치는 최소 비용으로 두면 ```dp[l][r]```은 마지막 합치는 시행 직전 상태는 ```l<=i<r```인 $i$를 기준으로 두 구간이 나뉘어 있었어야 합니다. 따라서 ```dp[l][r] = min(dp[l][i] + dp[i+1][r] + sum(l:r): l<=i<r)```가 성립하고, 구간의 길이가 짧은 구간에서 긴 구간 방향으로 업데이트가 일어나므로 dag가 됨을 알 수 있습니다.

 

이때 업데이트 간선의 개수가 $O(N^3)$개이므로 조금 더 최적화가 필요합니다. 구간을 합치는 데 드는 비용이 구간합이기 때문에 ```sum(a:d)>=sum(b:c)```와 ```sum(a:d)+sum(b:c)>=sum(a:c)+sum(b:d)```가 성립하므로 Knuth optimization 또는 Knuth-Yao speedup이라는 테크닉을 이용할 수 있습니다. dp 식의 min 부분은 주어진 값 가운데 하나를 선택하는 함수인데, 구간 마다 선택한 인덱스를 ```opt[l][r]```이라 한다면 ```opt[l][r-1] <= opt[l][r] <= opt[l+1][r]```이 성립하고 dp값과 동시에 구해주면 같은 길이의 dp를 모두 구하는 데 드는 min 탐색 비용 합이 $O(N)$이므로 전체 $O(N^2)$에 해결할 수 있습니다. ```opt``` 값에 관한 부등식의 증명은 어렵기 때문에 생략합니다.

 

edit: $O(N^3)$으로도 해결할 수 있다고 합니다.

 

O. Matching

문제 요약: 남자 또는 여자로 이루어진 이분 그래프에서 완전 매칭의 개수

풀이:

완전 매칭의 개수를 세야 하므로 1번 남자는 어떤 여자와 매칭되어야 합니다. 1번 남자를 어떤 여자와 매칭시키고 나면 2번 남자 또한 다른 어떤 여자와 매칭되어야 합니다. 같은 방식으로 번호가 작은 남자부터 순서대로 여자를 매칭하는 경우의 수를 세줄 수 있습니다. ```dp[i][j]```를 $i$번 남자까지 매칭한 결과 매칭된 여자의 비트마스크 집합의 결과가 $j$인 경우의 수로 두면 $i$의 모든 간선에 대해서 업데이트해줄 수 있습니다. 이때 ```popcount(j) = i```가 성립하므로 $i$ 인덱스는 필요하지 않습니다. popcount가 작은 인덱스부터 큰 인덱스 순서대로 업데이트해주면 popcount가 가장 큰 인덱스에서 완전 매칭의 개수를 얻을 수 있습니다. 업데이트 간선의 개수는 최대 $O(N 2^N)$개입니다.

 

P. Independent Set

문제 요약: 트리에서 독립 집합의 개수

풀이:

임의의 루트를 잡으면 rooted tree를 얻을 수 있습니다. rooted tree에서 독립 집합은 루트를 포함하는 경우와 포함하지 않는 경우로 나눌 수 있습니다. 루트를 포함하는 경우 maximal subtree의 루트는 포함할 수 없음을 이용하면 루트를 포함하는 경우와 포함하지 않는 경우의 독립 집합의 개수를 따로 세 줘야 함을 알 수 있습니다.

```dp[i][0]```을 $i$를 루트로 하는 서브트리에서 루트를 포함하지 않는 독립 집합의 개수, ```dp[i][1]```를 루트를 포함하는 독립 집합의 개수로 두면 ```dp[i][0] = \prod (dp[j][1]+dp[j][0]: (i,j) \in E)```, ```dp[i][1] = \prod (dp[j][0]: (i,j) \in E)```임을 알 수 있습니다. 각 간선마다 dp 업데이트가 두 번씩 일어나므로 업데이트 간선의 개수는 $2N-2$개입니다.

 

Q. Flowers

문제 요약: $(h,a)$ 꼴의 순서쌍의 수열에서 $h$가 단조 증가하는 부분 수열의 $a$ 값의 최댓값

풀이:

$i$번째로 끝나는 부분 수열의 최댓값은 $i$ 이전에 끝나는 부분 수열의 최댓값 뒤에 $i$번째 $a$를 더한 값입니다. 이를 ```dp[i]```라고 두면 ```dp[i] = max(dp[j]: j<i, h[j]<h[i])+a[i]```가 됩니다. 이를 $h$가 작은 $i$부터 순서대로 업데이트해주면 두 번째 조건을 자동으로 만족하게 됩니다. $i$보다 작은 구간의 최댓값을 구하는 것은 세그먼트 트리를 이용해 $O(lgN)$에 구할 수 있기 때문에 총 $O(NlgN)$에 모든 dp 값을 구할 수 있습니다. $h$가 가장 작은 인덱스의 경우 0번째에 $h$와 $a$가 모두 0인 꽃을 먼저 선택했다고 봐도 무방하기 때문에 예외 처리 없이 해결할 수 있습니다.

 

R. Walk

문제 요약: Directed graph에서 길이가 $K$인 서로 다른 walk의 개수

풀이:

길이가 $a+b$인 walk는 길이가 $a$인 walk와 $b$인 walk로 분리할 수 있고 그 방법이 유일합니다. 반대로 한 시작점과 반대쪽의 종점이 같은 두 walk를 합쳐서 긴 walk를 만들 수 있고 이 방법도 유일합니다. 따라서 y에서 시작해 길이가 $a$인 walk의 집합 $A$, y에서 출발해 길이가 $b$인 walk의 집합 $B$, y를 포함하는 길이가 $a+b$인 walk의 집합 $C$에 대해 $A\times B \cong C$가 성립합니다. $A$의 출발점과 $B$의 도착점 또한 명시해 주면 adjacent matrix의 행렬 곱과 같음을 알 수 있습니다. adjacent matrix의 $K$제곱을 binary lifting으로 구한 뒤 모든 항의 합을 구하면 $O(N^3 lgK)$ 시간에 답을 얻을 수 있습니다.

 

S. Digit Sum

문제 요약: $K$보다 작은 양의 정수 중 자릿수의 합이 $D$의 배수인 수의 개수

풀이:

$K$가 크기 때문에 산술적으로 접근하기 곤란합니다. leading zero를 허용하면 $K$와 같은 자릿수의 정수를 많이 관찰해야 한다는 생각을 할 수 있습니다. 이때 $K$와 leading digit이 같은 수는 계산하기 힘들지만 적어도 하나가 다르면 그 아랫 자리는 자유롭게 선택할 수 있음을 확인할 수 있습니다. ```cnt[i]```를 $K$와 $i$ 길이의 prefix가 같은 정수를 $D$로 나눈 나머지가 0인 정수의 갯수로 두면 ```cnt[i]```는 $i+1$번째 자리부터 자릿수 합이 ```-sum[K[0:i]]```인 원소의 개수와 같습니다. $i+1$번째 자릿수는 $K$보다 작은 경우만 계산하면 됩니다. $K$와 같은 경우는 ```cnt[i+1]```에서 계산할 것이기 때문에 중복 계산을 피하기 위해 $i+1$번째 자릿수가 $K[i+1]$보다 작은 경우만 생각합니다. 그러면 ```cnt[i]```를 ```cnt[i][j]```꼴로 나눠서 $K$와 길이 $i$의 prefix가 같은 정수 중에 $i+1$번째 자릿수가 $j$인 정수 중 $D$로 나눈 나머지가 0인 개수로 두면 ```cnt[i][j]```는 $i+2$번째 자리부터 자릿수 합이 ```-sum[K[0:i]]-j```인 원소의 갯수와 같습니다. 여기서는 모든 자리의 자릿값을 0부터 9까지 완전히 자유롭게 선택할 수 있습니다. leading zero를 포함하여 $x$자리인 정수 중에서 $D$로 나눈 나머지가 $y$인 정수의 개수를 ```dp[x][y]```로 두면 dp값은 쉽게 구할 수 있습니다. 이 dp의 업데이트 간선의 개수는 대략 $10lgK$개입니다. 이제 모든 ```cnt[i][j]```의 값을 구하면 총 $O(DlgK)$개의 값을 각각 상수시간에 구할 수 있습니다.

 

T. Permutation

문제 요약: 주어진 부등식을 만족하는 서로 다른 순열의 갯수

풀이:

부등식을 만족하면 실제 수의 배열은 어떻게 주어지더라도 무관함을 이용할 수 있습니다. 앞에서부터 $i$개의 수를 채운 결과 $i$번째 값 보다 작은 원소의 개수가 $j$개가 되는 순열의 개수를 ```dp[i][j]```라고 둡니다. 그리고 ```s[i]```에 따라 두 가지 경우의 수로 나뉩니다.

 

```s[i]```가 <인 경우라면 이전까지 구한 순열의 마지막 원소보다 큰 원소를 취해야 합니다. ```dp[i][j]```에서 마지막 원소보다 큰 원소는 ```i-dp[i][j]-1```개 있습니다. 이중 하나를 고른 뒤 이보다 크거나 같은 이전에 등장한 모든 원소에 1을 더해주는 방법으로 $i+1$번째 원소를 특정할 수 있습니다. ```dp[i+1][k] += dp[i][j]: k>j```와 같은 구간 업데이트를 진행할 수 있습니다.

반대로 ```s[i]```가 >인 경우라면 1부터 $j$까지 고를 수 있으므로 ```dp[i+1][k] += dp[i][j]: k<=j```와 같은 구간 업데이트를 진행할 수 있습니다. ```dp[i]```가 ```dp[i-1]```에만 의존하므로 $i$를 고정해 두고 구간 업데이트 쿼리를 이용할 수 있고, imos 등의 방법으로 $i$마다 $O(N)$에 해결할 수 있습니다. 반대로 ```dp[i][k] = \sum (dp[i-1][k])``` 꼴로 수정해 구간 합 쿼리를 이용할 수도 있습니다. 세그먼트 트리를 이용할 수도 있습니다.

 

U. Grouping

문제 요약: $N$개의 원소를 파티션 지어 같은 부분에 들어간 쌍마다 점수를 얻을 때 점수의 최댓값

풀이:

모든 원소를 분리할 수 있으므로 답은 0 이상입니다. ```dp[i]```를 비트마스크가 i인 부분집합을 파티션 지을 때 얻을 수 있는 점수의 최댓값으로 우선 정의하고 싶어집니다. top down이나 bottom up이나 비트를 뒤집으면 같은 모양이기 때문에 업데이트 간선의 개수는 같습니다. bottom up 관점에서 볼 때 ```dp[i] = max(dp[i-j] + cost(j): j \in i)```임을 확인할 수 있습니다. ```cost(j)```는 비트마스크가 $j$인 부분집합의 점수입니다. 이를 나이브로 구현하면 맞을 수 있습니다.

업데이트 간선의 개수는 모든 부분집합의 모든 부분집합의 원소 개수 합인데, 이항정리를 이용해서 업데이트 간선의 개수를 구할 수 있습니다. 비트마스크 $i$의 부분집합의 개수는 $2^{popcount(i)}$입니다. popcount가 같은 $i$끼리 모으면 총 업데이트 간선의 개수는 $\sum _ {k=0} ^{k=N} 2^{N} nCr(N,k)$인데 이항정리에 의해서 $(2+1)^N$과 같으므로 총 $3^N$개의 업데이트 간선이 있습니다.

cost를 나이브로 구하면 매 업데이트마다 최대 $N^2$번 더 연산하게 되므로 cost를 전처리해야할 수 있습니다.

 

V. Subtree

문제 요약: Unrooted tree에서 특정 정점을 포함한 connected subgraph의 개수

풀이:

rooted tree에서 subtree의 개수를 세는 것은 ```dp[v] = \prod (dp[u]: (u,v) \in E) + 1```으로 상대적으로 쉽습니다. 만약 dp가 체의 원소라면 간선을 쉽게 끊을 수 있습니다. root 정점 r, r의 자식 v에 대해 ```dp[r] = (dp[r]-1)/(dp[v]) + 1```, ```dp[v] = (dp[v]-1)*dp[r] +1```을 이용하면 루트를 r에서 인접한 v 정점으로 바꾼 경우의 dp 배열을 $O(1)$에 얻을 수 있습니다. 이 과정을 통해 전체 트리를 dfs하면 각 정점이 루트일 때 루트의 dp 값을 $O(N)$에 구할 수 있습니다.

체의 원소가 아니기 때문에 나누기 연산을 사용할 수는 없지만 나누는 행위가 r의 모든 자식 정점 중 v를 제외한 모든 정점을 합치는 것과 같음을 이용할 수 있습니다. 모든 자식 정점 v마다 v가 아닌 정점의 dp 값을 모으는 연산을 하게 되면 $\sum deg(v)^2$만큼 연산이 필요해 비용이 가장 큰 정점에서 $O(N^2)$보다 작을 수 없습니다. 대신 v의 접두/접미 누적합을 이용하면 $O(deg(r))$의 전처리를 통해 각 v마다 v를 제외한 dp값을 $O(1)$에 얻을 수 있습니다. 각 정점이 루트가 될 때마다 $O(deg(r))$의 전처리가 필요하므로 총 전처리 비용은 $O(\sum deg(r)) = O(N)$이 됩니다.

 

W. Intervals

문제 요약: 몇 개의 정수를 선택해 주어진 구간이 선택한 정수를 포함하는 경우 점수를 획득할 때 점수의 최댓값

풀이:

```dp[i]```를 선택한 정수 중 최댓값이 $i$일 때 점수 최댓값으로 두고 작은 수부터 순서대로 선택하고 싶어집니다. $i$를 선택하기 직전에 선택한 가장 큰 정수가 $j$라면 ```dp[i] - dp[j]``` 값은 $i$를 포함하면서 $j$를 포함하지 않는 구간의 가중치 합이 됩니다. 이를 나이브로 구하면 $O(M)$의 비용이 들고 각 $j$마다 구하면 총 $O(N^2M)$만에 답을 얻을 수 있습니다. $i$보다 작은 범위와 겹치는 구간의 가중치 합 등을 누적합으로 하는 차분 배열은 올바른 dp값의 차를 구할 수 없습니다. 

 

dp 식을 써보면 ```dp[i] = max(dp[j] - cost(i,j): j<i) + sum(i)```로 정리할 수 있습니다. 이때 ```cost(i,j)```는 $i$와 $j$를 동시에 포함하는 구간의 가중치 합, ```sum(i)```는 $i$를 포함하는 구간의 가중치 합입니다. 가중치가 $A$인 ```cost(i,j)```에 포함되는 구간 ```[L:R]```은 ```cost(i,L:R)```에 $-A$만큼 영향을 줍니다. dp값을 세그먼트 트리로 관리하면 해당 구간이 $i$를 포함하는 동안 $[L:R]$에 $-A$만큼 기여합니다. 이와 독립적으로 ```sum(i)```에 포함되는 구간은 $j$에 관계없이 영향을 줍니다. 따라서 $j$를 전체 범위로 확장해 보면 ```sum(i)```에 포함되는 모든 구간 $[L:R]$은 $[L:R]$이 아닌 범위에서만 $A$만큼 영향을 주는 것으로 볼 수 있습니다. 

 

실제로 구현을 구체화해 보면 $i$를 작은 것부터 순회하면서 $i$를 포함하는 모든 구간만을 동시에 관리합니다. 이때 세그먼트 트리를 이용해 해당 구간이 아닌 범위의 값을 구간의 가중치 만큼 증가시킵니다. 이때 $i$보다 작은 인덱스에서 ```dp[j] - segtree[j]```값의 최댓값이 ```dp[i]```값이 됩니다. 세그먼트 트리의 각 인덱스마다 ```dp[i]```값을 증가시켜놓으면 한 번의 세그먼트 트리 쿼리만으로 dp값을 구할 수 있습니다. 각 구간이 세그먼트 트리에 한 번 들어갔다 나오고 각 인덱스마다 세그먼트 트리의 구간 쿼리를 한 번 수행하므로 총 $O((N+M)lgN)$에 답을 구할 수 있습니다. 일본에서 starry sky tree로 알려진 유사 세그먼트 트리로 해결할 수도 있습니다.

 

X. Tower

문제 요약: 무게 $w$인 블럭 위에 무게 합이 최대 $s$인 블럭까지 쌓을 수 있을 때 쌓인 블럭의 가중치 합 최대

풀이:

블럭을 쌓는 순서가 중요하므로 블럭을 쌓는 순서를 정하는 것이 중요합니다. 각 블럭의 무게를 $W[i]$, 쌓을 수 있는 한계를 $S[i]$, 가중치를 $V[i]$라고 하고 쌓을 수 있는 한계를 용량이라고 부르면 좋아 보입니다. 용량 $s$ 위에 블럭 $i$, $j$가 아래에서부터 순서대로 쌓여있을 때 가장 꼭대기에 추가로 쌓을 수 있는 용량의 크기는 ```min(s-W[i]-W[j],S[i]-W[j], S[j])```입니다. 반대로 블럭 $j$, $i$가 순서대로 쌓여있다면 ```min(s-W[i]-W[j],S[j]-W[i], S[i])```입니다. 이때 $i$를 위에 쌓는 것이 더 이득이려면 ```min(s-W[i]-W[j],S[i]-W[j], S[j]) <= min(s-W[i]-W[j],S[j]-W[i], S[i])```를 만족해야 합니다. 가장 첫 항은 항상 같기 때문에 우변의 최솟값이 ```s-W[i]-W[j]```인 경우는 고려하지 않아도 됩니다. $i$와 $j$가 대칭식이기 때문에 좌변의 최솟값인 경우도 동일합니다. 따라서 ```min(S[i]-W[j], S[j]) <= min(S[j]-W[i], S[i])```가 성립하면 $i$를 위에 쌓는 것이 항상 유리합니다. 증명 없이 이 식을 기준으로 블럭을 정렬해 dp식을 세우면 맞을 수 있습니다.

 

식을 약간 변형하면 ```min(S[i]+W[i], S[j]+W[j]+W[i]) <=  min(S[j]+W[j], S[i]+W[j]+W[i])```처럼 쓸 수 있습니다. 우변의 최솟값이 ```S[i]+W[j]+W[i]```라면 우변은 ```S[i]+W[i]```보다 클 수 없기 때문에 항상 부등식이 성립합니다. 따라서 이 경우도 제외할 수 있습니다. 따라서 ```S[i]+W[i]<=S[j]+W[j]```인 경우에 $i$를 위에 쌓는 것이 유리하므로 $S+W$를 기준으로 큰 블럭부터 쌓는 것이 유리합니다.

 

```S[i]+W[i]<=S[j]+W[j]```이고 $i$ 위에 $j$를 쌓을 수 있다면 ```min(s-W[i],S[i])<=W[j]```를 만족합니다. 식을 변형해서 ```min(s-W[j],S[i]+W[i]-W[j])<=W[i]```를 얻습니다. 만약 둘 중 더 작은 값이 $s-W[j]$라면 문제 없이 $j$ 위에 $i$를 쌓을 수 있습니다. 아니라면 ```S[i]+W[i]-W[j] <= s-W[j] <= W[i]```를 얻어 ```S[i]<=W[j]```임을 알 수 있습니다. ```min(s-W[j],S[j]) <= min(W[i],S[j]) <= W[i]```이므로 이 경우도 $j$ 위에 $i$를 쌓을 수 있습니다. 따라서 $S+W$가 큰 블럭부터 순서대로 쌓는 dp를 구성하면 해결할 수 있습니다.

 

이제 마지막으로 ```dp[i][j]```를 $i$번째로 $S+W$가 작은 블럭까지 쌓았을 때 여유 용량이 $j$일 때 가중치 합 최대로 두면 0-1 배낭 문제로 해결할 수 있습니다. 정렬에 $O(NlgN)$의 시간이 필요하고 업데이트 간선의 개수는 최대 $O(N \sum s)$개입니다.

 

Y. Grid 2

문제 요약: 장애물이 있는 격자에서 수직인 두 방향만 이용해서 이동할 수 있는 경우의 수

풀이:

문제 제한이 크므로 모든 경우의 수를 다 구할 수 없습니다. $N$개의 장애물을 장애물이 아닌 도착점으로 생각합니다. ```dp[i]```를 $i$번째 장애물에 다른 장애물을 거치지 않고 도달할 수 있는 경로의 수로 둡니다. ```dp[i]```는 다른 장애물에 상관 없이 $i$번째 장애물에 도달하는 경우의 수에서 다른 장애물을 거쳐 도착하는 경우의 수를 뺀 값입니다. 또한 ```dp[i]```는 $i$가 처음 만난 장애물이고 그 자리에서 멈춘 경우의 수로 이해할 수도 있습니다. 따라서 ```dp[i] = nCr(r[i]+c[i]-2,r[i]-1) - \sum (dp[j] * nCr(r[i]+c[i]-r[j]-c[j],r[i]-r[j])```가 성립합니다. $j$의 범위에 따라 이항계수를 구할 때 문제가 생길 수 있음에 주의해야합니다.

$(H,W)$에 도달하는 경우의 수는 $(H,W)$에 장애물을 하나 더 추가로 놓고 이 장애물에 처음으로 도달하는 경우의 수를 세는 것과 같습니다. 업데이트 간선의 개수는 최대 $O(N^2)$개이고 이항계수를 상수시간에 구할 수 있도록 $O(H+W)$에 전처리해둘 수 있습니다.

 

Z. Frog 3

문제 요약: 위치가 증가하는 방향으로 점프하는 비용이 높이 차이의 제곱일 때 $1$번 칸에서 $N$번 칸으로 이동하는 최소 비용

풀이:

```dp[i]```를 $i$번 칸으로 이동하는 데 드는 최소 비용이라고 두면 ```dp[i] = min(dp[j] + (h_i-h_j)^2 + C: j<i)```입니다. 식을 변형하면 ```dp[i] = min(-2h_jh_i + dp[j] + h_j^2) + C+h_i^2```이 됩니다. 이는 일차함수의 모임에 대입한 값의 최솟값을 구하는 쿼리로 해결할 수 있습니다. convex hull trick 또는 Li-Chao tree를 통해 ```dp[i]```값을 구한 뒤 직선 ```-2h_i x + dp[i] + h_i^2```을 추가하는 것으로 해결할 수 있습니다. $h_i$가 증가하므로 선형 CHT를 수행할 수도 있고, Li-Chao tree를 통해 $O(Nlgh_N)$에 해결할 수도 있습니다.