やー、フェネックだよー。
残りの6問はどれも難しいけど、解説していくよ。
実装例は省略するから自分で考えて書いてみてねー。

U問題 Grouping

$N$ 羽のうさぎをいくつかのグループに分ける。
うさぎのペア $i,j$ について、 $i$ と $j$ が同じグループに属していれば $a[i][j]$ 点を得る。
最高得点を求めよ。
制約： $N\leq 16$

解説

bitDPっぽいねー。
$dp[S]=($ 集合 $S$ に属するウサギのグループ分けの最高得点 $)$
としてみようか。あとはN問題とほぼ同じで、「どこで切るか」を考えると良さそうだね。
$dp[S]=\max(dp[T]+dp[S\setminus T])$
ただし、N問題と違って「切らない」っていう選択肢もありだから注意が必要だよ。
実装はメモ化再帰の方が簡単かなあ。
bitDPは0-indexedの方が都合がいいから、入力は0-indexedで与えられているものとするねー。

#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
long long f(int S){
	if(flag[S])return dp[S];
	flag[S]=1;
	//「切らない」場合を計算
	temp=0;
	rep(i,0,N)rep(j,i+1,N)if(bit(S,i)&&bit(S,j))temp+=a[i][j];
	fans=temp;
	//「どこで切るか」を考える
	for(Sの空でない真部分集合Tについて){
		fans=max(fans,f(T)+f(S^T));
	}
	return dp[S]=fans;
}
//ans=dp[(1<<N)-1];

for文で「部分集合 $T$ 」を動くところが問題なんだけど、すぐに思いつく方法としてはこういうのがあるね。

rep(T,0,S)if((T|S)==S){/* */}

でもこれは状態数 $O(2^N)$ 、遷移 $O(2^N)$ だから全体で $O(4^N)$ になってTLEなんだよねー。
実は「 $S$ の部分集合 $T$ 」だけをちょうどループ出来るようなこういうテクニックが存在するよ。

for(int T=S;T>=0;T--){
	T&=S;
	/* */
}

この演算は「-1」という操作を「1であるような一番下のbitを0に変えて、それより下のbitを全て1にする」という意味だと思うと納得できるんじゃないかな？
今回は、空集合と $S$ 自身を除くからこうだね。

for(int T=S;T>=0;T--){
	T&=S;
	if(T==S || T==0)continue;
	/* */
}

さて、計算量はどうなるかな？
このループは $2^{|S|}$ 回されるから、全ての $S$ について和を考えると
$\sum_S 2^{|S|} \\ =\sum_{i=0}^N \sum_{|S|=i} 2^{|S|} \\ =\sum_{i=0}^N 2^i*\#\{S \ | \ |S|=i\}\\ =\sum_{i=0}^N 2^i* {}_N C_i\\ =\sum_{i=0}^N 2^i*1^{N-i} * {}_N C_i\\ =(2+1)^N=3^N$
となって、つまり全体で $O(3^N)$ だね。これなら間に合うよ。
今回みたいにbitDPとかで役に立つbit演算のテクニックはこの記事が詳しいねー。
ビット列による部分集合表現【ビット演算テクニック Advent Calendar 2016 1日目】 - prime's diary

V問題 Subtree

$N$ 頂点の木がある。頂点をいくつか選んで黒く塗る。このとき黒く塗られた頂点たちは連結であるようにする。
各頂点について、その頂点を黒く塗るような方法は何通りあるか $\mod M$ で答えよ。
制約： $N\leq 10^5$ 、 $M\leq 10^9$

解説

1つの頂点についてだけ答えればいいんだったら、P問題と同じようにして $O(N)$ で求められるけど、これを各頂点でやってたら $O(N^2)$ になって間に合わないんだよねー。
この問題みたいに「木の各頂点について～～であるようなものを求めよ」って問題は全方位木DPっていう方法で解けることが多いよ。
こういう感じのアルゴリズムだね。
１．適当な頂点を根にして木DPで問題を解く
２．根を子に移して問題を解く。このとき、今までに求めた情報を使い回す
３．繰り返す
詳しいアルゴリズムについてはこのブログが詳しいよ。
†全方位木DP†について - ei1333の日記
他にもsnukeさんのツイートも参考になるねー。

全方位木DP、有向辺に関するDPだと思うのが分かりやすい。
1. 青い矢印は普通の木DPで下から順に求まる
2. 根から出る矢印は全部求まっているので、根に入る矢印も求められる（ここの計算量改善に総和とって引き算とか左右からの累積和とかが出てくる）
3. 同様に赤い矢印を上から順に求めていく pic.twitter.com/p4bl6rXzGn
— ꑄ꒖ꐇꌅꏂ🐈 (@snuke_) 2019年1月6日

実はこの問題は、全方位木DPを知ってても"やるだけ"じゃないんだよねー。
まずはこの図を見てもらおうか。
f:id:kyopro_friends:20190112031630p:plain
左側でまず頂点1を根として問題を解いて、次に根を頂点2に移して問題を解くことを考えるよ。
左側の図で頂点1を根として問題を解くときは、頂点1で集める情報は「頂点2、頂点3、頂点4」の部分木に関する情報だね。
だけど右側の図で頂点2を根とするときは、頂点1で集める情報は「頂点3、頂点4」の部分木に関する情報で、頂点2は親だから含まないねー。
同様に頂点3,4を根にすると、頂点1で集める情報は「頂点2,4」「頂点2,3」になるから、毎回情報を集め直してたら、ウニグラフ*1のときに全体で $O(N^2)$ になっちゃうんだよねー。
かといって「頂点2,3,4」に関する情報を集めておいて、そこから「頂点2に関する情報を取り除く」ということも出来ないよ。部分木の答えが $\mod M$ で0のときにゼロ除算になるからね。
どうすればいいかな？ちょっと問題をまとめ直しておこうか。
問題：頂点 $v$ と隣接する頂点の集合を $U$ とする。 $U$ に属する各頂点 $u$ に対し、部分木に関する答え $dp[u]$ が求まっている。このとき、各 $u$ について $\prod_{w\neq u}dp[w]$ を高速に求めよ。
これも「累積和」を使うと解くことが出来るんだよね。今回は掛け算だから「累積積」って言った方がいいかな？
こういう手順で求めるよ
１． $U$ の頂点に順序を付けて $1,2,\ldots,k$ とする。
２．前方 $1$ ～ $i$ の累積積 $cum1[i]$ と、後方 $i$ ～ $k$ の累積積 $cum2[i]$ を計算しておく
３．各 $u\in U$ について求める答えは $cum1[u-1]*cum2[u+1]$
こうすれば前計算 $O(|U|)$ 、本計算 $O(1)$ でできるから、全ての頂点についての答えが $O(|U|)$ で求められるよ。
ここまで工夫すれば全体での計算量は $O(N)$ になって間に合うねー。いやー大変だよー。

…………ちなみに、私は本番ではこれを思いつかなくて、 $O(N\log N)$ で解いたんだよねー。詳しくは解説しないけど、こんな感じの方法だよ。
１． $U$ の頂点に順序を付けて $1,2,\ldots,k$ とする。
２． $f(l,r,s)$ という関数を「区間 $[l,r)$ に属する頂点について答えたい。この部分以外に関する積は $s$ 」とする
３．区間の長さが1なら $s$ が答え。そうじゃないなら $m=(l+r)/2$ として、 $f(l,m,s'),f(m,r,s'')$ を再帰呼び出し
こうすると、二分法の要領で $O(|U|\log|U|)$ 、全体だと $O(N\log N)$ で求められるねー。やー、競技プログラミングの問題は解ければ正義だから、ゴリ押しも大事だよー？

W問題 Intervals

$M$ 個の区間 $[l[i],r[i]]$ と値 $a[i]$ が与えられる。
長さ $N$ の01列に対して次のようにスコアを定めるとき、その最大値を求めよ。
条件：区間 $[l[i],r[i]]$ に1が存在すれば $a[i]$ 点を得る
制約： $N\leq 2*10^5$ 、 $M\leq 2*10^5$

解説

やー、DPの問題としては全部の問題のなかでこれが一番難しいんじゃないかな？
この問題をDPで解くためには
$dp[i][*]=(*$ の条件下で $i$ 文字目まで決めたときの最高スコア $)$
みたいな感じにしようと考えるのが自然だよねー。このとき、スコアは「 $[1,i]$ に完全に含まれる区間のみ」を考えることにするよ。 $i+1$ 以降にはみ出す区間は、 $dp[i+1][*]$ 以降に影響を与えちゃうからね。
DPの状態として持つべき情報は何かを考えてみよう。 $dp[i][*]$ を考える時には、 $dp[i-1][*]$ の時から新たに $[l,i]$ という形の区間に関するスコアを考慮することになるから、この区間に1があるかどうかがわかる必要がありそうだねー。だから
$dp[i][j]=(i$ 文字目まで決めて、最後に1であるのが $j$ 文字目であるようなものの最高スコア $)$
というものを考えてみようか。
$dp[i][j]\\ = \left\{ \begin{array}{ll} dp[i-1][j]+(j\in [l,i]となる区間に関するスコアの和) & (j< i) \\ \max \{ dp[i-1][j] | 0\leq j< i\}+([l,i]となる区間に関するスコアの和) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ & (j=i) \end{array} \right.$
として一応は計算できるけど、これをこの形のまま実装すると $O((N+M)N)$ かかっちゃうねー。
遷移をよく見ると、これは次の3つのステップに分解できるよ。
１． $dp[i][*]$ に $dp[i-1][*]$ をコピーする
２． $dp[i][i]=\max \{ dp[i-1][j] | 0\leq j< i\}$ とする
３． $[l,i]$ の各区間について、 $j\in[l,i]$ なる $j$ の範囲で $dp[i][j]$ にスコアを加える
ステップ１は $dp[i][*]$ と $dp[i-1][*]$ で同じ配列を使い回すことで省略できて、ステップ２は区間maxと1点更新、ステップ３は区間addだから、starry sky treeというものを使うとそれぞれ $O(\log N)$ 、全体で $O((N+M)\log N)$ にできるよ。
starry sky treeに関する説明は省略するけど、区間addと区間maxができるようにちょっと工夫したセグメント木のことだねー。遅延セグメント木が上位互換になってるから、そっちが使えるならそれでも十分だよ。

X問題 Tower

$N$ 個のブロックがあり、 $i$ 番目のブロックは重さ $w[i]$ 、丈夫さ $s[i]$ 、価値 $v[i]$ である。
これらのブロックを1列に積み重ねて、次の条件が満たされるような塔を作る。塔に含まれるブロックの価値の和の最大値を求めよ。
条件：塔を構成するどのブロックの丈夫さも、それより上にあるブロックの重さの合計以上である
制約： $N\leq 10^3、s[i]\leq 10^4$

解説

ナップサックDPみたいに
$dp[i][j]=(i$ 番目までのブロックを使って重さ $j$ 以下で作れる塔の最大価値 $)$
としたいけど、丈夫さに関する条件を考えると、次のブロックが使えるかどうかわからないからうまくいかないねー。
実はこの問題は「ブロックをうまく並び替えることで、塔に使うブロックの順序を決めることができる（＝次に使うブロックは、使うなら一番下）」らしいよ。やー、なんでこんなこと思いつくのかなー？
どういう順序で使えばいいか考えるためにこういうのを考えてみるよ。
f:id:kyopro_friends:20190112002741p:plain
そういうわけで $s[i]+w[i]$ でソートしたら、あとは最初に言ったDPができるね。
ちなみにこれは「 $s[i]+w[i]$ が大きいものの方が上になってたら、入れ替えても影響がない」という方針でも証明ができて、その方が簡単なんだけど、「 $s[i]+w[i]$ が小さいものが上になったほうがよさそう」ってわかってないと思いつけないから、ちょっと難しいかもねー。
計算量は $O(N\max s[i])$ だよ。

Y問題 Grid 2

2次元のマスを移動する。 $(i,j)$ からは $(i+1,j)$ か $(i,j+1)$ に移動できる。
ただし $N$ 個の壁があり、そのマスには移動できない。 $i$ 番目の壁の座標は $(r[i],c[i])$ である。
$(1,1)$ から $(H,W)$ へ移動する場合の数を $\mod 10^9+7$ で求めよ。
制約： $H,W \leq 10^5$ 、 $N\leq 3*10^3$

解説

壁は予め辞書順かマンハッタン距離順にソートしておこうか。それから二項係数もでてきそうだから「壁がない時(0,0)から(x,y)まで移動する場合の数＝ ${}_{x+y}C_x$ 」のことを $f(x,y)$ と書くことにしとくよ。階乗とその逆元を $O(H+W)$ で前計算しておくことで、 $f(x,y)$ は $O(1)$ で答えられるとしていいね。（やらなくても間に合うけどねー）
一瞬座標圧縮にも見えるけど、圧縮して無くなったマスだけを通る経路をうまく数えられないからそれはダメそうだねー。
$N$ が小さければ
$dp[i]=(i$ 番目の壁を通って、スタートからゴールまで移動する場合の数 $)$
として包除原理を使うことでも解けるけど、今回は無理だよ。
求めるものの余事象を考えると、「壁のマスを1回以上通って、ゴールまで行く場合の数」になるわけだけど、「1つ以上あるか？」とくれば、W問題と同じように「最後に/最初に〇〇したもののindex」を状態に持てば良さそうだねー。
そこで
$dp[i]$
$=($ 最初にぶつかる壁が $i$ である場合の数 $)$
$=(1～i-1$ 番目の壁を避けて $i$ 番目の壁の位置にたどり着く場合の数 $)$
というのを考えるよ。
$dp[i]$
$=f(r[i],c[i])-(i-1$ 番目までの壁に1回以上ぶつかって壁 $i$ の位置にたどり着く場合の数 $)$
で、
$(i-1$ 番目までの壁に1回以上ぶつかって壁 $i$ の位置にたどり着く場合の数 $)$
$＝\sum_{j=1}^{i-1}($ 壁 $j$ で初めて壁にぶつかって壁 $i$ の位置にたどりつく場合の数 $)$
$＝\sum_{j=1}^{i-1} (1～j-1$ 番目の壁を避けて $j$ 番目の壁の位置にたどり着く場合の数 $)\times(j$ 番目の壁の位置から $i$ 番目の壁の位置まで壁を無視して移動する場合の数 $)$
$＝\sum_{j=1}^{i-1} dp[j]*f(r[i]-r[j],c[i]-c[j])$
となるから、遷移は $O(N)$ でできるね。
ゴールまでの場合の数も同様にしてできるから、計算量は全体で $O(N^2)$ だね。

Z問題 Frog 3

$N$ 個の足場がある。
足場 $i$ からは足場 $i+1,i+2,\ldots,N$ のいずれかに移動でき、足場 $i$ から足場 $j$ に移動するコストは $(h[i]-h[j])^2+C$ である。
足場 $1$ から足場 $N$ に移動するまでの最小コストを求めよ。
制約： $N\leq 2*10^5$ 、 $C\leq 10^{12}$ 、 $h[i]\leq10^6$

解説

やー、この問題はCHT(Convex Hull Trick)を知ってれば、見た瞬間「CHTだ」ってなる問題だねー。いわゆる「知識ゲー」ってやつかな？
まずはCHTっていうのは、こういうのだねー。

区間 $[L,R]$ と直線群 $S$ が与えられたとき、次の2種類のクエリを高速に処理するアルゴリズムをCHTという。
１．直線追加クエリ： $S$ に直線 $Ax+B$ を加える
２．最小値クエリ： $x\in [L,R]$ に対し $\min\{f(x) \ | \ f\in S\}$ を求める

今回は追加される直線の傾き $A$ と最小値クエリで問われる値 $x$ のどちらもが単調だから、dequeを使って書けるんだけど、せっかくだからLi Chao Segment Treeを実装したよ。これはどちらのクエリについても単調性を問わないものだねー。
実装はこのブログを参考にしたよ。
傾きの単調性が要らない Convex Hull Trick - kazuma8128’s blog

Li Chao Segment Tree
$N$ 点集合 $P=\{x_i\}$ と直線群 $S$ が与えられたとき、次の2種類のクエリを $O(\log N)$ で処理するデータ構造
１．直線追加クエリ： $S$ に直線 $Ax+B$ を加える
２．最小値クエリ： $x\in P$ に対し $\min\{f(x) \ | \ f\in S\}$ を求める

元の問題の解説に戻ろうか。
A問題と同じ素直なDPを考えると
$dp[i]=($ 足場 $i$ にたどり着くまでの最小コスト $)$
$dp[i]=\min\{dp[j]+(h[i]-h[j])^2+C\ |\ 1\leq j< i\}$
となって遷移が $O(N)$ だから全体で $O(N^2)$ になって間に合わないんだけど、遷移式をよく見て変形すると
$dp[j]+(h[i]-h[j])^2+C\\ =-2h[j]*(h[i])+(dp[j]+h[j]^2)+(h[i]^2+C)$
となって、最後の部分をminの外に出して
$dp[i]=\min\{-2h[j]*(h[i])+(dp[j]+h[j]^2)\ |\ 1\leq j< i\}+(h[i]^2+C)$
となるねー。
わかりやすくするために $A_j=-2*h[j]$ 、 $B_j=dp[j]+h[j]^2$ とおくと、minの部分は
$\min\{A_j*(h[i])+B_j\ |\ 1\leq j< i\}$
つまり「 $A_jx+B_j$ という直線群の $x=h[i]$ における最小値を求めよ」という問題になってCHTで解けるというわけさ。
計算量は、単調性を仮定したdequeを使った実装だと $O(N)$ 、単調性を使わないLi Chao Segment Treeだと $O(N\log N)$ だね。

やー、これで26問全部を解説したわけだけど、どうだったかなー？
私たちは本番ではTWXYZの5問を残して21完で、残った5問は主にsnukeさんの解説を参考にして解説ACしたよ。
ꑄ꒖ꐇꌅꏂ🐈 on Twitter: "DPコン、解法全部書いた。 https://t.co/BqSnOQIkbR"
解説AC含めて全問ACすれば黄色くらいの実力になるんじゃないかな？　私たちが黄色になったばっかりだしねー。
それじゃあねー。

EDPC解説目次へ戻る

*1:1つの頂点を中心にして、そこからたくさんの辺が出てるようなグラフ

2019-01-12

EDPC解説 M～T

EDPC解説目次へ戻る

カラカルよ。M問題～T問題を解説するわ。
このあたりから計算量を気にして高速化をしないといけない問題が増えてきて大変だけど、ついてこれるかしら？

M問題 Candies

$N$ 人の子供にちょうど $K$ 個の飴を配る方法は何通りあるか $\mod 10^9+7$ で求めよ。
ただし $i$ 番目の子供には $a[i]$ 個以下しか渡すことができない。
制約： $N\leq 10^2$ 、 $K\leq 10^5$

解説

$dp[i][j]=(i$ 番目までの子供たちに $j$ 個の飴を配る場合の数 $)$
ってDPをやるだけね。

dp[0][0]=1;
rep(i,1,N+1)rep(j,0,K+1){
	rep(k,0,a[i]+1)if(j-k>=0)dp[i][j]=(dp[i][j]+dp[i-1][j-k])%MOD;
}

……とはいかないのよねぇ。
これだと計算量が $O(NK^2)$ になって全然間に合わないわ。
そこで状態遷移のところをよくみてみるわ。数式で書くと、これってこういうことよね。
$\displaystyle{dp[i][j]=\sum_{k=\max(0,j-a[i])}^j dp[i-1][k]}$
これは $dp[i-1][*]$ の区間の和だから、累積和を使えば高速化することができるわね。

dp[0][0]=1;
rep(i,1,N+1){
	cum[0]=0;
	rep(j,1,K+1+1)cum[j]=(cum[j-1]+dp[i-1][j-1])%MOD;
	//cum[j]=dp[i-1][0]+...+dp[i-1][j-1]
	rep(j,0,K+1)dp[i][j]=(cum[j+1]-cum[max(0,j-a[i])]+MOD)%MOD;
}
ans=dp[N][K];

計算量は $O(NK)$ よ。

N問題 Slimes

$N$ 匹のスライムが1列に並んでいる。 $i$ 番目のスライムの大きさは $a[i]$ である。
「隣り合う2匹のスライムを合体させる」という操作を繰り返して1匹のスライムにまとめることを考える。
合体後のスライムの大きさの和と等しいコストがかかる。最小コストを求めよ。
制約： $N\leq 400$

解説

この問題は逆から考えると簡単ね。つまり問題全体をこう読み替えるわけ。
「
1匹のスライムがいる。大きさは $\sum a[i]$ である。
「スライムを2匹に分解する」という操作を繰り返して、大きさが端から順に $a[i]$ であるような $N$ 匹のスライムを作ることを考える。
分解には分解前のスライムの大きさと等しいコストがかかる。最小コストを求めよ。
」
切るべき箇所は、最終的なスライムの切れ目にあたる $N-1$ 箇所のどれかね。
どれが最小になるか分かればいいから
$dp[l][r]=($ 区間 $[l,r]$ に相当するスライムが1匹にまとまっているとき、それを分解するために必要な最小コスト $)$
が分かればいいわね。実装はメモ化再帰が簡単だと思うわ。

int f(int l,int r){
	if(flag[l][r])return dp[l][r];
	flag[l][r]=1;
	if(l==r)return 0;
	//どこで切るか全通り試す
	fans=INF;
	rep(m,l,r)fans=min(fans,f(l,m)+f(m+1,r));
	return dp[l][r]=fans+(a[l]～a[r]の和);//予め累積和を計算しておく
}
//ans=f(1,N);

状態数が $O(N^2)$ 、遷移が $O(N)$ だから計算量は $O(N^3)$ ね。

O問題 Matching

男女が $N$ 人ずついる。男女からなるペアを $N$ 組つくりたい。
男性 $i$ と女性 $j$ の相性 $a[i][j]$ が0か1で与えられ、相性が0であるような2人はペアになることができない。
ペアの作り方は何通りあるか？ $\mod 10^9+7$ で求めよ。
制約： $N\leq 21$

解説

bitDPというテクニックを使う問題ね。
bitDPというのは、集合を数に変換して状態(=添字)として持つようなDPのことよ。
例えば $\{0,2,3\}$ という集合は $2^0+2^2+2^3=13$ という数に変換して、「数 $i$ が集合に属しているか」と「 $i$ bit目が1か」を対応させるわ。
こうすると、「集合として $S\subset T$ 」⇒「数として $S\leq T$ 」になるから

rep(S,0,1<<N){
	/*処理*/
}

というふうに、DPの遷移が単純なループで書けることが多いのよね。
この問題もこのことを知っていれば簡単よ。
$dp[i][S]=($ 男性は $i$ 人目までで、既にペアになった女性の集合が $S$ であるような場合の数 $)$
としてDPするわ。
今まではずっと1-indexedでやってきたけど、bitDPは0-indexedの方が都合がいいから、入力は0-indexedで与えられているものとするわ。

#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
dp[0][0]=1;
rep(i,1,N+1)rep(S,0,1<<N){
	rep(j,0,N)if(bit(S,j)==1&&a[i-1][j]==1){
		dp[i][S]=(dp[i][S]+dp[i-1][S^(1<<j)])%MOD;
	}
}
ans=dp[N][(1<<N)-1];

……とすると、これは $O(2^N N^2)$ でTLEなのよねえ。
少し考えると「既にペアになった女性の集合がS」なら「bitpopcount $(S)$ 人目までをチェックした」ってことになるから、 $i$ を状態として持つ必要は無いことがわかるわ。

#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
dp[0]=1;
rep(S,1,1<<N){
	i=__builtin_popcount(S);
	rep(j,0,N)if(bit(S,j)==1&&a[i-1][j]==1)dp[S]=(dp[S]+dp[S^(1<<j)])%MOD;
}
ans=dp[(1<<N)-1];

計算量は $O(2^N N)$ よ。

詳しくは説明しないけど、この問題を配るDPで解くときは、次のコードで実は $O(2^N N)$ になるわ。枝刈りが本質的に計算量を改善する例ね。

#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
dp[0][0]=1;
//一見するとO(2^N N^2)だけど……
rep(i,0,N)rep(S,0,1<<N)if(dp[i][S]){//<-ここのif文の枝刈りが効いてO(2^N N)に落ちる
	rep(j,0,N)if(bit(S,j)==0&&a[i][j]==1){
		dp[i+1][S^(1<<j)]=(dp[i][S^(1<<j)]+dp[i][S])%MOD;
	}
}
ans=dp[N][(1<<N)-1];

P問題 Independent Set

$N$ 頂点の木が与えられる。頂点を白か黒で塗る。
隣接する頂点どうしをともに黒で塗ることはできない。
塗り方は何通りあるか？ $\mod 10^9+7$ で求めよ。
制約： $N\leq 10^5$

解説

木DPというやつね。部分木に関する情報を集めて元の木に関する問題に答えるようなDPよ。
まず適当な頂点を1つ選んで根とするわ。
各頂点は子が何色かによって塗れる色が決まるから、各部分木について、根が黒/白の塗り方の数がわかればいいわね。
$dp[i][j]=($ 頂点 $i$ を( $j$ ?黒く:白く)塗ったとき、 $i$ を親とする部分木の塗り方の場合の数 $)$
とすると、
$\displaystyle{dp[i][0]=\prod_{jはiの子} (dp[j][0]+dp[j][1])}$
$\displaystyle{dp[i][1]=\prod_{jはiの子} dp[j][0]}$
となるわ。
実装は根からたどれるメモ化再帰が簡単じゃないかしら。

void f(int i){
	if(flag[i])return;
	flag[i]=1;
	dp[i][0]=1;
	dp[i][1]=1;
	for(iの子jについて){
		f(j);
		dp[i][0]=dp[i][0]*(dp[j][0]+dp[j][1])%MOD;
		dp[i][1]=dp[i][1]*dp[j][0];
	}
}
//頂点1を根とすると
//f(1);
//ans=(dp[1][0]+dp[1][1])%MOD;

計算量は $O(N)$ ね。

Q問題 Flowers

$N$ 本の花が一列に並んでいる。花 $i$ は高さ $h[i]$ 、美しさ $a[i]$ である。
左から見て単調増加になるように花を選ぶ時、美しさの最大値を求めよ。
制約： $N\leq 2*10^5$ 、 $h[i]$ は $1$ ～ $N$ で相異なる

解説

$i$ 番目までの選び方を決めた時、次の決め方に影響するのは最後に選んだ花だけだから
$dp[i][j]=(i$ 番目まで使って最後の高さが $j$ であるようなものの美しさの最大値 $)$
というのを考えるのが自然よね。
$dp[i][j]= \begin{cases} \max\{dp[i-1][k]|0\leq k< j\}+a[i] & (h[i]==j\text{のとき})\\ dp[i-1][j] & (\text{それ以外}) \end{cases}$
1回あたり更新するのは1箇所だから、 $i$ を状態にもつ必要はなくて、配列を使い回すことができるわ。
あとは、区間maxが高速に計算できればいいから、セグメント木を使えばできるわね。
セグメント木の説明は省略するけど、区間に対する操作が高速にできるようなデータ構造のことよ。

rep(i,1,N+1){
	temp=getmax(0,h[i]);//dp[0],...,dp[h[i]-1]のmax
	setvalue(h[i],temp+a[i]);//dp[h[i]]をtemp+a[i]にする
}
ans=getmax(0,N+1);

セグメント木は区間maxの計算と値の変更をどちらも $O(\log N)$ でできるから、計算量は $O(N\log N)$ になるわね。

もしこの問題で全ての $a[i]$ が1なら、これは最長増加部分列と全く同じ問題ね。
つまり最長増加部分列問題もこの解き方で解けるわ。

R問題 Walk

$N$ 頂点単純有向グラフ $G$ の隣接グラフ $A$ が与えられる。
長さ $K$ のパスがいくつあるか $\mod 10^9+7$ で求めよ。
ただし同じ辺を複数回通るものも含める。
制約： $N\leq 50、K\leq 10^{18}$

解法

長さKのパスを考えるのだから、とりあえず始点と終点を状態として
$dp[n][i][j]=($ 頂点 $i$ から頂点 $j$ へ行く長さ $n$ のパスの個数 $)$
というのを考えてみるわ。状態遷移は
$dp[n][i][j]=\sum_k dp[n-1][i][k]*a[k][j]$
となるわね。ところで、この積の形、よくみると行列の積と同じね！
$dp[n][i][j]$ を $(i,j)$ 成分とする行列を $DP_n$ と書くことにすると、さっきの漸化式は
$DP_n=DP_{n-1} A$
になるわ。
$DP_0$ は明らかに単位行列だから、 $DP_n=A^n$ ね。
求める答えは $\sum_{i,j} dp[K][i][j]$ だから、 $A^K$ を計算すれば求められるわよ。

matrixpow(A,K,MOD);//Aをmod MODでK乗する
rep(i,1,N+1)rep(j,1,N+1)ans=(ans+A[i][j])%MOD;

行列の積は1回あたり $O(N^3)$ 、繰り返し二乗法を使えば積を計算する回数は $O(\log K)$ だから、 $O(N^3\log K)$ で求められるわね。

「行列の積と同じ式になってると気づくのは無理じゃない？」
そうね、こればっかりは知ってるかどうかになりそうね。
行列累乗で解く問題は、次の２つのポイントを抑えておくといいわ。どっちも決め手になるほどじゃないけど……
・ポイント１：制約をみる
$N\leq 50$ くらい、 $K$ は $10^9$ とか $10^{18}$ とかの大きな値、みたいな制約の問題は、サイズ $N\times N$ の行列を $K$ 乗するかも。
・ポイント２：繰り返し
今回の状態遷移の式を見ると、回数 $n$ が遷移に影響しないわね。こういうふうに同じ状態遷移を何度も繰り返すものは、行列累乗かも。

S問題 Digit Sum

1以上 $K$ 以下の数のうち、十進表記での各桁の数字の和が $D$ の倍数であるものはいくつあるか？
$\mod 10^9+7$ で求めよ。
制約： $K\leq10^{10^4}$ 、 $D\leq 10^2$

解説

桁DPね。
桁DPっていうのは本質的に1種類しかなくて、基本的にこの方針で実装することになるわ。
$dp[i][f][*]=($ 上から $i$ 桁目まで決めて、 $K$ より小さいことが確定して $(f$ ?いて:いなくて $)$ 、条件*を満たすようなもの $)$
場合によっては下の桁から決めることもあるけど、まあ似たようなものね。
今回は桁和が $D$ の倍数であるものの個数を調べたいから、「既に決まっている部分の桁和の $\mod D$ 」という状態を追加で持てばいいわよ。
桁DPについてはこのサイトの説明がわかりやすいと思うわ。
桁DP入門 - ペケンペイのブログ
桁DPはもらうDPよりも配るDPの方が圧倒的に書きやすいのよね。実はいままでA問題からR問題までは全部もらうDPで説明してたんだけど、気付いてたかしら？

//K[i]でKの先頭からi文字目の数が得られるとする
dp[0][0][0]=1;
rep(i,0,N)rep(j,0,D){
	rep(dig,0,10)dp[i+1][1][(j+dig)%D]=(dp[i+1][1][(j+dig)%D]+dp[i][1][j])%MOD;
	rep(dig,0,K[i+1])dp[i+1][1][(j+dig)%D]=(dp[i+1][1][(j+dig)%D]+dp[i][0][j])%MOD;
	dp[i+1][0][(j+K[i+1])%D]=(dp[i+1][0][(j+K[i+1])%D]+dp[i][0][j])%MOD;
}
ans=(dp[n][0][0]+dp[n][1][0]-1+MOD)%MOD;//答えに0が含まれるのでそれを除くために-1

計算量は、基数を $B$ として $O(DB\log_B K)$ よ。

T問題 Permutation

不等号'<''>'のいずれかからなる長さ $N-1$ の文字列 $s$ が与えられる。
$1$ ～ $N$ の並び替え $p$ であって、次の条件を満たすものは何個あるか？
条件： $p$ の隣接する要素を比較し、順に不等号を書いたとき、それが $s$ と一致する
制約： $N\leq 3*10^3$

解説

$dp[i][j][S]=(i$ 番目まで決めたとき、最後の数が $j$ で、使用済みの数の集合が $S$ であるような場合の数 $)$
というのはすぐ思いつくけど、 $N\leq 3000$ だからこれは当然無理ね……。
よく考えると、次に決める数は、前に決める数との大小関係さえわかっていればいいから
$dp[i][j]=(i$ 番目まで決めたとき、 $i$ 番目の数より大きいものが $j$ 個残っているような場合の数 $)$
というのを考えればうまくいきそうね。

rep(j,0,N)dp[1][j]=1;
rep(i,2,N+1){
	if(s[i-1]=='<'){
		rep(j,0,N-i+1)rep(k,j+1,N-i+2)dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
	}else{
		rep(j,0,N-i+1)rep(k,0,j+1)dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
	}
}
ans=dp[N][0]

…………と言いたいところだけど、これもまだ $O(N^3)$ なのよね。
M問題と同じように最後の部分で累積和を使うと $O(N^2)$ に出来るわ

rep(j,0,N)dp[1][j]=1;
rep(i,2,N+1){
	cum[0]=0;
	rep(j,1,N-i+3)cum[j]=(cum[j-1]+dp[i-1][j])%MOD;
	if(s[i-1]=='<'){
		rep(j,0,N-i+1)dp[i][j]=(cum[N-i+2]-cum[j+1]+MOD)%MOD;
	}else{
		rep(j,0,N-i+1)dp[i][j]=cum[j+1];
	}
}
ans=dp[N][0];

ふぅ、これで私の担当範囲はおしまいね。最後の6問はフェネックが解説してくれるわ。
……もしかしてフェネックが何かしてくれるなんて珍しいことなんじゃないかしら？

EDPC解説目次へ戻る

2019-01-12

EDPC解説 F～L

EDPC解説目次へ戻る

はいはーい、サーバルだよ！
F問題～L問題の解説をしていくよ！　よろしくね。

F問題 LCS

2つの文字列 $s$ , $t$ が与えられる。
$s$ , $t$ の共通部分列であって、最長のものを1つ求めよ。
制約： $|s|,|t|\leq 3*10^3$

解説

いきなり難しい問題だね……。
「求める文字列の長さ」だけを先に求めておいて、実際の文字列はそれを手がかりに構成していくよ。
$dp[i][j]=(s$ を $i$ 文字目、 $t$ を $j$ 文字目までみた時の最長共通部分列の長さ $)$
とすると、
$s[i]==t[j]$ のときこの文字は使ったほうがいいから $dp[i-1][j-1]+1$ 、
そうじゃないときは、どっちかの最後の1文字は使わないから $\max(dp[i-1][j],dp[i][j-1])$
になるね。

//slenはSの長さ、tlenはTの長さとする
rep(i,1,slen+1)rep(j,1,tlen+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]);
}
//dp[slen][tlen]が求める長さ

具体的に文字列を作るのはDP配列を逆にたどればできるよ。
もし $s[i]==t[j]$ なら、求める最長共通部分列の最後の文字は $s[i]$ で、それより前の部分は $dp[i-1][j-1]$ の結果からわかって、
そうじゃないならどっちかの最後の文字は使わないから、 $dp$ の値が減らない方に移動すればいいね。

len=dp[slen][tlen];
i=slen;
j=teln;
while(len>0){
	if(s[i]==t[j]){
		ans[len]=s[i];
		i--;
		j--;
		len--;
	}else if(dp[i][j]==dp[i-1][j]){
		i--;
	}else{
		j--;
	}
}

計算量は $O(|s||t|)$ だよ。
イメージとしてはこんな感じ！

G問題 Longest Path

有向閉路を持たない $N$ 頂点 $M$ 辺の有向グラフ $G$ が与えられる。
$G$ の有向パスの最長経路を求めよ。
制約： $N\leq 10^5$ 、 $M\leq 10^5$

解説

これをもらうDP/配るDPで書くのはちょっと難しいね。トポロジカルソートっていうのが必要になるのかな？
こういうときはメモ化再帰で書くといいよ！
$f(x)=(x$ を始点とする最長経路 $)$ とすると
$f(x) = \begin{cases} 0 & (x\text{が葉のとき}) \\ \max\{f(y)+1|x\text{から}y\text{への辺があるような}y\} \ \ \ \ \ \ \ \ \ \ \ \ \ \ & (\text{そうでないとき}) \end{cases}$
として再帰で計算できるよ。答えは $\max\{f(x)\}$ だね。
再帰の深さが $O(N)$ くらいになるけど、スタックオーバーフローはしないみたい。

int f(int x){
	if(flag[x])return dp[x];
	flag[x]=1;
	fans=0;
	for(xからyへの辺があるようなy){
		fans=max(fans,f(y)+1);
	}
	return dp[x]=fans;
}
//ans=0;
//rep(i,1,N+1)ans=max(ans,f(i));

計算量は $O(N+M)$ だよ。

H問題 Grid 1

2次元のマスを移動する。 $(i,j)$ からは $(i+1,j)$ か $(i,j+1)$ に移動できる。
ただし $a[i][j]$ が'#'であるマスには移動できない。
$(1,1)$ から $(H,W)$ へ移動する場合の数を $\mod 10^9+7$ で求めよ。
制約： $H,W \leq 10^3$

解説

$(H,W)$ へ行く場合の数は、 $(H-1,W),(H,W-1)$ へ行く場合の数の和だね。だから
$dp[i][j]=((1,1)$ から $(i,j)$ へ移動する場合の数の $\mod 10^9+7)$
とすれば解けそうだよ。

dp[1][1]=1;
rep(i,1,H+1)rep(j,1,W+1)if(!(i==1&&j==1)){
	if(a[i][j]=='#')dp[i][j]=0;
	else dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;
}
ans=dp[H][W];

計算量は $O(HW)$ だよ。

I問題 Coins

$N$ 枚のコインがあり、コイン $i$ は確率 $p[i]$ で表、 $1-p[i]$ で裏が出る。
全てのコインを投げたとき、表が出たコインの数の方が多い確率を求めよ。
制約： $N\leq 2999$ 、 $N$ は奇数

解説

$dp[i]=(i$ 枚目のコインまで投げたとき、表が出たコインの数の方が多い確率 $)$
だと、次に裏が出たときでもまだ表のほうが多いかどうかがわからないからうまくいかないね。
表が出た枚数がわかってれば大丈夫そうだから
$dp[i][j]=(i$ 枚目のコインまで投げたとき、表が $j$ 枚でる確率 $)$
で出来そうだよ。
$dp[i][j]= \\ (i-1\text{枚目のコインまで投げたとき、表が}j\text{枚でる確率})\times(i\text{枚目のコインが裏である確率})\\ +(i-1\text{枚目のコインまで投げたとき、表が}j-1\text{枚でる確率})\times(i\text{枚目のコインが表である確率})$
でちゃんと計算できるね。
答えは $\sum_{j=(N+1)/2}^{N}dp[N][j]$ だよ。

dp[0][0]=1;
rep(i,1,N+1)rep(j,0,i+1){
	if(j>0)dp[i][j]=dp[i-1][j]*(1-p[i])+dp[i-1][j-1]*p[i];
	else dp[i][j]=dp[i-1][j]*(1-p[i]);
}
ans=0;
rep(j,N/2+1,N+1)ans+=dp[N][j];

計算量は $O(N^2)$ だね。

J問題 Sushi

$N$ 個の皿があり、皿 $i$ には寿司が $a[i]$ 個乗っている。
全ての寿司を食べるまで次の操作を繰り返すとき、操作の回数の期待値を求めよ。
操作：皿をランダムに1つ選ぶ。選んだ皿に寿司が乗っていれば、そのうち1つを食べる。
制約： $N\leq 300$ 、 $1\leq a[i]\leq 3$

解説

まずは状態をどうやって持つか考えよう。
普通にやると $dp[a0][a1][a2][a3]\ldots$ みたいに添字が $N$ 個欲しくなっちゃう。
でも例えば「皿1に寿司が2個、皿2に寿司が1個」という状態と「皿1に寿司が1個、皿2に寿司が2個」という状態だと、操作回数の期待値は同じになるよね。
よく考えると、「どの皿に何個あるか」っていうところまでわかる必要はなくて、「1個の皿がいくつ、2個の皿がいくつ、3個の皿がいくつ」だけで期待値は決まることがわかるよ。
そこで
$dp[c1][c2][c3]=($ 1個の皿が $c1$ 枚、2個の皿が $c2$ 枚、3個の皿が $c3$ 枚あるとき、全て食べるまでの操作回数の期待値 $)$
というのを考えるよ。
えーっと、これはループで書くのが難しいからメモ化再帰で書く方がいいね。

$dp[c1][c2][c3]=\\ 1\\ +dp[c1-1][c2][c3]*(\text{1個の皿が選ばれる確率})\\ +dp[c1+1][c2-1][c3]*(\text{2個の皿が選ばれる確率})\\ +dp[c1][c2+1][c3-1]*(\text{3個の皿が選ばれる確率})\\ +dp[c1][c2][c3]*(\text{0個の皿が選ばれる確率})$

再帰なのに同じ状態に戻ってきちゃう！
けど、これは $dp[c1][c2][c3]$ の項を移項すれば解消できるね。

$dp[c1][c2][c3]=\\ 1/(1-(0個の皿が選ばれる確率))\\ +dp[c1-1][c2][c3]*(\text{1個の皿が選ばれる確率})/(1-(0個の皿が選ばれる確率))\\ +dp[c1+1][c2-1][c3]*(\text{2個の皿が選ばれる確率})/(1-(0個の皿が選ばれる確率))\\ +dp[c1][c2+1][c3-1]*(\text{3個の皿が選ばれる確率})/(1-(0個の皿が選ばれる確率))$

double f(int c1,int c2,int c3){
	if(c1==0&&c2==0&&c3==0)return 0;
	if(flag[c1][c2][c3])return dp[c1][c2][c3];
	flag[c1][c2][c3]=1;
	fans=1/(1-(double)(N-c1-c2-c3)/N);//doubleにキャストしないと整数除算になっちゃう
	if(c1>0)fans+=f(c1-1,c2,c3)*c1/N/(1-(double)(N-c1-c2-c3)/N);
	if(c2>0)fans+=f(c1+1,c2-1,c3)*c2/N/(1-(double)(N-c1-c2-c3)/N);
	if(c3>0)fans+=f(c1,c2+1,c3-1)*c3/N/(1-(double)(N-c1-c2-c3)/N);
	return dp[c1][c2][c3]=fans;
}
//rep(i,1,N+1)c[a[i]]++;
//ans=f(c[1],c[2],c[3]);

計算量は $O(N^3)$ だよ。

K問題 Stones

$N$ 個の元をもつ数の集合 $A$ と、石の山があり、二人でゲームをする。
「 $x\in A$ を選び、石の山からちょうど $x$ 個の石を取り除く」という操作を交互にして、先に操作できなくなったほうが負けとなる。
最初に石が $K$ 個あるとき、どちらが勝つか答えよ。
制約： $K\leq 10^5$ 、 $N\leq 10^2$

解説

ゲームの基本的な問題だよ！
石の個数によって勝敗が決まるから、
$dp[i]=($ 石の個数がi個のとき直後の手番の人が勝てるか？ $)$
を考えるよ。これがYesになる状態を「勝ち状態」、Noになる状態を「負け状態」と呼ぶことにするね。
自分の手番の後で残る石の個数としてありえるものについて考えて、どれか1つでも「負け状態」になるなら、それを相手に渡せば良くて、全部「勝ち状態」ならどうやっても相手に「勝ち状態」を渡すことになるから自分は負けだよ。

rep(i,1,K+1){
	rep(j,1,N+1)if(i-a[j]>=0&&dp[i-a[j]]==0)dp[i]=1;
}
//ans=dp[K];

計算量は $O(NK)$ だね。

L問題 Deque

長さ $N$ の数列 $a$ が与えられ、二人でゲームをする。
「 $a$ の先頭か末尾の数を取り除く。取り除いた数と同じ点数を得る」というルールである。
ゲーム終了時の先手の総得点を $X$ 、後手の総得点を $Y$ とする。先手は $X−Y$ を最大化しようとし、後手は $X−Y$ を最小化しようとする。二人が最適に行動するとき、 $X−Y$ を求めよ。
制約： $N\leq 3*10^3$

解説

太字で書いてあるところは要するに「(自分の点数)－(相手の点数)を最大化しようとする」だね！
前から取ったほうがいいか後ろから取ったほうがいいかは、残った数を使ってのゲームの結果が分かれば判断できるから、
$dp[i][j]=($ 区間 $[i,j]$ が残ってるときの「次の手番の人の得点－そうじゃない方の人の得点」)
とすればよさそうだね。実装はメモ化再帰が簡単かな。

int f(int l,int r){
	if(flag[l][r])return dp[l][r];
	flag[l][r]=1;
	if(l==r)return dp[l][r]=a[l];
	return dp[l][r]=max(a[l]-f(l+1,r),a[r]-f(l,r-1));
}
//ans=f(1,N);

計算量は $O(N^2)$ だね。

ふー、大変だった！　これで私の担当はおしまい。
次はカラカルがM問題からを解説してくれるよ！

EDPC解説目次へ戻る

2019-01-12

EDPC解説 A～E

EDPC解説目次へ戻る

アライさんなのだ！
EDPCのA問題～E問題を解説するのだ！

A問題 Frog 1

$1$ ～ $N$ の番号がついた足場がある。
足場 $i$ からは足場 $i+1$ か $i+2$ に移動でき、足場 $i$ から足場 $j$ に移動するコストは $|h[i]-h[j]|$ である。
足場 $1$ から足場 $N$ に移動するまでの最小コストを求めよ。
制約： $N\leq 10^5$

解説

足場 $N$ にたどり着くには足場 $N-1$ から来るか足場 $N-2$ から来るしかないのだ！
だから答えは
「足場 $N-1$ にたどり着くまでの最小コスト $+|h[N-1]-h[N]|$ 」と
「足場 $N-2$ にたどり着くまでの最小コスト $+|h[N-2]-h[N]|$ 」の小さい方になるのだ！
ということは
$dp[i]=($ 足場 $i$ にたどり着くまでの最小コスト $)$
がわかってれば良さそうなのだ！

rep(i,2,N+1){
	if(i-2>=1)dp[i]=min(dp[i-1]+abs(h[i-1]-h[i]),dp[i-2]+abs(h[i-2]-h[i]));
	else dp[i]=dp[i-1]+abs(h[i-1]-h[i]);//i-2<1のときi-2の足場はないのだ！
}
ans=dp[N];

$N$ 回ループだから計算量 $O(N)$ なのだ。

B問題 Frog 2

$1$ ～ $N$ の番号がついた足場がある。
足場 $i$ からは足場 $i+1,i+2,\ldots,i+K$ のいずれかに移動でき、足場 $i$ から足場 $j$ に移動するコストは $|h[i]-h[j]|$ である。
足場 $1$ から足場 $N$ に移動するまでの最小コストを求めよ。
制約： $N\leq 10^5$ 、 $K\leq 10^2$

解説

rep(i,2,N+1){
	dp[i]=dp[i-1]+abs(h[i-1]-h[i]);
	rep(j,2,K+1)if(i-j>=1)dp[i]=min(dp[i],dp[i-j]+abs(h[i-j]-h[i]));
}
ans=dp[N];

外側のループが $N$ 回、内側のループが $K$ 回だから計算量は $O(NK)$ なのだ。

C問題 Vacation

$N$ 日間のそれぞれの日について $A,B,C$ の3つの行動のうち1つを選んで行う。
$i$ 日目に $A$ をすると幸福度 $a[i]$ 得る。同様に $B,C$ をすると $b[i],c[i]$ を得る。
同じ行動を2日以上連続して選ぶことが出来ないとき、幸福度の和の最大値を求めよ。
制約： $N\leq 10^5$

解説

さっきまでの問題と同じように
$dp[i]=(i$ 日目までに得られる幸福度の和の最大値 $)$
としたいけど、それじゃダメなのだ。例えば $a[N]=1,b[N]=1,c[N]=1000$ だったときには、最終日には $C$ を選んだ方が良さそうだけど、前の日に $C$ を選んでたら困るのだ！
「2日連続で選べない」という条件は、前の日に何をしたかわかってればどうにかできるから
$dp[i][j]=(i$ 日目に行動 $j$ をして、 $i$ 日目までに得られる幸福度の和の最大値 $)$
を考えれば良さそうなのだ！
$i$ 日目に行動 $A$ をするには、前日の行動は $B$ か $C$ じゃないとダメだから
$dp[i][A]=\max(dp[i-1][B]+a[i],dp[i-1][C]+a[i])$
になるのだ！ $dp[i][B]$ 、 $dp[i][C]$ も同様なのだ。
最終的な答えは、最終日の行動がどれでもいいから
$\max(dp[N][A],dp[N][B],dp[N][C])$
なのだ！
実際には文字を添え字に持つのは大変だから、A→0、B→1、C→2としてるのだ。

rep(i,1,N+1){
	dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][2]+a[i]);
	dp[i][1]=max(dp[i-1][0]+b[i],dp[i-1][2]+b[i]);
	dp[i][2]=max(dp[i-1][0]+c[i],dp[i-1][1]+c[i]);
}
ans=max(dp[N][0],max(dp[N][1],dp[N][2]));

$A[i][0]=a[i],\ A[i][1]=b[i],\ A[i][2]=c[i]$ として $a[i],b[i],c[i]$ を1つの2次元配列にまとめて持つとループで書けて簡単なのだ！

rep(i,1,N+1)rep(j,0,3){
	rep(k,0,3)if(j!=k)dp[i][j]=max(dp[i][j],dp[i-1][k]+A[i][j]);
}
ans=max(dp[N][0],max(dp[N][1],dp[N][2]));

$N$ 回ループだから計算量 $O(N)$ なのだ。

D問題 Knapsack 1

$N$ 個の品物があり、品物 $i$ は重さ $w[i]$ 、価値 $v[i]$ である。
重さの総和が $W$ 以下になるように品物を選ぶとき、選んだ品物の価値の総和の最大値を求めよ。
制約： $N\leq10^2$ 、 $W\leq10^5$ 、 $v[i]\leq 10^9$

解説

ナップサックDPなのだ！
$dp[i]=(i$ 番目までの品物を、重さが $W$ 以下になるように選んだときの価値の最大値 $)$
じゃやっぱりダメで、次の品物を使っていいかどうかがわからないのだ。
次の品物を使っていいかどうかは、前までの重さがわかってればわかりそうな気がするから
$dp[i][j]=(i$ 番目までの品物を、重さが $j$ 以下になるように選んだときの価値の最大値 $)$
を考えるのだ。すると $dp[i][j]$ は、
$i$ 番目の品物を使うとき「 $i-1$ 番目までで重さが $j-w[i]$ 以下の価値の最大値 $+v[i]$ 」
使わないとき「 $i-1$ 番目までの重さが $j$ 以下の価値の最大値」
という2つの場合の大きい方になるのだ

rep(i,1,N+1)rep(j,0,W+1){
	if(j-w[i]>=0)dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
	else dp[i][j]=dp[i-1][j];//j-w[i]<0のときはi番目の品物は使えないのだ！
}
ans=dp[N][W];

外側のループが $N$ 回、内側のループが $W$ 回だから計算量は $O(NW)$ なのだ。

E問題 Knapsack 2

$N$ 個の品物があり、品物 $i$ は重さ $w[i]$ 、価値 $v[i]$ である。
重さの総和が $W$ 以下になるように品物を選ぶとき、選んだ品物の価値の総和の最大値を求めよ。
制約： $N\leq10^2$ 、 $W\leq10^9$ 、 $v[i]\leq 10^3$

解説

D問題と全く同じなのだ。…………なのだ？
$W\leq10^9$ になってるから、全く同じじゃダメなのだ。
D問題とは添字と値を逆にして
$dp[i][j]=(i$ 番目までの品物を、価値が $j$ になるように選んだときの最小重さ $)$
とすると解けるのだ。
最後に $dp[N][j]$ を $j$ が大きいところから見ていって、初めて $W$ 以下になったときの $j$ が答えなのだ！

rep(i,0,N+1)rep(j,0,100001)dp[i][j]=INF;
dp[0][0]=0;
rep(i,1,N+1)rep(j,0,100001){
	if(j-v[i]>=0)dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
	else dp[i][j]=dp[i-1][j];//j-v[i]<0のときはi番目の品物は使えないのだ！
}
ans=100000;
while(dp[N][ans]>W)ans--;

$j$ のループをどこまでする必要があるかといえば、全部の品物を選んだときの $\sum v[i]\leq 10^5$ なのだ。だから計算量は $O(N\sum v[i])$ なのだ。

……「これを思いつくのは無理」？　確かに難しいけど、次のどれかの発想を使って思いつくのだ！
・発想１：制約を見る
この問題で考えるべきものは「何番目の品物まで使ったか」「価値はいくらか」「重さはいくらか」の3つなのだ。制約を考えると、状態として持てるのは多くても前の2つだけなのだ。だから
$dp[$ 何番目 $][$ 価値 $]=(i$ 番目までの品物を、価値に関するなんらかの条件を満たすように選んだときの重さに関するなにか $)$
という形にするしかないのだ。あとは頑張って考えるのだ！
・発想２：boolのDP
まずはさっき言った「考えるべきもの3つ」を全部状態に持つDPを考えてみるのだ。
$dp[i][j][k]=(i$ 番目までの品物を、価値が $j$ 、重さが $k$ となるように選べるか？)
ここで「『はい』か『いいえ』を値に持つようなDPは、添字を1つ選んで「～が『はい』になる〇〇の最小値(最大値)」という形に書き直せることが多い」というテクニックを使うと、思いつけるのだ！
・発想３：添字の入れ替え
「～となる〇〇の最大値」を値に持つDPは、適当な添字と入れ替えて「～となる××の最小値」というDPにできることが多いのだ！
D問題の解法にこれを使えば思いつけるのだ！
これは発想２の考え方「～となる○○の最大値」→「～とできるか？」→「～となる××の最小値」の間を飛ばしたものとも言えるのだ。

これでアライさんの解説はおしまいなのだ。
アライさんにかかればこんなの朝飯前なのだ！
次のF問題からはサーバルが解説してくれるのだ。

EDPC解説目次へ戻る

2019-01-12

DPまとめコンテスト（EDPC）解説目次

みなさん、こんにちは。パークガイドのミライです。
先日行われた『DPまとめコンテスト/Educational DP Contest』、通称EDPCの解説を競プロフレンズのみなさんに書いていただきました。
個別の解説に入るまえに、解説の中で登場するコードについて注意をいくつかしておきます。
・解説で使われるコードはC言語で書かれたものです。
・入出力は省略しています。入力で与えられる配列は入力例にならい1-indexedです。
・DP配列は0で初期化されています。
・次の5つのマクロが定義されています。

#define rep(i,l,r)for(int i=(l);i<(r);i++)
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define INF ((1LL<<62)-(1LL<<31)) /*オーバーフローしない程度に大きい数*/
#define MOD 1000000007

repが半開区間になっていること以外は自然なものだと思いますので、混乱はないと思いますが注意してください。

それでは解説をどうぞ。
EDPC解説 A～E (入門編)　アライグマさん
EDPC解説 F～L (基本編)　サーバルさん
EDPC解説 M～T (応用編)　カラカルさん
EDPC解説 U～Z (発展編)　フェネックさん

さて、せっかくなので私も「DPとはなにか」について話してみましょうか。
これにはさまざまな宗派がありますが、私は「ある問題を部分問題に分解し、それらの解を用いて元の問題に答える手法」だと考えています。
簡単にいうと「困難は分割せよ」ですね。この考え方は実装するうえではもらうDPやメモ化再帰との相性がよいです。
「何を状態として持つか」が「どのような部分問題に分解するか」と対応し、「状態遷移がどのようになっているか」が「部分問題の解から元の問題の解をどうやって得るか」に対応しています。
この考え方だけで基本的なDPの問題は多くが解けるようになるので是非覚えてくださいね。