言及解禁されたので公開です。一回後回しにしたけどこれが解けたら中級に乗るってところだったので頑張って解きました
問題を記録しておくのを忘れたのでうろ覚えで書いていますがACになったことは確かなので…………
↑公開された問題原文です。
問題
エヌ氏が数直線上 $0 \le x \le L$ でハードル走をします。$N$ 本のハードルがそれぞれ位置 $ x_i $ に立っています。エヌ氏が走って $1$ 進むのに必要な時間は $T_1$ 、ジャンプしたまま $1$ 進むのに必要な時間は $T_2$ です。また、ハードルがあるところをジャンプせずに通過しようとするときは、通過する直前で余計に $T_3$ の時間がかかります。エヌ氏は以下のいずれかの行動をとります。
- 走って1進む。
- 走って0.5進み、ジャンプして1進み、走って0.5進む。合計で2進む。
- 走って0.5進み、ジャンプして3進み、走って0.5進む。合計で4進む。
ゴール $x = L$ を通過するまでの最短時間を求めてください。なお、ジャンプ中に $x=L$ を通過するときは、空中で $x=L$ を通過した瞬間が求める時間です（ゴールの先に着地する時間では無い）。
入力
$x_1 \quad x_2 \quad\cdots\quad x_{N-1}$
$T_1 \quad T_2 \quad T_3$
制約
- $0 < x_i < L$
- $T_1,T_2,T_3$ はそれぞれ偶数
例
説明がどうもややこしいですね
$x=2$ にハードルが立っているとき
- 0から1を通過するまで、走って進むとき時間 $T_1$ かかる
- 1から2を通過するまで、走って進むとき時間 $T_1 + T_3$ かかる。走ってハードルがあるところを通過しようとするので余計に $T_3$ かかっている
- 0から2を通過するまで、ジャンプして進むとき時間 $T_1 + T_2$ かかる
- 0から4を通過するまで、3番目のロングジャンプ(?)で進むとき時間 $T_1 + T_2\times 3$ かかる
$x=5$ がゴールのとき
- 4からゴールを通過するまで走って進むとき、時間 $T_1$ かかる（先述の通り）
- 4からゴールを通過するまでジャンプして進むとき、0.5走って、ジャンプして0.5進んだところでゴール上空を通過するので時間 $0.5\times T_1 + 0.5\times T_2$ かかる
- 3からゴールを通過するまでジャンプして進むとき、0.5走って、ジャンプして1.5進んだところでゴール上空を通過するので時間 $0.5\times T_1 + 1.5\times T_2$ かかる
入出力例
//input 2 5 1 4 4 2 8 //output 13
↓図にするとこんな感じ
| | +--+--+--+--+--+ 0 1 2 3 4 5
解法
動的計画法です。位置 $x=j$ を通過するまでの最短時間は、$x=i \ (0 \le i < j)$ への最短時間がわかっていれば求められます。
- 1つ前のところ $x= j -1$ から $T_1$ で来る
- 2つ前のところ $x= j -2$ から $T_1 + T_2$ で来る
- 4つ前のところ $x= j -4$ から $T_1 + T_2\times 3$ で来る
- 但し、$x_j$ にハードルが立っていたら、どの方法でも $T_3$ 余計に時間がかかる
以上のうち最短になるものを選びます。いわゆる「貰うDP」です。この方法でとりあえず位置 $ x = L - 1 $ までそれぞれ通過するまでの最短時間を求めます。その後、 $x=L$ について
- $ x = L - 1 $ から走って来る
- $ x = L - 2 $ からジャンプして着地
- $ x = L - 4 $ からジャンプして着地
- $ x = L - 1 $ からジャンプ中に通過
- $ x = L - 2 $ からジャンプ中に通過
- $ x = L - 3 $ からジャンプ中に通過
のうち最短で来れる方法をとれば良いです。
イメージ
ハードルの無い位置を丸で、ハードルのある位置を四角で表すと次のようなイメージです。
入出力例に則って、$ x = 4 $ までの遷移は
ハードルの無いところに着地する黒の線と、ハードルのあるところに着地する赤の線があります。
$ x = 5 $ を通過する方法は
$x=5$ に着地する方法と、$x=5$ の空中を通過する方法があります。
dpテーブル
$T_1 = 4, \ T_2 = 2, \ T_3 = 8$ としてdpテーブルを埋めてみます。
$$ dp[i] := 位置iを通過するまでの最短時間 $$
- 初期値
| i | 0 |
|---|---|
| dp[i] | 0 |
- $i=1$
| i | 0 | 1 |
|---|---|---|
| dp[i] | 0 | 12 |
\begin{align} dp[1] &= dp[0] + 4+8\cr &= 12 \end{align}
- $i=2$
| i | 0 | 1 | 2 |
|---|---|---|---|
| dp[i] | 0 | 12 | 6 |
\begin{align} dp[2] &= \min \{dp[1] + 4, dp[0] + 4+2 \}\cr &= \min \{16, 6\} = 6 \end{align}
- $i=3$
| i | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| dp[i] | 0 | 12 | 6 | 10 |
\begin{align} dp[3] &= \min \{dp[2] + 4, dp[1] + 4+2 \}\cr &= \min \{10, 18\} = 10 \end{align}
- $i=4$
| i | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| dp[i] | 0 | 12 | 6 | 10 | 18 |
\begin{align} dp[4] &= \min \{dp[3] + 4+8, dp[2] + 4+2+8, dp[0] + 4+2 \times 3 + 8 \}\cr &= \min \{22, 20, 18\} = 18 \end{align}
- $i=5$ （ゴール）
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| dp[i] | 0 | 12 | 6 | 10 | 18 | 13 |
- $dp[4] + 4 = 22$
- $dp[3] + 4+2 = 16$
- $dp[1] + 4+2\times 3 = 22$
- $dp[4] + 4\times 0.5 + 2\times 0.5 = 21$
- $dp[3] + 4\times 0.5 + 2\times 1.5 = 15$
- $dp[2] + 4\times 0.5 + 2\times 2.5 = 13$
の最小値をとって $dp[5] = 13$ です。
実装
それぞれの位置にハードルがあるかどうかをbool型の配列で保管しておき、dpの増加幅に $T_3$ を加えるかどうか分岐します。条件演算子の活躍が光りますね(?)
#include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vb = vector<bool>; #define INF 1<<29 //無限大 int main(){ int N,L;cin>>N>>L; vb isHurdle(L, false); for(int i=0; i<N; i++){ int x;cin>>x; isHurdle[x] = true; } int t1, t2, t3; cin>>t1>>t2>>t3; vi dp(L, INF); //座標i通過までの最短時間 Lの手前まで見ておく dp[0] = 0; for(int i=1; i<L; i++){ int a = dp[i-1] + (isHurdle[i]? t1+t3 : t1); if(i==1){ dp[i] = a; continue; } int b = dp[i-2] + (isHurdle[i]? t1+t2+t3 : t1+t2); if(i<4){ dp[i] = min(a, b); continue; } int c = dp[i-4] + (isHurdle[i]? t1+(t2*3)+t3 : t1+(t2*3)); dp[i] = min({a,b,c}); } int ans = min({ dp[L-1] + t1, //1つ前から普通にくる dp[L-2] + t1+t2, //2つ前から飛んで着地 dp[L-4] + t1+(t2*3), //4つ前から飛んで着地 //ジャンプ中通過 dp[L-1] + t1/2 + t2/2, //1つ前からジャンプ中 dp[L-2] + t1/2 + t2/2*3, //2つ前からジャンプ中 dp[L-3] + t1/2 + t2/2*5 //3つ前からジャンプ中 }); cout<<ans<<endl; }
