Typical DP Contest

[5/13 초본, 5/27 L 추가, 5/28 M 추가, 6/22 I,J 추가, 6/23 N,T 추가]

흔한 DP 컨테스트라고 말은 하지만, 어렵다.

http://tdpc.contest.atcoder.jp/

A

Subset Sum이라는 유명한 문제로, 풀이 역시 유명하다. 개행 문자를 넣어야만 AC가 되니 유의.

cpp : http://codepad.org/nKJbfaBR

C

win[player][i] 를 i번째 라운드까지 진행되었을 때 player의 승률이라 정의하자. 동적 테이블을 채울 때, 각 플레이어가 i-1번째 라운드를 통과하고 본인과 대전할 확률을 구할 수 있으며, 싸워서 이길 확률은 식으로 주어져 있다. 이를 통해서 테이블을 채울 수 있으며 1초 안에 통과될 만큼 시간복잡도가 나올 듯 하다.

사실 코드가 없어서 검증된 풀이는 아니다. 믿거나 말거나..

D

먼저 목표값 D가 7 이상의 소인수를 가지면 확률은 0이다. 이를 처리해 주자.

처리해 주면 목표값 D는 2^k * 3^l * 5^m 꼴이 된다. 각 주사위는 1 2 3 4 5 6의 값을 가지고 있으며 이에 따라 몇개의 배수를 충족시켜주는지 역시 구할 수 있다.

이러면 dp[현재 던지는 주사위][필요한 2][필요한 3][필요한 5] 와 같은 점화식이 나온다. 시간 복잡도는 Nlg^3D이다.

cpp : http://codepad.org/bpUVdaNw

E :

dp[D로 나눈 나머지][현재 보는 중인 자리수][N보다 수가 커질 수 있는가] 라는 식으로 테이블을 정의하면, 다음에 올 수 있는 숫자 (0 ~ 9)를 돌면서 동적 테이블을 채울 수 있다. 해당 수가 N보다 작다는 것을 보장해 주기 위해서 세번째 인자가 존재하는데, 한번이라도 숫자가 N과 달라진다면 저 수를 0으로 두면서 계산해야 할 것이다. 이 때는 그 뒤에 무엇이 나오던간에 N보다 수가 커질 수 없으며, 그렇지 않다면 그 뒤에 나오는 수는 항상 N의 현재 자리수보다 작거나 같아야 한다.

마지막 자리수를 볼 때 D = 0이어야지 배수라는 것을 알 수 있다.

시간 복잡도는 10 * D * |N| 이다. N은 그냥 문자열이라 치자.

cpp : http://codepad.org/1expn0PJ

F : 골라야 하는 원소를 선택하는 방법이 아니라, 고르지 말아야 하는 원소를 선택하는 방법의 개수를 구하도록 하는 것이 더 계산하기 편할 것이다 (K개의 연속된 원소라는 개념이 꽤 머리아프다). 이렇게 되고 초항을 적절히 고르면 O(N^2)에 dp[i]를 구할 수 있다. 하지만, dp[i] = S[i] - S[i-1] 라는 식으로 점화식을 합에 대해서 나타내면 계산을 더 빠르게 할 수 있으며, 이를 사용하면 O(N)에 풀린다.

cpp : http://codepad.org/1049aJ34

G : dp[pos] -> S[pos,n-1] 에서 사전순으로 몇개의 문자열을 만들 수 있는가? 라고 식을 정의하자. 중요한 관찰이 필요하다.

 * pos 뒤에 2개 이상의 같은 알파벳이 있다면, 앞에 있는 것만 택해야 한다. 뒤에 있는 것을 택했을 경우, 이는 앞에 있는 것을 택한 것의 부분집합으로 들어간다.

next[pos][alpha] 를 정의하자. pos 뒤에 있는 가장 앞에 있는 alpha 문자의 위치를 저장하는 배열로써, 이는 간단한 동적 계획법으로 구할 수 있다. 이렇게 되면 dp[pos] = Sum for all alpha i (dp[next[pos][i]]) 라는 식이 나온다. 이를 계산해 준다.

문자열을 추적하는 것은 점화식을 짰던 과정을 그대로 trace해주면 된다. 재귀를 쓰면 편하다. 시간 복잡도는 26 * |S|.

cpp : http://codepad.org/KVbAI7hf

H : dp[pos][weight][color][used] 로 식을 정의하자. pos는 현재 보고 있는 가방의 번호, weight는 현재 사용할 수 있는 무게, color는 사용할 수 있는 색깔, used는 이와 같은 색깔을 사용한 적이 있는지에 대한 불리언 값이다. 먼저 짐들을 색깔 순으로 정렬한 후, 전이 과정에서 한번 썼던 색깔을 다시 쓰면 used를 1로 해준 후 color를 사용해 주지 않는 식으로 dp를 돌리면 된다. 만약에 색깔이 바뀐다면 used를 다시 0으로 바꿔주는 등의 노력이 필요하다.

서술한 방법은 메모리 사용량이 크므로 toggling을 사용해서 메모리를 잘라준다. O(NWC)로 2초 안에 나온다.

cpp : http://codepad.org/KjxPZssv

I : 처음에 문제를 봤을때 생각한 것은 스택을 사용하는 것이었다. 스택에 "i", "iw"의 출현 횟수를 담은 후 이를 토대로 dp를 돌리는 것, 되는지 안되는 지는 모르겠지만 일단 꽤 힘든 방법임은 분명하니 관점을 바꾸자.

두개의 DP를 정의한다.

DP1(i,j) -> [i,j] 에서 적당한 원소를 빼는 게 허용되어 있을 때 iwi를 만들 수 있는 개수

DP2(i,j) -> [i,j] 에서 적당한 원소를 빼는 게 금지되어 있을 때 iwi를 만들 수 있는 개수

빼는 게 허용되어 있는 것이 우리가 구하는 것이다. 이 때 우리는 DP를 1) 중간으로 쪼개거나. 2) 양옆을 잘라내거나, 3) 구간의 iwi를 인식하고, 나머지 구간을 완전히 날려버리는 연산을 함으로써 iwi를 만들면 된다. 왜 이것이 iwi를 만드냐고..? "iwiwii[...]iwi" 라는 수열을 생각해보자. 이를 거꾸로 생각해보면 알 수 있다.

DP2 배열의 필요성은 3)의 조건에서 출현한다. 나머지 구간을 완전히 날려야 하는데 양 옆이 잘리면 조금 곤란해 질것이다. 이러한 경우를 막기 위해서 dp2를 따로 만들고, 여기서 iwi를 만들 수 있는 개수를 구한다. 만약 구할 수 없다면 -inf를 반환.

시간 복잡도는 O(|S|^3) 이다.

cpp : https://gist.github.com/koosaga/41d34743cad1f7000e4e

J : 비트마스킹을 통해서 적절한 dp 식을 만들 수 있지만, dp의 특성상 사이클은 아니지만, 자기 자신의 값을 요구하는 경우가 생긴다. 손으로 풀 경우에는 이를 방정식을 사용해서 해결하는데, 이 문제에서도 그러한 전략은 유효하다. 만약에 이번에 요구하는 dp값이 자신일 경우에는, 확률을 조정할 수 있다. 이러한 과정을 거치면 자기 자신의 값을 요구하지 않는다.

cpp : https://gist.github.com/koosaga/b0c77bcca6f942af959d

K : r이 작은 순서대로 들어가니까 그 순으로 정렬하고 dp 돌리면 되네라고 생각하면 말린다. O(n^2)보다 줄이기가 힘들기 때문.

다시 원이라고 생각을 한 후 평면 상에 쌓아올려보면 [s1,e1] > [s2,e2] ... > [si,ei] 식으로 완전히 포함 관계에 있는 폐구간 부분집합의 최대 크기를 물어보는 문제가 된다는 것을 알 수 있다.

이때 s1 순서대로 정렬을 시키면 이는 최대부분감소수열과 동치인 문제라는 것을 알 수 있다. 다만 strictly라는 조건이 있기 때문에 greedy LIS를 짜서 어셉시키는 것보다는 (가능한지는 생각해보지 않았다.) n^2 dp를 짠 후 Range Minimum Query 인덱스 트리를 사용해서 O(nlgn)으로 최적화 하는 것이 이득이다.

cpp : http://codepad.org/CJZHuBMB

L : 고양이의 위치를 직접 고정해주자니 머리가 골치아파진다. 그러지 말고, Li = i번째 고양이가 왼쪽으로 볼 수 있는 가장 번호가 작은 고양이라고 정해주자.

L1 = 1, Li <= Li+1을 만족해 주면, 그에 상응하는 번호를 항상 붙여줄 수 있음을 보장할 수 있다. 사실 난 보장도 증명도 못하고 AC라는 사실이 보장한다 (....)

본론으로 들어가서, dp[j][i] = (Li = j일때의 최대 이득) 이라고 점화식을 세우면, Li-1 <= Li라는 조건을 만족하는 테이블에 대해서 모두 순회할 때 O(n^3)의 상당히 깔끔한 식이 나온다. 데이터가 약한지 뭔지 이걸로 충분히 AC를 볼 수 있지만, dp[j][i]를 Prefix Max의 형태로 해서, 앞까지의 맥시멈 값을 모두 저장하고 있도록 코딩하자. 한 테이블을 상수 시간에 채울 수 있으니 복잡도는 O(n^2). 코드는 cubic보다 짧다.

cpp : http://codepad.org/TtQFvEYI

M : i -> j로 가는 경로의 개수를 R^2개의 쌍에 대해서 해결하는 것이 첫번째 과제이다. 끝 점을 고정시키고, DP[visited][pos] 를 통해서 그러한 경로의 개수를 세는 비트 DP를 돌리면, 2^R * R^2의 시간 복잡도를 통해서 각 끝점당 경로의 개수를 셀 수 있다. 이걸 R번 돌리니 여기까지 시간 복잡도가 2^R * R^3이다.

다음으로는 이를 H개의 집에 대해서 해결하는 것이 문제이다. 편의상 0층 1번 방부터 H층 1번 방까지의 경로라고 세자. (왜 1층이 아닌지는 잘 생각해 보자) 이 경우 dp[0][1] = 1, dp[i][j] = Sum(1 <= k <= r) ((j -> k로의 경로의 수) * dp[i-1][k]) 이라는 점화식이 나온다. 단순 계산으로는 HR^2가 나오고 토글링이든 뭐든 TLE이다.

이때 경로의 수 테이블을 행렬로 생각해 보면, dp[i](...) 와 dp[i-1](...) 에 대한 관계식이 행렬의 곱으로 정의될 수 있다는 것을 알 수 있으며, 심지어 이것이 제곱식으로 깔끔하게 나온다는 것도 알 수 있다. 제곱 식이 나왔다는 것은, 반복제곱법을 사용할 수 있다는 말이다. 행렬의 제곱에는 R^3의 시간 복잡도가 드므로, 이 과정은 R^3lgH의 시간 복잡도를 가진다. 문제 하나로 비트 DP와 행렬 제곱을 동시에 다뤄서, 최종 시간 복잡도에는 무려 지수와 로그가 같이 붙는다. O(2^R * R^3 + R^3lgH).

cpp : http://codepad.org/WrBDMpBu

N : 시작점을 하나 잡고 거기서 넓혀가면서 트리를 만드는 것을 생각해 보자. 서브트리에서 문제를 푸는 식으로 dp를 짤 수 있을 까 고민을 해보면, 서브트리를 왔다갔다하면서 트리가 생성될 수 있기 때문에 쉽지 않다는 것을 알 수 있다. 이러한 문제점은 이항 계수를 사용함으로써 해결할 수 있다. 그냥 각 서브트리에서 순서대로 트리를 만든다 치고, 이항 계수를 곱해주면서 이들이 섞인 경우를 곱해주면 된다. dp[i] = nCr * n-rCr' .... * dp[subtrees] ... 와 같은 식이 나온다는 것을 알 수 있다. 시작점을 각각 고정시켰기 때문에 복잡도는 O(N) * O(N) = O(N^2) 이며, 이항 계수의 계산은 O(N^2) 나 O(NlgP)에 가능하다.

cpp : https://gist.github.com/koosaga/046b74533cc1d194cb97

R : 먼저 SCC를 구하면 DAG를 만들 수 있으며 사이클이 없으므로 DP를 돌리기 위한 준비가 되어 있다.

이후 두 정점을 놓은 후 dp(x,y)는 다음과 같은 순서대로 구한다. 단, x < y이다.

-> 만약에 연결된 정점이 y보다 작으면 dp(i,y) + Size(x)과 비교.

-> 만약에 연결된 정점이 y보다 크면 dp(y,i) + Size(x) 과 비교.

이러한 방식으로 구하면 두 점을 두 번 거치지 않는 방법으로 문제를 풀 수 있다. 이러한 순회를 Bitonic Tour라고 한다.

cpp : http://codepad.org/s3cWRpkd

T : K^3lgN 풀이는 행렬 곱셈을 이용하는 것인데, (M 참조) 그것보다 빠르게 할 수 있는 방법이 있다.

정확히 말해서는, Ai = C1 A1 + C2 A2 .. CN AN 과 같은 식이 있다면, 이 때 Ai -> Ai+1, Ai -> A(2i) 로 식을 변환할 수 있다. Ai를 값으로 가지지 말고, 행렬 곱셈에서 그렇듯이 {C1 .... CN} 과 같은 계수의 집합으로 가지고 가자. (구조체 사용)

1) Ai = A1C1 .. ANCN 이므로, A(i+1) = A2C1 + A3C2 ... A(N+1)CN 임을 알 수 있다. A(N+1) = AN + A(N-1) ... 이므로, A(i+1)을 Ai에서 O(N)에 유도할 수 있다.

2) A(2i) = C1A(i+1) + C2A(i+2) ... CNA(i+N) 이고, A(i+1) ... A(i+N)은 A(i) 에서 O(N) * O(N) -> O(N^2) 에 구할 수 있다. A(i+1) .. A(i+N) 까지의 값에서 A(2*i)는 O(N^2)에 구할 수 있다. 즉, A(2*i) 는 A(i)에서 O(N^2)에 구할 수 있다.

(사실 2번보다 좋은 풀이는, A(i+1) 의 식을 또 풀어버리는 것이다. A(2*i) = C1 * (C1A2 + C2A3 ....) + C2 * (C1 A3 + C2 A4 ...) 와 같은 식으로 보면, A(2*i) = (C1C1) A2 + (C2C1 + C1C2) A3 .... (CNCN) A2N 임을 알 수 있다. A(2N) 까지는 bounded 되어 있기 때문에 그냥 미리 precomputation을 하면 O(N^2)에 구할 수 있다.)

계산으로 돌아가자. AK = {0,0,0,0 ... 1} 일 경우, Ai -> Ai+1 이 O(K), Ai -> A2*i가 O(K^2) 일 경우 O(K^2lgN)에 K -> N으로 전이 시킬 수 있다. 고로 시간 복잡도는 O(K^2lgN)이다. 이러한 방법을 일본에서는 키타마사 법이라고 하는 것 같다.

cpp : https://gist.github.com/koosaga/d4df80a3128b9f5b36b0