問題

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d

考え方

まずはすぬけくんが散歩する操作をシミュレーションする。そうすると散歩による操作を数列で表すことができることがわかる。その数列はある性質を持っていて以下のように表される。

0 even odd even 0

イメージ図は以下の通り。言われれば確かにそうなるのは分かるが...

f:id:d_tutuz:20190210195918j:plain

よって、この数列と元の数列 $\{A_L\}$ の差を考える。数列の区切り位置を全探索すること計算量的にできない。DPを考えることにする。

$dp[i][j] := i+1$ 番目までの要素で状態が $j$ であるときの差の最小値

と定義する。 $j$ の状態数が $5$ であることからこのDPを定義することができる。 DPの初期値は

$dp[0][j] = 0\ (0 \le j \le 4)$

でDP遷移は

$dp[i+1][j] = min(dp[i+1][j], dp[i][j] + cost(i, k))$

である。 $cost(i, k)$ は $A_i$ を状態 $k$ に割り当てたときの差の最小値である。１例えば、状態が $0$ から $3$ に遷移するのは無駄だが、最適な解にはなり得ないので無視して大丈夫である。

どこに着目して考察するべきだったか

まずは、すぬけくんが散歩する経路をシミュレーションすることが重要そう。次に、散歩するという操作を数列で表すと、一般に 0 even odd even 0 のような形で表されることが分かる。ここまで来ると、この数列と元の数列の差を考えればよい。この数列の区切り位置を全探索することはできないが、DPを考えると解ける。

「こういうゴチャゴチャした状態遷移を扱う問題はそのまんま DP になるイメージがある。*1」らしい。たしかに Tree Burning もごちゃごちゃしていたが、DPを考えると部分点解が自然に浮かぶような気がする。