EDPC解説 M~T

EDPC解説目次へ戻る

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

M問題 Candies

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

解説

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)で求められるわね。

「行列の積と同じ式になってると気づくのは無理じゃない?」
そうね、こればっかりは知ってるかどうかになりそうね。
行列累乗で解く問題は、次の2つのポイントを抑えておくといいわ。どっちも決め手になるほどじゃないけど……
・ポイント1:制約をみる
N\leq 50くらい、K10^9とか10^{18}とかの大きな値、みたいな制約の問題は、サイズN\times Nの行列をK乗するかも。
・ポイント2:繰り返し
今回の状態遷移の式を見ると、回数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が与えられる。
1Nの並び替え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解説目次へ戻る