- 考えたこと
- 問題条件を勘違いしてた(白黒2色だと勘違い)ので仕切り直し(ページ末に移動)
- 操作の結果の数え上げ
- 操作の結果の数え上げ→操作の結果が同一になる条件は？
- オーバーラップする区間の操作に関して
- 色が異なっているなら先の操作で操作不能になるのでありえない
- 同じ色なら合成した区間の操作をしたものと同じ
- よって操作の区間はオーバーラップしないものとして良い
- 同じ色が連続してる区間について
- どこを端点に選んでも結果は同じ
- まず連続する同じ色を1マスに潰した列C’を用意する
- 先頭に注目すると、同じ色c=C’0の出現する箇所について残りの部分での場合の数を足し合わせたものになる
- 一般に
- 各ステップごとの足し算の対象は、ならすと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色じゃないのか！問題条件勘違い
- 公式解説がわかりにくい
- https://drken1215.hatenablog.com/entry/2019/03/17/130800
- 区切る位置のDP
- 挟まないか、右端と挟む、の2通りしかないって解説は納得