EDPC解説 A～E - kyopro_friends’ diary

アライさんなのだ！
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問題の解法にこれを使えば思いつけるのだ！
これは発想２の考え方「～となる○○の最大値」→「～とできるか？」→「～となる××の最小値」の間を飛ばしたものとも言えるのだ。