「? を 0 1 にそれぞれ\(\frac{1}{2}\) の確率で書き換えた文字列を \(T'\) とする。\(T'\) に対する最小の操作回数の期待値は？」という問題を考えます。この問題の答えを \(2^{qK}\) 倍したものが元の問題の答えです。 (\(T'\) は確率変数であることに注意して下さい)

\(T'\) の最初と最後をつなげて円環状にします。操作を \(1\) 回行うごとに、0 と 1 が隣り合う箇所はちょうど \(2\) 箇所ずつ減るので、\(T'\) に対する最小の操作回数は、(0 と 1 が隣り合う箇所の数) ÷ \(2\) です。

\(T'\) の \(i\) 文字目を \(T'_i\) と表し、添字は \(\bmod |T'|\) で考えます。確率変数 \(X_i\) を、\(T'_i =T'_{i+1}\) なら \(0\)、\(T'_i \neq T'_{i+1}\) なら \(1\) とすると、求めるものは\(\displaystyle E\left[\frac{1}{2} \sum_{i=1}^{|T'|} X_i\right]\) です。 期待値の線形性からこれは \(\displaystyle \frac{1}{2} \sum_{i=1}^{|T'|} E[X_i]\) に等しくなります。

特に、\(i \equiv j \bmod |S|\) のとき \(T_i=T_j\) かつ \(T_{i+1}=T_{j+1}\) となるので \(E[X_i]=E[X_j]\) が成り立ち、\(\displaystyle \frac{1}{2} \sum_{i=1}^{|T'|} E[X_i] =\frac{1}{2}K \sum_{i=1}^{|S|} E[X_i]\) となります。

\(E[X_i]\) は\(S_i,\ S_{i+1}\) がそれぞれ ? 0 1 のいずれであるかによって、\(0,\frac{1}{2},1\) のいずれかの値を取ることが直ちに計算できるため、\(O(|S|)\) で答えを求めることができます。

なお、上の議論は |T’|=1のとき成り立ちません。このケースのみ場合分けして答える必要があります。

どこが成立しないか考えてみましょう。