EDPC解説 F～L - kyopro_friends’ diary

はいはーい、サーバルだよ！
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解説目次へ戻る