Educational DP Contest N,O,P,Q,Rメモ

Educational DP Contest / DP まとめコンテスト - AtCoder

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]$ で求められる。

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$ となる。

• sum (21*21!/i!/(21-i)!), i=0 to 20 - Wolfram|Alpha

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}$$

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)$ の形となるので、簡略化した形で書ける

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使う機会って無い。