[AOJ] No. 0299 鉄道路線II

問題

方針

買い物をする駅の番号の順番を変えても影響がないので、\( d_i \) を昇順に整列させます。ここで、\( d_i < p \) を満たす最大の \( d_i \) を \( l \) とし、\( d_i > p \) を満たす最小の \( d_i \) を \( r \) とします。\( d_i = p\) を満たす \( i \) が存在しないことに注意します。ここで、\( L(s, g) \) を 左回りで 駅 \( s \) から 駅\( g \) まで行く時のコストとして、\( R(s, g)\) を右回りで 駅 \( s \) から 駅\( g \) まで行く時のコストとします。このとき、

\[\begin{eqnarray}
L(s, g) &=& \begin{cases} 100(s – g) & ( g \leq s ) \\ 100(N – (g – s)) & ( g > s ) \end{cases}\\
R(s, g) &=& \begin{cases} 100(N – (s – g)) & ( g \leq s ) \\ 100(g – s) & ( g > s ) \end{cases}
\end{eqnarray}\]

となります。最適な駅の周り方は、方向を転換して回るのが少なくとも \( 1 \) 回だけなので、全探索を行います。

全て同じ方向に進むとき

全て左回りで行動するときの最小のコストは、\( L(p, r) \) となり、全て右回りで行動するときの最小のコストは \( R(p, l) \) となります。

駅 \( d_i \) まで左回りに進んだ後、右回りで進む

\( i = 0 \) のとき

このときの最小のコストは、\( 2L(p, d_0) + R(p, d_{M – 1}) \) となります。

\( i \neq 0 \) のとき

このときの最小のコストは、\( 2L(p, d_i) + R(p, d_{i – 1}) \) となります。

駅 \( d_i \) まで右回りに進んだ後、右回りで進む

\( i = M – 1\) のとき

このときの最小のコストは、\( 2R(p, d_i) + R(p, d_{0}) \) となります。

\( i \neq M – 1 \) のとき

このときの最小のコストは、\( 2R(p, d_i) + R(p, d_{i + 1}) \) となります。

コード