京セラプログラミングコンテスト2021 F - Minflip Summation (600)
文字列が定まったとき、最小の操作回数は0と1が切り替わっている回数の半分(端数は切り上げ)
解説の方法
$ qを?の個数とする
最終的な文字列長が1なら答えは0
それぞれの文字列間での切り替わりの発生する期待値を出してk倍して$ 2^{kq}をかける
左右どちらかが?なら1/2で発生
それ以外で左右が異なるなら必ず発生
$ k-1回文字列の最初と最後の間が繋がるので、これについても上と同様に足す
解説では最初と最後の文字が異なる場合の補正があったが入れなくてもACした
テストケースが弱い?
最初と最後の文字しか無いところに新しく文字を挿入することを考える
挿入によって切り替わり回数が偶数回しか変わらないことが分かる
よって全体での偶奇は最初と最後の文字が異なるかどうかに依る
元の文字列の期待値を求めるのが$ \mathcal{O}(N)で最後に累乗を掛けるのが$ \mathcal{O}(\log (NK))