いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

Codeforces Round #462 C. A Twisty Movement

問題

Problem - C - Codeforces

1と2のみからなる長さnの数列が与えられる。
1度だけ連続した区間を選びその区間の1と2を逆転させることが出来る。
最長増加部分列の最大値の長さを出力する。

考察

反転後の数列が
111...111222...222
みたいな感じであれば理想ぽい。
これの反転前を雑にイメージすると
111...122112...222
みたいな感じになる気持ちがある。
ある地点から左は1の個数を最大化、右は2の個数を最大化するような地点を全探索することを考える。
すると左の1の個数の最大化も右の2の個数の最大化も全探索すればいいので、累積和使って計算量を落とす。
累積和パートでO(N)
全探索パートでO(N^2)とかで終わり。

ソース

codeforces.com

添え字ミスには気を付けような