目次
Educational DP Contest N,O,P,Q,Rメモ
N - Slimes
問題
- $N$ 匹のスライムが横一列に並ぶ
- 最初の大きさは左から $a_1,a_2,...,a_N$
- 隣り合う2匹を合成することを繰り返して、1つにまとめる
- 合成する時、2匹のその時点の大きさの和のコストがかかる
- 最小コストを求めよ
- $1 \le N \le 400$
解法
区間DP。ループ回数は多め。
データ
$DP[l][r]=$初期状態で左から $[l, r)$ の区間のスライムを1匹に合成する最小コスト
初期条件
全て0
遷移
例えば$[2, 7)$の区間のスライムを1匹に合成するには、その直前で、$[2,x)$ と $[x,7)$ の2匹に分かれていないといけない。（$x$は$3～6$の任意の数）
逆に、$[2,x)$ や $[x,7)$ がどう合成されたものであろうが、それぞれのコストの最小値さえわかっていれば、$[2,7)$ の合成コストは求められる。
この$x$を全て試し、最小を取るとよい。
$DP[l][r]=\min_{l+1 \le x \le r-1}(DP[l][x]+DP[x][r])+([l,r)のスライムの大きさ合計)$
大きさの合計は、最初に累積和$acc$を取っておけば、$acc[r-1]-acc[l-1]$ で求められる。
from itertools import accumulate
n = int(input())
acc = [0] + list(accumulate(map(int, input().split())))
dp = [[0] * (n + 1) for _ in range(n)]
for w in range(2, n + 1):
for l in range(n - w + 1):
r = l + w
dp[l][r] = min(dp[l][m] + dp[m][r] for m in range(l + 1, r)) + acc[r] - acc[l]
print(dp[0][n])
O - Matching
問題
- $N$ 人の男と $N$ 人の女
- 相性は $N \times N$ 行列で示される
- $A_{i,j}=1$ なら$i$ 番目の男と $j$ 番目の女が好相性、0なら相性なし
- 好相性同士で $N$ 組のペアを作る時、組み方は何通りあるか
- $1 \le N \le 21$
解法
bitDP。集合をビットフラグで表し、0から積み上げて $2^N$ 通りの集合の値を計算する。
データ
$DP[i][s]=i$ 番目までの男たちが、集合 $s$ で示される女たちとペアになるパターン数
初期条件
$DP[0][0]=1$
遷移
$i-1$ 番目の男まで計算済みとする。
$i$ 番目の男と $j$ 番目の女が好相性の時、
$DP[i-1]$ の中で、まだ $女_j$ が含まれていない集合 $s$ に対して、$DP[i][s|女_j] += DP[i-1][s]$ と遷移する。
たとえば $j=5$ とすると、下から5番目だけ立ったビットフラグ$b=10000$を用意して、
- 集合 $s=11000$ に対しては、既に5番目のbitが立っている（$女_5$ が既に他の男とペアになっている）ので何もしない
- 集合 $s=00101$ に対しては、ペアが1組作れるので、$DP[i][10101] += DP[i-1][00101]$ と加算する
…という処理を、$DP[i-1]$ に含まれる各 $s$ について行っていく。
計算量
$i$ から $i+1$ への遷移で必要なのは、ビットフラグ $s$ の $N$ 本のビットのうち、立っているのがちょうど $i$ 本のもののみ。 （男が $i$ 人なので、女も同数のもののみ考慮すればよい） そのようなビットは、$\displaystyle {}_NC_{i}$ 通りある。
「立っているのがちょうど$k$本のビットフラグのみのイテレート」はやりにくく、結局は $0～2^N$ を回して条件に合う物のみ処理するのが単純だし早い。 ただ、この問題の場合「立っているのがちょうど$i$本のビットフラグ」は、$i-1$ から $i$ への遷移の際に新しく作られた $s$ に他ならない。 これを記録しておくことで、$DP[i+1]$ の計算時に過不足のないイテレートが可能となる。 代わりに記録するコストがかかるので、言語によっては却って遅くなるかも知れないが……。
ともかく、$\displaystyle {}_NC_{i}$ 通りのそれぞれで、$男_i$ と相性のよい女（最大 $N$人）の遷移を行うので、全体での計算量は
$\displaystyle \sum_{i=0..N-1} N \times {}_NC_{i}$ となる。これは、$N=21$ で約 $4.4 \times 10^7$ となる。
n = int(input())
dp = [0] * (1 << n)
dp[0] = 1
curr = {0}
MOD = 10 ** 9 + 7
for i in range(n):
compatibilities = [1 << i for i, v in enumerate(input().split()) if v == '1']
nxt = set()
for k in curr:
p = dp[k] % MOD
for c in compatibilities:
if k & c:
continue
dp[k | c] += p
nxt.add(k | c)
curr = nxt
print(dp[(1 << n) - 1] % MOD)
P - Independent Set
問題
- $N$ 頂点の木を、白か黒に塗り分ける
- 辺で直接結ばれた2頂点を同時に黒で塗ってはいけない
- 塗り方は何通りか、$\mod{10^9+7}$ で求めよ
解法
木DP。適当な頂点を根として、部分木の解を求めていく。
どの頂点から先に計算すれば良いかわかりづらいので、再帰関数で書くのがやりやすい。
一応、DFSで計算順序を求め、その順にDP配列を埋めていくやり方でボトムアップでも可能。PyPyは再帰が遅いので、PyPyの速度が必要な場合はそのようなやり方をする。
データ
$DP[i][w]=$頂点1と根とした時、頂点 $i$ 以下の部分木で、頂点 $i$ 自身の色が$w=白/黒$だった場合のパターン数
$DP[1]$ を再帰で求める
初期条件(末端条件?)
葉のパターン数: (白,黒) = (1,1)
遷移
頂点 $i$ を黒にするには、子供が全部白でなくてはならない。逆に頂点 $i$ が白なら、子供は白でも黒でもよい。
\begin{eqnarray} DP[i][白] &=& \prod_{c \in iの子供} (DP[c][白]+DP[c][黒]) \\ DP[i][黒] &=& \prod_{c \in iの子供} DP[c][白] \end{eqnarray}
import sys
sys.setrecursionlimit(100005)
MOD = 1000000007
def dfs(v, a):
w, b = 1, 1
for u in links[v]:
if u == a:
continue
cw, cb = dfs(u, v)
w *= cw + cb
b *= cw
w %= MOD
b %= MOD
return w, b
n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
x, y = map(int, line.split())
x -= 1
y -= 1
links[x].add(y)
links[y].add(x)
print(sum(dfs(0, None)) % MOD)
Q - Flowers
問題
- $N$ 本の花が横1列に並ぶ
- 花の高さは左から $h_1,h_2,...,h_N$ で、これは $\{1,2,...,N\}$ を並び替えたものである
- つまり、$1～N$ の高さの花が1本ずつある
- 花の価値は、左から $a_1,a_2,...,a_N$
- 何本かの花を摘み取り、左から高さが単調増加になるようにしたい
- 残る花の価値を最大化せよ
解法
セグメント木上でのDP
データ
$DP[i]=$左から $1～i$ 本目までの花だけを考慮し、$i$ 番目の花は必ず残す場合の、残る花の価値の最大値
セグメント木上で実装し、更新・取得をそれぞれ $\log{N}$ で行えるようにする
- 更新(i, x): DP[i] を xにする
- 取得(i): DP[1]～DP[i] の最大値を取得する
初期条件
全て0
遷移
$DP[i-1]$ まで確定して、$i$ 番目の花を残すときを考える。
この時、「左から $1～i-1$ 番目に位置し、かつ $h_i$ より低い高さである花のうち、$DP[j]$ が最大のもの」に、$a_i$ を加えたものが $DP[i]$ となる。
↓いまここ
1 2 3 4 5 6
h 1 5 3 6 4 2
a 10 20 30 40 50 60
DP 10 30 40 70
$i=5$ より左にあり、$h_5=4$ より低い花の中で、$DP$ が最大のものは、$DP[3]=40$。よって、$DP[5]=40+50=90$ となる。（花1,3,5を残す時にこれが実現できる） 4より高い花が左にあると置けなくなってしまうので、自分より低い花の中から最大値を探すことになる。
位置と高さを両方考えるのはややこしいので、事前に$h_i$でソートしておき、低い方から処理していくと、高さは無視できる。 花 $i$ を処理時点での $DP$ の値は必ず$h_i$ より低い花のみを考慮した値となっている。
↓いまここ
1 2 3 4 5 6
h 1 5 3 6 4 2
a 10 20 30 40 50 60
DP 10 40 70
セグメント木に対する更新は点更新、取得は必ず$[1, k)$ の形となるので、簡略化した形で書ける
def solve(n, hhh, aaa):
n2 = 1 << n.bit_length()
offset = n2 - 1
data = [0] * ((n2 << 1) - 1)
def update(k, x):
i = k + offset
while i >= 0:
if data[i] < x:
data[i] = x
else:
break
i = (i - 1) // 2
def get_max(k):
i = k + offset
ret = data[i]
while i:
# 自身が右枝の場合のみ、左枝と比較
if i % 2 == 0:
ret = max(ret, data[i - 1])
i = (i - 1) // 2
return ret
srt = sorted((h, i) for i, h in enumerate(hhh))
for h, i in srt:
update(i, get_max(i) + aaa[i])
return data[0]
n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
print(solve(n, hhh, aaa))
R - Walk
問題
- $N$ 頂点の単純有向グラフ
- 辺の有無は行列の形で与えられる
- $1 \le i,j \le N$ について、$a_{i,j}=1$ なら $i→j$ の辺が存在し、0なら存在しない
- 長さ $K$ の有効パスは何通りあるか求めよ
- 同じ辺を複数回通ってもよい
- $1 \le N \le 50$
- $1 \le K \le 10^{18}$
解法
行列累乗
データ
現在考慮中のパス長が $k$ として、
$DP[i][j]=$ 頂点$i$から$j$ へ、パス長がちょうど $k$ の行き方の通り数
初期条件
全て0
遷移
有向グラフの経路パターン数は、辺の有無を0-1行列にし、累乗することで算出できる。
①-->②<->③
<------->
1 2 3
1| 0 1 1
A^1 2| 0 0 1
3| 1 1 0
1| 1 1 1
A^2 2| 1 1 0
3| 0 1 2
1| 1 2 2
A^3 2| 0 1 2
3| 2 2 1
$A^3_{1,2}$ を例に取ると、
- $A^1$ より、
- 1→1 への長さ1の経路が0通り(A)
- 1→2 への長さ1の経路が1通り(B)
- 1→3 への長さ1の経路が1通り(C)
- $A^2$ より、
- 1→2 への長さ2の経路が1通り(A)
- 2→2 への長さ2の経路が1通り(B)
- 3→2 への長さ2の経路が1通り(C)
(A)(B)(C) それぞれ同士を掛け合わせて合計すればよいが、この計算が行列の積算と一致する。
$A^3_{1,2} = A^1_{1,1}A^2_{1,2}+A^1_{1,2}A^2_{2,2}+A^1_{1,3}A^2_{3,2} = 2$
ただし、行列の積算は1回に $N^3$ かかり、とても$10^{18}$回は計算できない。 繰り返し二乗法を用いると、計算回数を $\log{10^{18}}$ に減らせる。
行列演算ならNumPyを使いたくなるが、オーバーフローするのかWAになる。以外と競プロでNumPy使う機会って無い。
def dot(a, b):
ret = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
ret[i][j] = sum(a[i][k] * b[k][j] for k in range(n)) % MOD
return ret
n, k = map(int, input().split())
dp = [list(map(int, input().split())) for _ in range(n)]
ans = [[0] * n for _ in range(n)]
for i in range(n):
ans[i][i] = 1
MOD = 1000000007
while k:
k, i = divmod(k, 2)
if i:
ans = dot(ans, dp)
dp = dot(dp, dp)
print(sum(sum(a) % MOD for a in ans) % MOD)
