HUPC2020Day3 G Katsusando - ツバサの備忘録

解法

まず、二人が出会う地点は必ずカツが置いてある座標になります。途中で挟むとしても、左右どちらかのカツで出会うように適切に調整することで損をすることはありません。

$dp[i] =$ 左から $i$ 番目のカツまで食べ終えた状態のときに経過した時間の最小値

としてこれを解こうとします。
今、 $j$ 番目のカツの座標で次のカツサンドを作成するとします。また、

$d_{(i,j)} = i$ 番目のカツに誰かを配置して、 $j$ 番目のカツに移動させたときにかかる時間

とします。これは $O(N^{2})$ で計算できます。 $i,j$ はどちらが大きくても問題ないです。

そのとき、左側における行動の最適解は $min\left(dp[p] + d_{(p+1,j)}\right)$ になります。この時間を $T$ とします。これが求まると、
$dp[i] = min\left(dp[i], T + d_{(i,j)} + K + 1\right)$
という計算をしていくことで、dpの計算ができます。
あとは、 $dp[N]$ を答えれば終了です。
コストを求める前計算、dpの計算共に $O(N^{2})$ になります。

感想

カツを挟む部分を決め打った場合に更新が楽にできるようになり、これはあまり普段使わない考え方だったので面白かったです。