AGC_050-B.txt

【解説】AtCoder Grand Contest 050 (Good Bye rng_58 Day 1) Ｂ問題「Three Coins」


●問題
https://atcoder.jp/contests/agc050/tasks/agc050_b


●解説
　コインの有無を反転する操作は「長さが３の区間」に対して行うことになっていますが、これは「長さが３の倍数の区間」だったとしても答えは変わらないので、そう読み替えます。すると、操作の対象となる区間は互いに交差しない（共通部分がない or 包含関係にある）と仮定しても良いことになります。これを踏まえて、次のような区間ＤＰをします。

　まず、ＤＰの状態を
　　　　dp0[L][R] := 区間 [L, R) 内のどのマスにもコインが「ない」状態から、区間の内部への操作だけでできる、区間内の点数の最大値
　　　　dp1[L][R] := 区間 [L, R) 内のどのマスにもコインが「ある」状態から、区間の内部への操作だけでできる、区間内の点数の最大値
と規定します（マスの番号は 0-index とします）。すると、初期値は各 i (0 <= i < N) に対して
　　　　dp0[i][i+1] = 0
　　　　dp1[i][i+1] = a[i]
となります。

　次に dp0 の遷移を考えます（dp0 と dp1 は対称なので、dp1 の遷移も dp0 と同様になります）。
　まず dp0 の遷移として挙げられるのは、２つの区間を連結する遷移、つまり
　　　　dp0[L][R] ← max_{M: L < M < R} (dp0[L][M] + dp0[M][R])
という遷移です。
　ここで、dp0[L][R] への遷移がこれ以外にあるかについて考えます。２つの区間の連結では実現できないケースというのは、区間 [L, R) 内に分割できる場所がないということなので、つまり区間 [L, R) 全体を反転する操作が含まれているケースに限られます。そして、そのようなケースとは dp1[L][R] の集計対象に他なりません。
　従って、区間の長さ R - L が３の倍数である場合には
　　　　dp0[L][R] ← dp1[L][R]
という遷移も行われ、そしてこれが dp0 の遷移のすべてです（dp1 に関しても同様です）。

　このＤＰを、区間の長さが短い方から順に計算したときの dp0[0][N] がこの問題の答えです。時間計算量のオーダーは O(N^3) です。


●実装例（C++）
https://atcoder.jp/contests/agc050/submissions/19004943