EDPC解説 F~L

EDPC解説目次へ戻る

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

F問題 LCS

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

解説

いきなり難しい問題だね……。
「求める文字列の長さ」だけを先に求めておいて、実際の文字列はそれを手がかりに構成していくよ。
dp[i][j]=(si文字目、tj文字目までみた時の最長共通部分列の長さ)
とすると、
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|)だよ。
イメージとしてはこんな感じ!
f:id:kyopro_friends:20190111033239p:plain

G問題 Longest Path

有向閉路を持たないN頂点M辺の有向グラフGが与えられる。
Gの有向パスの最長経路を求めよ。
制約:N\leq 10^5M\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 2999Nは奇数

解説

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 3001\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(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^5N\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解説目次へ戻る