DPまとめコンテスト/A - Frog 1 - 競技プログラミング用 知識集積所【7/9更新】

---

問題

DP-A

必要知識

ABCのB以下レベルの内容は省略

• 動的計画法

考え方

N（最大10万）個の足場で2つの選択肢があるため、愚直に全ルートをやると2^10万通りのルートを扱うことになり、計算に10^30000年くらいかかってしまう。
（実際には飛ばした足場では選択が発生しないので2^69400年≒10^21800年くらいだが、焼け石に水である）

そこで、計算の高速化を行うのだが、まずは愚直解を十分書き出せる例で様子を見て、計算を省けそうなところを探さなければならない。
ということで、入力例1で、全足場への最小コストを愚直解で求めてみる。

足場1へ行く場合。
スタート地点がそのままゴールなので、明らかに最小コストは0。

足場2へ行く場合。
1から直接2へ行くルートしかなく、明らかに最小コストは20。

足場3へ行く場合。
1から2を経由して3へ行くルートと、直接3へ行くルートがある。
前者のコストは20+10=30で、後者のコストは30。
よって最小値は30。

足場4へ行く場合。
1から2と3を経由して4へ行くルート、1から2だけ経由するルート、3だけ経由するルートがある。
それぞれのコストは順に、20+10+20=50、20+10=30、30+20=50、である。
よって、最小値は30。

そうして各足場への最小コストが全て求まる。

足場	1	2	3	4
足場の高さ	10	30	40	20
最小コスト	0	20	30	30

さて、足場4の計算方法を見直してみよう。
1から2と3を経由して4へ行くルートの20+10+20=50、3だけ経由するルートの30+20=50、この2つは式の一部に見覚えがある。
これらは、足場3へのコストを求めた計算の後ろに+20を書き足しただけである。
そういう目で見てみると、2だけ経由するルートの20+10=30も、足場2へのコストを求める式の後ろに+10をつけただけである。

ということは、実は足場4へのコストの最小値を求めるために全経路を計算する必要は全くなく、

• 足場3への最小コスト+足場3から4への移動コスト
• 足場2への最小コスト+足場2から4への移動コスト

の2つだけ計算して、小さい方を全体の最小値としてしまえばいい。

もちろん、そこに必要な足場3への最小コストは

• 足場2への最小コスト+足場2から3への移動コスト
• 足場1への最小コスト+足場1から3への移動コスト

の2つの小さい方である。

つまり、この問題は動的計画法を用いて、各足場への最小コストを前から順に求めて、そのデータを継承していけばいい。
入力例1なら、

• 足場1は、そもそもコスト0（特殊処理）
• 足場2は、ルートが1つしかないのでコスト20（特殊処理）
• 足場3は、上記の方法で0+30と10+20の小さい方で30
• 足場4は、上記の方法で20+10と30+20の小さい方で30

とすればいい。
これなら各足場への最小コストを計算2回+比較1回で済ませられるので、N=100000であっても余裕で間に合う。

動的計画法には「もらう」「配る」の2つの書き方があるが、この問題ではどちらでも書ける。
初期化の方法に気を配らなくていい分、もらう方が若干書きやすいか？

解答例

解答例（もらうDP）
解答例（配るDP）

注意点

範囲のはみだしに注意（もらうDPの場合）

足場1だけでなく、足場2も特別扱いしないといけない。
そうでないと、うっかり足場0のコストを見ようとして範囲外アクセスで落ちる。
ループを始める前に最初の2つを個別で埋めて、3番目の足場からループを開始するとよい。

範囲のはみだしに注意（配るDPの場合）

足場N-1を特別扱いしないといけない。
そうでないと、うっかり足場N+1に配ろうして範囲外アクセスで落ちる。
架空のN+1番目の足場をバグ防止のためだけに用意しておくと楽。

別解

vector（未作成）を使わずにメモリを節約する解法

直前2つだけ継承すればいいので、実はvector（未作成）を使わずに実装する方法がある。
ややこしさとバグりやすさ大幅アップだが、実はメモリ節約はほぼメリットにならない。
メモリ不足が心配になるような解法では、メモリが足りなくなる前にまず時間が足りなくなるのが現実である。
メリットは「なんかテクいことしててカッコイイ」くらいか。
解答例