競技プログラミング 知識集積所

EDPC A - Frog 1

カエル 1

問題ページ解答例配る方式別解

考え方

ABCでいうと、易しめのD問題級。

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

そこで、計算の高速化を行う。
まずは愚直解を十分書き出せる例で様子を見て、計算を省けそうなところを探さなければならない。
ということで、入力例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$ へのコストの最小値を求めるために全経路を計算する必要は全くない。
以下の $2$ つだけ計算して、小さい方を全体の最小値としてしまえばいい。

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

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

つまり、この問題は動的計画法を用いることで高速化できる。
各足場への最小コストを前から順に求めて、そのデータを継承していけばいい。
後述の、入力例1での動作を参照。

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

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

今回は最小コストだけでよいが、もし実際の経路まで答える問題があったら、バックトレースを用いる。
つまり、以下のように逆再生で辿る。

あるいは、もらうDPで書いている場合、どこから来るルートを採用したかを全ての足場でメモしてもよい。

経路復元コードが正しいか確認したければ、競技プログラミングの鉄則 B17 へ。

入力例1での動作

入力を受け取る。

n: 4
h: {10, 30, 40, 20}

dp[i] を、足場 i までの最小コストとする。
コード上では 0-indexed なので、足場 $1$ が dp[0]、足場 $2$ が dp[1] などと対応する。

まず、dp の初期値を用意する。
スタートの足場までのコストは $0$ なので、dp[0] は $0$ である。
足場 $2$ へは足場 $1$ から来るしかないので、dp[1] は $|30-10|=20$ である。

h : {10, 30, 40, 20}
dp: {0, 20, ?, ?}

足場 $3$ への最小コストを求める。
足場 $2$ から来る場合は、dp[1]+abs(h[1]-h[2]) $= 20+|40-30| = 30$。
足場 $1$ から来る場合は、dp[0]+abs(h[0]-h[2]) $= 0+|40-10| = 30$。
小さい方を採用して、dp[2] は $30$ となる。

h : {10, 30, 40, 20}
dp: {0, 20, 30, ?}

足場 $4$ への最小コストを求める。
足場 $3$ から来る場合は、dp[2]+abs(h[2]-h[3]) $= 30+|20-40| = 50$。
足場 $2$ から来る場合は、dp[1]+abs(h[1]-h[3]) $= 20+|20-30| = 30$。
小さい方を採用して、dp[3] は $30$ となる。

h : {10, 30, 40, 20}
dp: {0, 20, 30, 30}

最後の足場の値、つまり dp の最後尾の値が答え。

注意点

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

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

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

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

別解

vector を使わずにメモリを節約する解法

直前 $2$ つだけ継承すればいいので、実は vector を使わずに実装する方法がある。
ややこしさとバグりやすさ大幅アップだが、実はメモリ節約はほぼメリットにならない。
メモリ不足が心配になるような解法では、メモリが足りなくなる前にまず時間が足りなくなる。