yukicoder : No.1840 Random Painting

これは考察が難しい。
https://yukicoder.me/problems/no/1840

問題

N個のマスが円環状に並んでいる。
各マスは黒で塗られているか、まだ塗られていないかである。
駒を0番のマスに置いた後、以下のように駒が移動するとする。

• 1/2の確率で、左右どちらかのマスに移動する。
• 移動先のマスがまだ塗られてないなら、黒く塗る

全マスが黒く塗られるまでの移動回数の期待値を求めよ。

解法

塗られてないマスの集合をSとしたとき、f(S)をSの状態をキープする回数の期待値+1とすると、包除原理より解はsum*1となる。

• f(S)の状態が崩れるのは、S中で初期位置より時計回りまたは反時計回りの最寄のマスが黒く塗られる時である。逆に、|S|が3以上の時、その最寄りの1または2マス以外の有無は、f(S)の値に影響しない
• しかし、それらの最寄りの1または2マス以外に、間にもともと塗られていないマスがあったとしても、その有無は、包除原理の過程で(-1)の偶奇に対応するため、そのようなマスが存在すると互いに相殺して最終的な解に寄与しない。
• Sのうち、時計回りと反時計回りで初期位置からの最寄のマスまでの距離がx,yの時、f(S)=x*yである。

そこで、そのようなマスがない状態だけ数え上げればよい。
塗られていないマスの番号からなる数列をVとする。

• 最寄りのマスが共通する1マスの場合、sum(V[i]*(N-V[i]))を加算
• 最寄りのマスが(塗られていないマスだけ見たとき)隣接する2マスの場合、sum(V[i]*(N-V[i+1]))を減算

int N;
string S;
vector<ll> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	ll pre=0;
	ll ret=0;
	FOR(i,N) if(S[i]=='0') {
		ret+=1LL*i*(N-i);
		ret-=1LL*pre*(N-i);
		pre=i;
	}
	cout<<ret<<endl;
}

まとめ

f(S) = x*yになるの、ギャンブラーの破産問題って問題は知らなかったけど、なんか昔SRMで見たような気がする。

*1:-1)^(|S|-1)*f(S