AtCoder ARC044 C
問題リンク https://atcoder.jp/contests/arc044/tasks/arc044_c 解説 縦のビームが飛んでくるとき、高橋君は横に逃げます。このとき、縦に逃げる必要はないため、縦方向の座標は考えなくてよいです。横のビームも同様です。したがって、縦に逃げる回数と横に逃げる回数を独立に計算して足し合わせれば答えが求まります。 縦のビームを考えましょう。各時刻にそれぞれの座標にいるときの移動回数の最小値を、配列\(move\)で管理します。最初、すべての座標について移動回数は\(0\)です。 \[\begin{array}{c|c|c|c|c|c|c|c} \text{座標} & 1 & 2 & 3 & 4 & 5 & 6 & \ldots \\ \hline \text{移動回数} & 0 & 0 & 0 & 0 & 0 & 0 & \ldots \end{array}\] ここで、ある時刻に座標\(2, 3, 4, 5\)にビームが通過したとします。次のようにして移動回数を更新してみましょう。 ビームが通過した直後に座標\(2, 3, 4, 5\)にいることはないため、これらの座標の移動回数を無限大とする ビームが通過した座標に、その左右の位置から移動してくる。ビームが通過した座標を\(p\)として、\(move(p) = 1 + min(move(p - 1), move(p + 1))\)で更新する 手順2を座標\(2, 3, 4, 5\)の順に左から行うと、更新後の移動回数は次のようになります。 \[\begin{array}{c|c|c|c|c|c|c|c} \text{座標} & 1 & 2 & 3 & 4 & 5 & 6 & \ldots \\ \hline \text{移動回数} & 0 & 1 & 2 & 3 & 1 & 0 & \ldots \end{array}\] これは最適ではありません。座標\(4\)に移動するためには、座標\(6\)から左に2回移動するのが最適です。このよ