Codeforces Round #804 (Div. 2)

　Cまで三完。

コンテストへのリンク

D. Almost Triple Deletions

　解説AC。

　（3WAを出した後、乱択解を書いて比較して）区間DPか？　とは思った（DP[i][j]で、A[i]=A[j]のとき、A[i]やA[j]を残すなら最大何個残せるか、などと定義）のだが、三乗以上の時間がかかってしまいそうで、どうやればDPを回せるか分からなかった。

　ここで、

・ある区間[l, r]が消せるのは、その区間に含まれる一番多い数の個数が半数以下のとき

　であることに注目。（このことはコンテスト中気付いていた）

　これを前計算するのは二乗で済む。

　これを用いてDPしようと思えば、区間でDPを定義しなくて良くなる。

・DP[i]=A[i]を残したとき、区間[0, i]でA[i]を残せる個数の最大値

　とすれば、DPが回る。