アライさんなのだ!
EDPCのA問題~E問題を解説するのだ!
A問題 Frog 1
~の番号がついた足場がある。
足場からは足場かに移動でき、足場から足場に移動するコストはである。
足場から足場に移動するまでの最小コストを求めよ。
制約:
解説
足場にたどり着くには足場から来るか足場から来るしかないのだ!
だから答えは
「足場にたどり着くまでの最小コスト」と
「足場にたどり着くまでの最小コスト」の小さい方になるのだ!
ということは
足場にたどり着くまでの最小コスト
がわかってれば良さそうなのだ!
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];
回ループだから計算量なのだ。
B問題 Frog 2
~の番号がついた足場がある。
足場からは足場のいずれかに移動でき、足場から足場に移動するコストはである。
足場から足場に移動するまでの最小コストを求めよ。
制約:、
解説
A問題と全く同じで答えは
「足場にたどり着くまでの最小コスト」
「足場にたどり着くまでの最小コスト」
……
「足場にたどり着くまでの最小コスト」の最小のものなのだ!
だからやっぱり
足場にたどり着くまでの最小コスト
がわかれば良さそうなのだ!
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];
外側のループが回、内側のループが回だから計算量はなのだ。
C問題 Vacation
日間のそれぞれの日についての3つの行動のうち1つを選んで行う。
日目にをすると幸福度得る。同様にをするとを得る。
同じ行動を2日以上連続して選ぶことが出来ないとき、幸福度の和の最大値を求めよ。
制約:
解説
さっきまでの問題と同じように
日目までに得られる幸福度の和の最大値
としたいけど、それじゃダメなのだ。例えばだったときには、最終日にはを選んだ方が良さそうだけど、前の日にを選んでたら困るのだ!
「2日連続で選べない」という条件は、前の日に何をしたかわかってればどうにかできるから
日目に行動をして、日目までに得られる幸福度の和の最大値
を考えれば良さそうなのだ!
日目に行動をするには、前日の行動はかじゃないとダメだから
になるのだ!、も同様なのだ。
最終的な答えは、最終日の行動がどれでもいいから
なのだ!
実際には文字を添え字に持つのは大変だから、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]));
としてを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]));
回ループだから計算量なのだ。
D問題 Knapsack 1
個の品物があり、品物は重さ、価値である。
重さの総和が以下になるように品物を選ぶとき、選んだ品物の価値の総和の最大値を求めよ。
制約:、、
解説
ナップサックDPなのだ!
番目までの品物を、重さが以下になるように選んだときの価値の最大値
じゃやっぱりダメで、次の品物を使っていいかどうかがわからないのだ。
次の品物を使っていいかどうかは、前までの重さがわかってればわかりそうな気がするから
番目までの品物を、重さが以下になるように選んだときの価値の最大値
を考えるのだ。するとは、
番目の品物を使うとき「番目までで重さが以下の価値の最大値」
使わないとき「番目までの重さが以下の価値の最大値」
という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];
外側のループが回、内側のループが回だから計算量はなのだ。
E問題 Knapsack 2
個の品物があり、品物は重さ、価値である。
重さの総和が以下になるように品物を選ぶとき、選んだ品物の価値の総和の最大値を求めよ。
制約:、、
解説
D問題と全く同じなのだ。…………なのだ?
になってるから、全く同じじゃダメなのだ。
D問題とは添字と値を逆にして
番目までの品物を、価値がになるように選んだときの最小重さ
とすると解けるのだ。
最後にをが大きいところから見ていって、初めて以下になったときのが答えなのだ!
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--;
のループをどこまでする必要があるかといえば、全部の品物を選んだときのなのだ。だから計算量はなのだ。
……「これを思いつくのは無理」? 確かに難しいけど、次のどれかの発想を使って思いつくのだ!
・発想1:制約を見る
この問題で考えるべきものは「何番目の品物まで使ったか」「価値はいくらか」「重さはいくらか」の3つなのだ。制約を考えると、状態として持てるのは多くても前の2つだけなのだ。だから
何番目価値番目までの品物を、価値に関するなんらかの条件を満たすように選んだときの重さに関するなにか
という形にするしかないのだ。あとは頑張って考えるのだ!
・発想2:boolのDP
まずはさっき言った「考えるべきもの3つ」を全部状態に持つDPを考えてみるのだ。
番目までの品物を、価値が、重さがとなるように選べるか?)
ここで「『はい』か『いいえ』を値に持つようなDPは、添字を1つ選んで「~が『はい』になる〇〇の最小値(最大値)」という形に書き直せることが多い」というテクニックを使うと、思いつけるのだ!
・発想3:添字の入れ替え
「~となる〇〇の最大値」を値に持つDPは、適当な添字と入れ替えて「~となる××の最小値」というDPにできることが多いのだ!
D問題の解法にこれを使えば思いつけるのだ!
これは発想2の考え方「~となる○○の最大値」→「~とできるか?」→「~となる××の最小値」の間を飛ばしたものとも言えるのだ。
これでアライさんの解説はおしまいなのだ。
アライさんにかかればこんなの朝飯前なのだ!
次のF問題からはサーバルが解説してくれるのだ。