はじめに
本日Atcoder#331のコンテストに参加しまして、無事灰色を維持しました。F★CK
今回のB問題は全探索とは別に動的計画法を使用してACできるらしくて、
結論から言えばどっちのやり方も知らねえよって感じでB問題落としたんだけど、ちょっとわからなかったのが悔しすぎて寝れなかったので普段修業しないフリーザが久々に本気出して修行しました的な方法で自分も本気を出して調べてみた。
。。。ただ調べたんだけどどの記事もハイレベルすぎて理解できなかったし、
赤ちゃんコーダーの自分にもわかるように説明してくれてる記事は見当たらなかった。
3時間ぐらい調べてやっと理解できるレベルに腑に落ちたので記事として共有してみる。
同じ赤ちゃんコーダーの救いに少しでもなればよいと思う。
※本記事のプログラムはすべてPythonで記載しておりますのでご了承ください。
そもそも動的計画法ってなんやねん
まず動的計画法が何かっていう話なんだけどここら辺についてはよくわかっていない。
いきなりごめん。
複雑な問題でも少しずつ分解して簡単にしていけばいいよね。みたいな意気込みのアルゴリズムだと思ってくれればいい。
ちなみに今調べた限り動的計画法っていってもいろいろあって
その中にナップサック問題とかスケジューリング問題とか含まれてるらしいんだけど
今回のB問題はナップサック問題に該当しそうなのでこれに対して説明する予定です。
まぁこんな座学は成人コーダーになってから少しずつ学んでいけばいいと思う。
とにかくなんかいい感じの処理なんでしょ。
基本
動的計画法の基本としてメモ化というのがある。
計算した記録を一時保持しておくことで別処理を行う際にはその回答を用いて次の処理を行う。
日常的に言えば、345×24は何って聞かれたら、筆算もしくはスマホの電卓で計算して8280と回答することができる。
次に345×24＋10は何？って聞かれたら記憶力が3秒しかない人以外は先ほどの答えに10を追加すればいいとわかるから簡単に8290と回答することができる。
これがメモ化と言っているんだと思う。知らんけど。
つまりプログラム内で処理される一時的な値を保持しておいて別の計算で使用できれば良いよね。ってこと。
今は覚えなくてもいい。
ABC＃331について
今回自分が落とした問題内容はここに記載してある。
冒頭でも話したようにこの問題への回答は全探索と、動的計画法があって、灰色コーダーの人は基本的に脳死ぶん回しForループを使用するんじゃないかと思っている。僕はそこに気づけなくてできなかった。
ちなみに全探索の解法は以下になる。
n,s,m,l = map(int,input().split())
ans = float("inf")
for i in range(n + 1):
for j in range(n + 1):
for k in range(n + 1):
if 6*i + 8*j + 12*k >= n:
ans = min(ans,i*s+j*m+k*l)
print(ans)
で、今回の記事のネタになっている動的計画法で書くとどうなるかっていうと
N, S, M, L = map(int,input().split())
dp = [0] + [float('inf')] * (N + 12)
for i in range(N + 12):
if i >= 6:
dp[i] = min(dp[i], dp[i - 6] + S)
if i >= 8:
dp[i] = min(dp[i], dp[i - 8] + M)
if i >= 12:
dp[i] = min(dp[i], dp[i - 12] + L)
print(min(dp[N:]))
見てわかる通り、N ＋ 12でループをしてなんやかんやしている。
うん、本当は見てもわからない。
これ何してんの？なんでリストの参照値マイナスしてんの？そしてなんで足してんの？
みたいな初めて見たときは全然理解できなかった。
今回の目標は上記のコードの理解と自信でソースコードを入力できるようになること
問題
動的計画法について説明する上で以下の問題を作成した。
実際に問題を解いていきながら説明しようと思う。
問題の整理
まず最初に言っておきたいのがアルゴリズムベイビーは現実には存在しないということだ。
こいつは自分が風呂に入りながらスマホで動的計画法について調べ頭を悩ませているとき
突如舞い降りた架空のキャラクターだ。
こいつがこれからアルゴリズムを視覚的に実践することでみんなの理解の助けになることを願っている。
問題を整理しよう
・アルゴリズムベイビーは最低でも24ｋｍ以上離れた旅行に出たい
・使える交通手段は3つで車、飛行機、船のいずれか
・各交通手段の利用には交通費がかかり、また交通手段によって移動できる距離が異なる
・各交通手段は何度でも使える
・24ｋｍ以上進んだ地点での交通費の最小金額はいくらか
もっと簡単に言うとこうだ。
君が社会人であるとして会社に行くまでの交通手段を考える
自宅から最寄り駅までバスや自転車をつかったり、最寄駅からは電車に乗っていったりいろいろな交通手段を選択することができる。
その中で一番交通費が安く済む方法は何か？という問題だ。
当然答えは交通費のかからない徒歩か自転車であるが、この問題に徒歩も自転車もないのでそれ以外の方法で最安値を答える必要がある。
STEP1:全探索の理解
以下の画像で少しずつ問題を解いてゆこう。
動的計画法の説明をしているほとんどの記事がループ処理の中を「以降を繰り返す」などと省略しているが灰色コーダーの人たちにとってはこれは死活問題だ。
「ちゃんと最後まで教えろ。」「全部書け」と彼らに言いたい。
この記事を最後まで読めれば動的計画法の基本的なことについては理解できるはずだ。
STEP1では全探索の理解をしてみる。まず以下の画像を見てほしい。
これは先ほどアルゴリズムベイビーと一緒に動的計画法を学んでいた時の図だ。
全探索というものがどういうものかを考えるには真ん中の表を見てみよう。
車での交通から始まり各交通手段の組み合わせのすべてだ。
水色が車、黄色が飛行機、茶色が船だとすると、一番の赤★、緑★、桃★を経由する方法は車のみ交通手段を使用して24ｋｍの移動を行っている。
この時、車は一度で6ｋｍ移動するため、必要な車の使用回数は24÷6の4回だ。
車の交通費を1回あたり4円と考えると合計16円の交通費がかかることがわかる。
全探索とはこのようにすべての組み合わせの合計値を算出して、最小値を求める方法だ。
すべての組み合わせというのは車が0回からn+1回、飛行機が0回からn+1回、船が0回からn+1回使用した時の組み合わせなのですべてをForループで処理すればよい。
(n + 1とはどの交通手段でも最低でも1ｋｍ進む場合、n回数分のループを行えば確実に到達できることを意味している)
trip = 24
car_cost = 4
flight_cost = 5
ship_cost = 7
ans = float("inf")
for i in range(trip + 1):
for j in range(trip + 1):
for k in range(trip + 1):
if 6*i + 8*j + 12*k >= trip:
ans = min(ans,i*car_cost+j*flight_cost+k*ship_cost)
print(ans)
再起するが上記のようにFor分を入れ子にしてループ処理を行い、
移動距離(trip)+1個**3乗の組み合わせのなかで最小交通費金額を比較している。
ちなみにこの中のif文について説明すると、i,j,jともに0の時回答は0になるが、
このままでは0が最小金額になるので全探索の中でも目的地（24ｋｍ）以上になっているものを条件にしている。
詳細については動的計画法を解くとともに理解していけばよい。
STEP2:変数とリストの作成
では動的計画法の説明に入ろう。
動的計画法では現在のいる位置情報とその時の金額の最安値を保持しておく。
具体的になぜそんなことをするのかを説明していく。
まず初めに変数を設定しておこう。
問題文から目的の距離と、各交通手段の交通費を保持しておく。
trip = 24
car_cost = 4
flight_cost = 5
ship_cost = 7
いくら灰色コーダーといえど変数の代入については理解している思っている。
では次によくわからないリストの作成だ。
trip = 24
car_cost = 4
flight_cost = 5
ship_cost = 7
dp = [0] + [float('inf')] * (trip + 12)
ここで疑問点がいくつが出てくるはずなので一つ一つ答えていく。
Q1: なにしてんのこれ
ここではある位置においての交通費を記録するリストを作成している。
例えば車を使用して6ｋｍ進んだとき、dp[6]の位置には交通費の4が入るようにするためリストを作成する。
これを作成すれば6ｋｍ行く時って交通費いくらだっけ？という質問もdp[6]の値を見ればすぐにわかるだろう。
途中説明したようにこれが動的計画法におけるメモ化だと自分は認識している。
Q2: [0]ってなに
リストの説明の通りある位置に置いての交通費を記録しているの、位置が０であるとき、つまり出発するまえは交通費がかかっていないので最初から交通費0を入力している。
アルゴリズムベイビーだって家から出ていないのに交通費を請求されたくはないからね。
Q3:[float('inf')]ってなに
[float('inf')]は無限大とでも覚えておけばよい。よくわからんがとりあえず大きい数字だ。
これは後々使用したときにわかるが、今回はある地点への到達方法が複数ある場合その中の最安値（最小値）を求める必要があるので、min関数を使用する。
その際にリストの中の初期値として[float('inf')]を使用することで初回の比較時には必ず[float('inf')]ではないほうが選択されるようにしている。
例でいえば初期値を０としてしまうと、どの交通費と比較しても０が最安値になってしまうからなるべくかぶらないであろう最高値をあらかじめ入力しておく必要がある。
0といえば交通費のかからない徒歩と、自転車が常に選択されたら問題にならないからね。
前述した表の中には実際には初期値として[float('inf')]が入っているのだけれども見づらいので今回は空白にしている。
極端な話でいえば、初回実行時の比較に使うだけなので、誤って選択されないようなとても大きい数字だったらなんでもでもいいんじゃないかな。10**9とかね。
Q4:* (trip + 12)ってなに
3で初期値に無限大を設定すると伝えたように、まずは可能性としてあり得る位置の数だけリストを作る必要があるのでこの無限大初期値を複製してリストを作っている状態なんだ。
Q5:trip + 12ってなに
この後のループ処理にも使うけどtrip + 12っていうのは到達する位置の可能性としてありえる最大だね。
どうして+12かっていうのは3つの交通手段を一度使っていける最大距離が船を利用した12ｋｍだからね。
全探索もそうだけ一生ループして最小値を求めていたら処理は終わらない。ある程度の区切りをつけなくちゃいけないはずだ。
その中で目的の位置＋一度の交通手段で行ける最大距離ぐらいまでの処理を見ておけばすべての可能性を確認できるということだ。
言葉での説明が多くなってきたから改めて以下の画像を見てみよう。
目的地の24という縦軸を見てほしい。
この24の位置に存在する組わせの中で交通費が最安値であるのが今回求める回答になるのだが、
もし仮に前の位置が23の時この後車を利用して6進んだ29か、飛行機を利用して8進んだ31か、船を利用して12進んだ35が最終位置になる可能性がある。しかし36以上の移動は不要と考える。
可能性でいえば船での移動を3回繰り返したとき（画像では2回目の段階で24になっているがここが23だと考えよう）
もしかしたら船での移動3回の35に到着する方法が最安値になる可能性はあるが36以上は考慮する必要はない。
36以上を考慮するということは目的値についているのに交通費を払って進み続けているということだ。
それが最安値なわけはない。
やり方としては最終地点から最高移動距離1回分ぐらいまでの処理を見ておけば後の答えは変わらないはずだ。
それ以上先を見ても最小値は変わらない。と伝えれば理解できるだろうか。
STEP3:０から初回位置(i = 6)登録までのループ
本格的に動的計画法のループ処理についてみていこう。
これまでに学んだ通り目的位置＋一度の最大移動距離分のループをしてその地点での交通費を見てみよう。
for i in range(trip + 12):
まずi = 1の地点にいる場合を考えてみよう。
おっと、どうやら徒歩と、自転車を禁止されているアルゴリズムベイビーは1へ到達する手段を持ち合わせていないようだ。1に行く手段はないので交通費も支払う必要はないね。
これと同じよう2から5についても到着するすべを持っていないことはわかるよね。
...車で移動する際は高速道路に乗っているのかな。
続いて以下の画像を見てほしい。
どうやら最初に車を選択したアルゴリズムベイビーが6の位置まで来たようだ。
問題文にも記載しているが一度の車で移動できる距離は6ｋｍなので、
アルゴリズムベイビーは6ｋｍの移動で交通費が4円かかっているわけだから現時点での交通費をリストに追加しよう。
ちなみに空白には初期値の[float('inf')]が入っていると説明したが、4円と無限大円だったらどっちが安いかは明白だ。
ソースコードとしてはこんな感じになる。
for i in range(trip + 12):
if i >= 6:
dp[i] = min(dp[i], dp[i - 6] + car_cost)
リストに追加するだけって言ったのに難しいじゃないか。
いったい何をしているんだっていう人もいるだろうからゆっくり説明していく。
まずdp[i] = min(dp[i], dp[i - 6] + car_cost)のdp[i]から見ていこう。
初めて移動したときのdp[6]（位置6）については[float('inf')]（無限大）が格納されている。
次に車を利用してdp[6]の位置へ移動するときの前にいた位置の交通費を確認する。
つまり今回の移動に必要だった交通費とは別にこれまでの移動にかかった交通費を確認するということだ。
dp[i - 6]というのは車で移動する前の位置だね。i が 6 の時はdp[0]だから出発地点の交通費の話をしているよ。
出発地点の交通費は0円だからそれに今dp[6]まで車を利用した際の交通費(car_cost)を追加すればこれまでの交通費を確認できるね。
結果としてまだ車での移動を一度しかしていないから交通費は4円しかかかっていないので
[float('inf')]と4円をmin関数を使用して安い金額が選択されるけど[float('inf')]は無限大だからもちろん4円の費用が選択される。
ここでメモ化しておくことで、今後アルゴリズムベイビーが出発地点から6ｋｍの距離に出かけるときは最小金額4円の車を利用することになるよ。もう迷わなくて済むね。
STEP4:i = 7 から11まで
位置が6ｋｍの時の一番安い交通費に関してはばっちりだ。
交通手段は車しかないので交通費も4円で確定となる。
次にdp[7]からdp[11]までの状態を確認しておこう。
位置7と11の間でアルゴリズムベイビーが到達できる可能性があるは位置8のみだ。
それ以外はどの方法でもアルゴリズムベイビーが到達できる方法は基本的には存在しないはずなので一度ここまでのソースコードを確認しておこう。
trip = 24
car_cost = 4
flight_cost = 5
ship_cost = 7
dp = [0] + [float('inf')] * (trip + 12)
for i in range(trip + 12):
if i >= 6:
dp[i] = min(dp[i], dp[i - 6] + car_cost)
if i >= 8:
dp[i] = min(dp[i], dp[i - 8] + flight_cost)
まず最初に位置6の時点での交通費を入力したのは覚えていると思う。
ソースコードを見るとif i >= 6:になっているので、iが7の時も条件が一致するんじゃないかといえるかもしれないが、
確かにそうだ。
iが7の時の条件を見てみよう。
まずdp[7]はこれまで訪れたことのない位置なので、ここでの交通費は[float('inf')]になっているはずだ。
もし7に到着してしまったらアルゴリズムベイビーの破産が確定する。
でもちょっと待ってほしい。
ここでmin関数を使用しているのでdp[7 - 6] + car_costがdp[7]より小さければいいんじゃないの？と思うかもしれないが、残念ながらdp[1]も[float('inf')]なので無限大と無限大＋4円を比較しているようなものだ。
確実に最小値ではないことは分かっているので無視してかまわない。
続いてiが8の場合はどうだろうか。
if i >= 6:
dp[i] = min(dp[i], dp[i - 6] + car_cost)
車での移動についてはiが7の時と同様無限大になっているので最小値ではないことは確実だ。
念のため確認してみる。
dp[8] の初期値は無限大
dp[8 - 6] = dp[2]についても過去に到着したことのない位置であるので無限大+4円。
どちらをとっても確実に最小金額になることはないので無視してもよいだろう。
では次の条件はどうなるだろうか。
if i >= 8:
dp[i] = min(dp[i], dp[i - 8] + flight_cost)
ここでは飛行機で移動した場合の交通費を記録している。
まずdp[8]はfloat('inf')だが、dp[8 - 8] を計算した dp[0]は出発地なので0である。
そこに今回の移動にかかった交通費5円を追加すると、
min ([float('inf')], 5)となるがこの二つが比較されてdp[8]には5の交通費が格納される。
この時点で距離8の移動の際は飛行機での移動が最小金額ということだ。
そのほかに車や船を利用して位置8ｋｍに到達できる移動手段はないので8にたどり着く最小値は5で確定することがわかるので交通費リストに追記する。
i=9,10,11も7同様に元の位置への到達方法が[float('inf')]なのでこれらが最小値となることはない。
STEP5:i = 12 の時
ここまで読んだ君たちなら以下の説明ももちろん理解できるはずだ。
i = 12 の時
if i >= 6:
dp[i] = min(dp[i], dp[i - 6] + car_cost)
上記車を利用した場合の条件を計算してみる。
dp[12] = min(dp[12], dp[12 - 6] + car_cost)となり
dp[12]はもちろん初回到着地点なので[float('inf')]だが、dp[12 - 6]はdp[6]の4になる。
そうdp[6]に行く手段は存在していて、それは初回に車で移動した際の位置になる。
その時の交通費4円といま位置6ｋｍから12ｋｍへ移動した際の交通費4円を足すことで
位置12までの交通費は8円かかったことがわかる。
上記画像の通り、一回目に交通費4円を払って位置0→位置6に移動、二回目に交通費4円を払って位置6→12に移動
しかしちょっと待ってほしい。この時点で位置12へ行く方法が車で二回移動する8円が最小値だと決めつけてはいけない。
このまま処理を見ていこう
if i >= 8:
dp[i] = min(dp[i], dp[i - 8] + flight_cost)
飛行機を使用した場合の可能性を計算する。
現在dp[i]→dp[12]の交通費の最小金額は8円である。
dp[i - 8]→dp[12 - 8]→dp[4]の時の金額を調べると、dp[4]にいる場合のみ飛行を利用して12に到達することが可能。しかしdp[4]へ到達するには[float('inf')]の交通費がかかるため、二つを比較した場合の最小値は8円のままになる。
少し参考の画像がわかりづらいが基本的に★マークのついている境界線以外の移動方法には無限大円のお金がかかってしまうことになる。
続いて船を使用する場合を確認してみよう。
if i >= 12:
dp[i] = min(dp[i], dp[i - 12] + ship_cost)
お気づきの方もいるかもしれないが、船を利用しても位置12への到達が可能なのだ。
しかもこの時の交通費は7円なので車を二回利用していくよりも安いことがわかる。
そのため交通費リストとしては位置12に行く場合は船を利用するのがベストな選択となる。
このように交通費をメモ化しておくことで、今後位置12に到着したい場合は船を選択することが確実となる。
今後の計算において車を二回使用したパターンの考慮が不要となるのだ。
STEP6:i = 13 から18まで
同様に位置が18のパターンを見てみよう。
この中でアルゴリズムベイビーが18に到着できる可能性があるのは以下のとおりである。
パターン1
出発地点から車を二回利用し位置12へ移動してから車を利用して6進んで18へ行くパターン
パターン2
出発地点から車を一度利用した位置6から船を利用して12進んで18へ行くパターン
パターン3
出発地点から船を一度利用した位置12から車を利用して6進んで18へ行くパターン
一つ一つのパターンの交通費の最小値を確認しておこう。
まずパターン１については
もとにいた位置が車を2回利用して位置12に移動したパターンなので前回の移動までに8円の交通費がかかっている。
STEP4で実行済みだが、位置12でのいく最安値は船を使った7円の移動となるため、
今回車での二回移動するパターン１の考慮は不要となる。
パターン2については
一度目の車で位置6へ移動した後船を利用して位置6から位置18へ移動している。
交通費としては、
もともといた位置6の交通費 = 4
今回移動した際の船の交通費 = 7
なので合計値が11になる。
パターン3については位置12までは7円を支払い位置12にいた状態から車を利用して、位置18へ移動している。
交通費としては、
もともといた位置12の交通費 = 7
今回移動した際の車の交通費 = 6
なので合計値が11になる。
パターン2,3から見るに位置18へ行く場合の最安値は11となる。
「表を見ると位置14や位置16にも数値が記載してあるけどちゃんと説明してくれよ。」
そんな赤ちゃんコーダーの君たちのために再度説明する。
i = 13と15はこれまで説明してきた「到達不可能」なパターンと同じで無限大円の金額がかかる。
これらが最小値になることはないので表としては空白なままにしてある。
次にi = 14のパターンを見てみよう。
パターン1
パターン2
i = 14へのパターンは二通りあるがどちらも車と飛行機を1回ずつ利用している。
ソースコードで確認してみよう。
if i >= 6:
dp[i] = min(dp[i], dp[i - 6] + car_cost)
i = 14 から上記ソースコードは以下の計算になる。
if i >= 6:
dp[14] = min(dp[14], dp[14 - 6] + 4)
dp[14]に初めて到達した場合dp[14]には無限大の[float('inf')]が格納されている。
dp[14 - 6]はdp[8]のことなので、dp[8]の移動までにかかった交通費を見てみると、飛行機を利用した際の5円の費用を払う必要がある。
改めてソースコードを整理すると以下になる。
if i >= 6:
dp[14] = min(float('inf'), 9) #9=初回飛行機を利用した5円と、今回車で移動した4円の9円
上記を比較するともちろんdp[14]の最安値は9円となる。
次のコードを見てみよう。
if i >= 8:
dp[i] = min(dp[i], dp[i - 8] + flight_cost)
同様に整理するとdp[i - 8]はdp[6]になるので(i=14と計算)dp[6]には車で移動した4円の交通費がすでに交通費として格納されている状態だ。
if i >= 8:
dp[i] = min(dp[14], 9) #9=初回車を利用した4円と、今回飛行機で移動した5円の9円
この時min(dp[14], 9)のdp[14]には何が入るだろうか。
先ほどの流れでいえばdp[14]には無限大のfloat('inf')が入るのではないかと思うかもしれない。
しかし
if i >= 6:
dp[14] = min(float('inf'), 9) #9=初回飛行機を利用した5円と、今回車で移動した4円の9円
ですでにその時点での最安値の9円を格納しているので実際には
if i >= 8:
dp[i] = min(9, 9) #9=初回車を利用した4円と、今回飛行機で移動した5円の9円
となる。
答えはどちらかの9円だと思うがどちらでも一緒だろう。
つまり位置14に移行方法は2パターン存在するということだ。
i = 16の場合はどうだろうか。
i = 16のパターンは飛行機を二回利用することで到達することができる。
前回飛行機到達時のdp[8]にかかった交通費5円と、今回飛行機の移動でかかった交通費5円を足して
dp[16]には交通費10円が最安値となるだろう。
おさらい
ここまで詰め込んで説明してきたのでそろそろ頭の中がパンクするころだろう。
次のiに行く前にもう一度おさらいしておく。
trip = 24 #目的地
car_cost = 4 #車を利用した際の交通費
flight_cost = 5 #飛行機を利用した際の交通費
ship_cost = 7 #船を利用した際の交通費
dp = [0] + [float('inf')] * (trip + 12) #その時点での最安の交通費を格納しておくリスト
for i in range(trip + 12): #目的地以上に到達するまでのループ処理を開始
#前回までにかかった交通費+今回車で移動した際の交通費を計算(dp[i - 6] + car_cost)
#すでに記録してある最安の交通費(dp[i])と比較して少ない交通費で更新する。
if i >= 6:
dp[i] = min(dp[i], dp[i - 6] + car_cost)
#前回までにかかった交通費+今回飛行機で移動した際の交通費を計算(dp[i - 8] + flight_cost)
#すでに記録してある最安の交通費(dp[i])と比較して少ない交通費で更新する。
if i >= 8:
dp[i] = min(dp[i], dp[i - 8] + flight_cost)
#前回までにかかった交通費+今回船で移動した際の交通費を計算(dp[i - 12] + ship_cost)
#すでに記録してある最安の交通費(dp[i])と比較して少ない交通費で更新する。
if i >= 12:
dp[i] = min(dp[i], dp[i - 12] + ship_cost)
ここまで読んでまだ不明点があるならばコメントしていただければ自分のわかる範囲でお答えするつもりだ。
また「何度も同じ説明されるせいで余計わからない」ということであればあなたの理解力は素晴らしいので別の記事を参考にすることをおすすめする。
改めて言うがこれは自分と同じ赤ちゃんコーダーに向けた記事であり、
「何度も同じ説明をされないとわからない」レベルの人間にあてた記事であることを理解していただきたい。
i = 24の時
これまでの説明でi = 20, i = 22のパターンについても自分たちで計算することができるだろう。
大切なのは「前回いた位置までにかかった交通費と、今いる位置に移動するのに必要な交通費を計算した後に、その位置での最安値を更新する」ということだ。
それでは最後に i = 24の説明を見ていこう。
一つの方法として車を四回利用して6→12→18→24と到着した場合の計算ができる。
交通費は全部で16(4円 × 4回)となるはずだが、少し待ってほしい。
本当にこの計算が必要なのだろうか？
というのもこれまでの処理で位置12に行く際は船を利用した方法で行くのが最安値だとわかっている。
これと同様に位置18までに行く際の最安値も決定している。
つまりどういうことかというと、最後にもし車を利用して24へ到着したい場合
前回の出発位置は18になるはず（車の一度の移動距離は6ｋｍ)だ。
そして位置18に行く最安値はすでに確定しているので
わざわざ位置18まで車を3回利用していくという考えを無視してもよいということだ。
実際に全探索では車を4回利用した際の計算が行われるはずだが、
動的計画法ではこういった途中経過を一度記録しておくことで改めて比較する必要はないということだ。
我々はすでに位置18へ交通費11円で行く手段をしっているのだから
車を四回利用することが最安値であるということは最初からあり得ないということがわかっているのだ。
この方法を用いれば、
最後に車を利用して到着した場合と、
最後に飛行機を利用して到着した場合、
最後に船を利用して到着した場合の3パターンを考えてみる。
最後に車を利用したパターンは前述したように位置18まで交通費11円を支払って出発し、最後に4円のコストを支払って24に到達するパターンだ。
この場合の交通費は11円＋4円の15円になるはずだ。
続いて最後に飛行機を利用したパターンは、
飛行機の移動距離8ｋｍと考えると24ｋｍ地点に到着する前の位置はdp[24 - 8] →dp[16]の位置にいることがわかっている。
つまりdp[16]までは最安値10で到達し、最後に飛行機を利用するのでかかる費用は15円となる。
船のパターンも同様だ。
船は一度で12ｋｍ進むことができるので目的地24の前にいる位置12の最安値は7である。
これは最初に船を利用して移動した場合の条件となり二つの交通費を合わせても14円になることから
結果的に位置24ｋｍに行く際の最安値は船を二回利用した際の14円であることがわかる。
復習
このように移動した位置の最安値を更新し続けることで、次の計算に利用することが動的計画法というものらしい。
たとえば位置25の場合の最安値はどうなるの？
といった場合も同様に考えてみよう。
最後に車を利用して位置25到着する場合前の位置は19にいる必要がある。
飛行機の場合は17にいる必要がある。
船の場合は13にいる必要があるが、そのどれもがこれまで経由してくることが出来なかった位置であり、交通費はfloat('inf')かかるはずだ。
これは得策では無い。
25に行くぐらいなら24の地点から再度車を利用して30の位置でも言った方が安上がりだ。
確認になるが問題は目的地以上に行く最安値であるのであって、必ずしも目的地にいる必要は無い。
この場合25以上でいちばん安く行ける箇所を探す必要が出てくる。
25の到達方法がなければ26の場合も見ればよい。
26の到達は車、飛行機、船を利用した16円で到着することができる。
たとえば以下のように目的地を25に設定した状態で全探索のプログラムを実行する。
trip = 25
car_cost = 4
flight_cost = 5
ship_cost = 7
ans = float("inf")
for i in range(car_cost + 12):
for j in range(flight_cost + 12):
for k in range(ship_cost + 12):
if 6*i + 8*j + 12*k >= trip:
ans = min(ans,i*car_cost+j*flight_cost+k*ship_cost)
print(ans)
このプログラムを実行すると正しく「16」という数値が出てくるはずだ。
表で見てみると、
26への到達には以下のパターンが存在する。
1:位置20から車を利用していく場合
2:位置18から飛行機を利用していく場合
3:位置14から船を利用していく場合
各パターンの最小値は前位置の最小値から交通費を計算すればいい。
1:位置20まで行く際の最安値は12円なので＋4円の16円
2:位置18まで行く際の最安値は11円なので＋5円の16円
3:位置14まで行く際の最安値は9円なので＋7円の16円
上記のパターンにおいて16円が最安値となることがわかる。
この時に全探索では車を三回利用して位置18にいる状態で飛行機を利用し26へ到達する方法も計算する必要が出てくるが、動的計画法においてこの計算は不要となる。
なぜなら位置18に行くまでの最安値は11円と決まっているのでそのほかの方法で行く必要がないのだから。
解法とソースコードの考え方
ここまでの説明を踏まえて改めて今回の問題の回答を見てみよう。
回答は以下のとおりである。
trip = 24 #目的地
car_cost = 4 #車を利用した際の交通費
flight_cost = 5 #飛行機を利用した際の交通費
ship_cost = 7 #船を利用した際の交通費
dp = [0] + [float('inf')] * (trip + 12) #その時点での最安の交通費を格納しておくリスト
for i in range(trip + 12): #目的地以上に到達するまでのループ処理を開始
#前回までにかかった交通費+今回車で移動した際の交通費を計算(dp[i - 6] + car_cost)
#すでに記録してある最安の交通費(dp[i])と比較して少ない交通費で更新する。
if i >= 6:
dp[i] = min(dp[i], dp[i - 6] + car_cost)
#前回までにかかった交通費+今回飛行機で移動した際の交通費を計算(dp[i - 8] + flight_cost)
#すでに記録してある最安の交通費(dp[i])と比較して少ない交通費で更新する。
if i >= 8:
dp[i] = min(dp[i], dp[i - 8] + flight_cost)
#前回までにかかった交通費+今回船で移動した際の交通費を計算(dp[i - 12] + ship_cost)
#すでに記録してある最安の交通費(dp[i])と比較して少ない交通費で更新する。
if i >= 12:
dp[i] = min(dp[i], dp[i - 12] + ship_cost)
print(min(dp[trip:]))
まずすでに問題文に与えられている値を変数として定義しておく。
trip = 24 #目的地
car_cost = 4 #車を利用した際の交通費
flight_cost = 5 #飛行機を利用した際の交通費
ship_cost = 7 #船を利用した際の交通費
続いて各位置の交通費を記録するためのリストを作成し、今回は最小値を求めるために
出発地点の0と初期値に[float('inf')]を設定したリストを作成しておく。
dp = [0] + [float('inf')] * (trip + 12) #その時点での最安の交通費を格納しておくリスト
次に各位置の最小値を判断するために到着する可能性のある位置に対してループ処理を行う。
for i in range(trip + 12): #目的地以上に到達するまでのループ処理を開始
この時注意してほしいのはループ回数は目的地だけでなく目的地から一度に進める最大距離分を追加しておく。
今回でいえば船を利用した際に12ｋｍ進むことができるので目的地に12を追加した値（36）がループ回数となる。
Q:どうして目的より先を見る必要があるのか
というと、前述したようにもし目的地が25であった場合、実際の最安値は位置26の地点の値が必要になり、目的位置分のループ処理では算出することができないからである。
今回の問題は24ちょうどの位置で到達するので仮にループ回数が24回（trip + 1）でも回答としては正しい答えが出力されるはずだが、今後別の問題を解くうえでこの考え方は必要となる。
Q:24回なら(trip + 1)ではなくtripではないのか
という質問に対しては出発地0を考慮すると24までの試行回数は25回となることを認識してほしい。
差の求め方:24(到達) - 0（出発） + 1 = 25
各ループ内の処理を記載する。
#前回までにかかった交通費+今回車で移動した際の交通費を計算(dp[i - 6] + car_cost)
#すでに記録してある最安の交通費(dp[i])と比較して少ない交通費で更新する。
if i >= 6:
dp[i] = min(dp[i], dp[i - 6] + car_cost)
#前回までにかかった交通費+今回飛行機で移動した際の交通費を計算(dp[i - 8] + flight_cost)
#すでに記録してある最安の交通費(dp[i])と比較して少ない交通費で更新する。
if i >= 8:
dp[i] = min(dp[i], dp[i - 8] + flight_cost)
#前回までにかかった交通費+今回船で移動した際の交通費を計算(dp[i - 12] + ship_cost)
#すでに記録してある最安の交通費(dp[i])と比較して少ない交通費で更新する。
if i >= 12:
dp[i] = min(dp[i], dp[i - 12] + ship_cost)
今回の条件は車、飛行機、船で行く場合の3パターン用意する必要がある。
各位置に対して、前回いたと思われる位置までのかかった交通費 + 今回の交通費を追加して現在の最安値と比較する
前回いたと思われる位置の求め方は現在の位置 - 交通手段の移動距離を求めればいい。
i → 現在の位置
i - 6 → 車で6ｋｍ移動する前の位置
d[i] → 現在の位置の最安値（初期値：float('inf')）
d[i - 6] → 移動する前にすでにかかっている交通費（前の時点の交通費の最安値）
という理解をすれば自分でソースコードをかけるのではないだろうか。
まずわかるところから埋めていこう。
今回は車を例にしておく。
if i >= 6:
if i >= 6:とは単純な条件分岐である。
なぜこのようにしているのかというと、車を利用した場合は6ｋｍずつ進むため位置１から5までに到達することはない。
よってその時点では計算をする必要がないということだ。
もしこの条件を無視した場合i = 1の位置にいる車の状況を考える必要が出てくるが、
i = 1に車がいるということは車はi = - 5の位置にいなくてはいけない。
出発より過去の状況を見る必要はないし、実際にリストは0からスタートなので正常に動作しなくなってしまう。
そのため車での移動を考慮するのは位置が6以上になってからでよいということでif i >= 6:が必要になってくる。
dp[i]
まずは到達した時点での現在位置の最安値を取得する。
dp[i - 6] + car_cost
続いて前のいた位置の交通費dp[i - 6]と
今回の移動にかかった交通費car_costの合計値を取得する
上記二つの値のうち小さいほうを最安値と定義するためin関数を使用すると以下のような計算式になる。
min(dp[i], dp[i - 6] + car_cost)
そしてこのうちの最安値のほうで現在の位置にかかる交通費を更新しておく
dp[i] = min(dp[i], dp[i - 6] + car_cost)
これで計算式の完成だ。
#前回までにかかった交通費+今回車で移動した際の交通費を計算(dp[i - 6] + car_cost)
#すでに記録してある最安の交通費(dp[i])と比較して少ない交通費で更新する。
if i >= 6:
dp[i] = min(dp[i], dp[i - 6] + car_cost)
上記と同じように、飛行機、船の処理も追加する。
trip = 25 #目的地
car_cost = 4 #車を利用した際の交通費
flight_cost = 5 #飛行機を利用した際の交通費
ship_cost = 7 #船を利用した際の交通費
dp = [0] + [float('inf')] * (trip + 12) #その時点での最安の交通費を格納しておくリスト
for i in range(trip + 12): #目的地以上に到達するまでのループ処理を開始
#前回までにかかった交通費+今回車で移動した際の交通費を計算(dp[i - 6] + car_cost)
#すでに記録してある最安の交通費(dp[i])と比較して少ない交通費で更新する。
if i >= 6:
dp[i] = min(dp[i], dp[i - 6] + car_cost)
#前回までにかかった交通費+今回飛行機で移動した際の交通費を計算(dp[i - 8] + flight_cost)
#すでに記録してある最安の交通費(dp[i])と比較して少ない交通費で更新する。
if i >= 8:
dp[i] = min(dp[i], dp[i - 8] + flight_cost)
#前回までにかかった交通費+今回船で移動した際の交通費を計算(dp[i - 12] + ship_cost)
#すでに記録してある最安の交通費(dp[i])と比較して少ない交通費で更新する。
if i >= 12:
dp[i] = min(dp[i], dp[i - 12] + ship_cost)
これで動的計画法の完成だ。
しかしこの状態では最終的な出力がない状態だが、どのようにして出力結果を求めればよいだろうか。
それは作成した交通費リストに対して目的地以上の位置にある最安値を求めればよい。
目的地以上の地点の交通費の取得はリストのスライス機能を使用する。
dp[trip:]
上記のコードで以下のリストの目的地以上のリストが取得されるはずだ
このスライスを使用しないとリスト全体を見ることになり、
目的地に到着する前の最安値が取得されてしまうので注意が必要だ。
今回はtrip(24)以降のリストを参照するが実際にはループは36回行っているので
リストの位置24から36までの最安値を確認することになる。
画像では25までの位置しか記録していないがここまで読んでくれた方なら理解できるはずだ。
念のため説明しておくがアルゴリズムベイビーの画像でいうと以下の赤枠のリストの中で最安値を求めるということだ。
最安値の求め方は今までと同様にmin関数を使用することで回答することができ、最終的に出力する方法は以下になる。
print(min(dp[trip:]))
以上でソースコードの作成を実行してみよう。
出力欄に「14」と表示されれば完成である。
最後に実際に自分が解けなかったB問題を今回手に入れた動的計画法という武器を手にしてボコボコにしてやろうと思う。
実際に出題された問題
問題はこちらになる。
アルゴリズムベイビーとともに動的計画法を学んできた皆さんも実際に解いてみてほしい。
解法
まず卵6個入りはS円、卵8個入りはM円、卵12個入りはL円となり入力値から情報を得ることになる。
また目的地、今回は目的個数ということだがそれに対してもNという入力を受け取る必要があるのでまずは入力情報を受け取ってみよう。
N, S, M, L = map(int,input().split())
今回map関数を使用してすべての入力をint型に変更しているがAtcoderの標準入力については別の記事を参考にしてもらえるとありがたい。ここでは割愛する。
やっていることは受け取った内容を変数に格納しているだけなのでアルゴリズムベイビーと学んだ以下のコードと同じである。
trip = 25 #目的地
car_cost = 4 #車を利用した際の交通費
flight_cost = 5 #飛行機を利用した際の交通費
ship_cost = 7 #船を利用した際の交通費
これを今回にパターンに置き換えると
N = #目的個数
S = #6個入りの卵の値段
M = #8個入りの卵の値段
L = #12個入りの卵の値段
次に各卵の個数時の最安値を格納するリストを作成する。
N, S, M, L = map(int,input().split())
dp = [0] + [float('inf')] * (N + 12)
ここで(N + 12)部分だが、今回の卵の目的個数Nと最大で12個入りのLパックを追加したときの12を範囲として定める。
逆にこれ以上の計算は不要であると判断する。
実際にループ処理を書いていこう
for i in range(N + 12):
if i >= 6:
dp[i] = min(dp[i], dp[i - 6] + S)
if i >= 8:
dp[i] = min(dp[i], dp[i - 8] + M)
if i >= 12:
dp[i] = min(dp[i], dp[i - 12] + L)
ループ回数はリストの長さと同様に目的個数N＋一度に増える最大個数でいいのだが、
人によってはlen(dp)と先ほど作成したリストの長さを取得してもいいかもしれない。
ループ処理の中についてみてみる。
if i >= 6:
dp[i] = min(dp[i], dp[i - 6] + S)
アルゴリズムベイビーと同じようにまず1から5個の卵を買う方法は存在しないので考慮する必要はなく、
条件分岐はS円パックを買った場合の個数6を起点として考える。
dp[i - 6] + Sで前回までに購入した際の金額と、今回購入したS円の金額の合計値を求めたあと
min関数を使用してリストに登録されてある最安値を比較し少ないほうの値でリストを更新する。
同じようにM円の卵の場合と、L円の卵の場合も記載すると以下のようなソースコードとなるだろう。
N, S, M, L = map(int,input().split())
dp = [0] + [float('inf')] * (N + 12)
for i in range(N + 12):
if i >= 6:
dp[i] = min(dp[i], dp[i - 6] + S)
if i >= 8:
dp[i] = min(dp[i], dp[i - 8] + M)
if i >= 12:
dp[i] = min(dp[i], dp[i - 12] + L)
最終的に最安値が記録されているリストdpの中からN個以上買った場合の卵の最安値を出力する。
print(min(dp[N:]))
上記のソースコードを結合して完成である。
N, S, M, L = map(int,input().split())
dp = [0] + [float('inf')] * (N + 12)
for i in range(N + 12):
if i >= 6:
dp[i] = min(dp[i], dp[i - 6] + S)
if i >= 8:
dp[i] = min(dp[i], dp[i - 8] + M)
if i >= 12:
dp[i] = min(dp[i], dp[i - 12] + L)
print(min(dp[N:]))
提出結果
見事ACである。
参考までに全探索した場合と速度を比較しても一目瞭然である。
[全探索の場合]
[動的計画法の場合]
最後に
これで自分が理解した限りでの動的計画法について共有することはできたと思う。
正直灰色コーダーのような知識レベルで投稿していい記事でもないと思うし、本当に自分の言っていることが正しいのかもわかっていない。
しかし今後学習するにつれて今日このときに記載した内容の正誤が判断できるようなれれば自分も一人前の成人コーダーになれたといえるであろう。
今回自分の人生で初めてのQiita投稿ということもありつたない文章であったが、
ここまで見てくれた皆さんには感謝の言葉を贈るとともに、アルゴリズム理解の第一歩となってくれることを願っている。
以上