phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

みんなのプロコン2019 D. Ears

問題

数直線上のある整数点から自由に左右の整数点に移動し、どこかの整数点で終わるような行動をする。
このとき、整数iについて、i-0.5の地点を通過したら、i番目の位置に石を1つ置く。

目標となるi番目の石の数A_iが与えられたとき、上記の行動を行った後で、目標の石の数にするために石を追加または除去することができる。
追加または除去する石の個数が最小となるように行動を行った時の、追加または除去する石の総数を答えよ。

制約

  • 0 <= A_i <= 10^9, (1 <= i <= 2 * 10^5)

解法

行動を行った後の石の形には法則性があり、
【0個】【0でない偶数個】【奇数個】【0でない偶数個】【0個】
のようなゾーンにわかれる(ゾーンがない場合もある)。

dp[i][j] := i番目がゾーンj(上記)だった場合の最小の追加または削除の回数
として、更新すればよい。

解法2

(コンテスト中考えていた方向性の解法で、一応通ったのでメモしておく)

行動を、ある整数iに注目すると、「左から入って右にぬける」「右から入って右にぬける」「左から入って左に抜ける」「右から入って左に抜ける」ような4パターンがあることがわかる。

ここで、右にぬけるようなパターンについてだけ考えると、i番目の地点で右に抜けるようなパターンの最小コストは、
dp1[i][0] := i番目で右から入り、0~i番目のどこかを通って、i番目で右にぬけた場合の最小コスト
dp1[i][1] := 0~i番目のどこかで入り、i番目で右にぬけた場合の最小コスト
を更新すれば、求められる。
(更新は、i-1までのdpの値から更新する場合とi-1までをすべて捨てて更新する場合を考える。A_i=0となる場合のコストに注意)

同様に、逆方向からdpすれば左にぬけるようなパターンについても同様に最小コストが求めらえる。(これをdp2とする)

あとは、ある地点iを境に左側を通った時の最小コストdp1[i][x]と右側を通った時の最小コストdp2[i][y]の組み合わせで最小となるなるものを見つければ、求められる。(dp2は通る向きを逆向きで考えれば等価)

その他

解法2の方の類題
D - 建物