AGC031B
https://gyazo.com/1b9bf271902f33d4edff465f40136e47
考えたこと
問題条件を勘違いしてた(白黒2色だと勘違い)ので仕切り直し(ページ末に移動)
オーバーラップする区間の操作に関して
色が異なっているなら先の操作で操作不能になるのでありえない
同じ色なら合成した区間の操作をしたものと同じ
よって操作の区間はオーバーラップしないものとして良い
同じ色が連続してる区間について
どこを端点に選んでも結果は同じ
まず連続する同じ色を1マスに潰した列C'を用意する
先頭に注目すると、同じ色c=C'0の出現する箇所$ i \in X(c)について残りの部分での場合の数を足し合わせたものになる
$ f(0) = \sum_{i\in X(C'_0)} f(i+1)
一般に
$ f(i) = \sum f(j + 1) [j \in X(C'_i)][i < j]
各ステップごとの足し算の対象は、ならすとO(1)になる？
色が交互のときがやばそう
色ごとに累積和を持てば良い
Xの計算にO(N)支払うとまずそうなのでC'を作るタイミングでまとめて計算しておくと全体でO(N)
-----
考えたこと(問題条件を勘違いしている)
白と黒のブロックごとに考える
追記: ここで問題条件を勘違いしている
両端が同じブロックだと変化しない
端をブロック内のどこに取るかは結果に関係ない
ブロックの中の石の個数は結果に関係ない
最初のブロックが何色かも結果に関係ない
よってブロックの個数だけから結果が決まる
1,2個の時1通り
3個の時2通り
4個の時、2通りの選択肢があってどちらでも2個の時に帰着する
DPっぽい
f(4)=2f(2)+1
5個の時
1個挟む方法が3通り、3個挟む方法が1通り
1個挟む方法の2つが後で合流するからDPの漸化式が怪しい
10101は11101と10111とになるが、どちらもその後11111になりうる
むしろ「1に揃えることにした時、端でない0のブロックは2個、なので2^2」でいいな
これを0に揃える側でもやる
変化しない1通りは共通なので1引く
まとめ
ブロックの個数をNとする
2^floor(N/2)+2^ceil(N/2)-1
公式解説
DPして愚直O(N^2)、工夫してO(N)とのこと
ちょっと意味がわかりにくい
実装して試す
あっ、白黒2色じゃないのか！問題条件勘違い
公式解説がわかりにくい
挟まないか、右端と挟む、の2通りしかないって解説は納得