AtCoder ARC #109 : E - 1D Reversi Builder

実装は短いけど、考察はしんどい。
https://atcoder.jp/contests/arc109/tasks/arc109_e

問題

1列に並んだNマスからなる変則オセロを考える。
まず、各マスはランダムに白黒で塗る。
次にSマス目に、マスの色と同じ色の石を置く。

以後、先手後手交互に以下の手順を行う。

• すでに石があるマスの隣接マスのうちいずれかに、まだ石が置かれていないマスにマスろ同じ色の石を置く。
• その際、オセロと同様に既存の石の色が白黒入れ替わる。

先手は黒石、後手は白石を増やすようにふるまう。
各Sに対し、黒石の個数の期待値を求めよ。

解法

ほとんどのケースでは、白黒判定すると最終的な状態も一致する。
そのため、おおむねN/2が期待値となる。
唯一の例外は、先手が有利なケースである。

両端が白黒異なるマスであるケースを考える。

両者の最適手は、自身の増やしたい色と同じ色の端のマスの連結成分に向けて、最速で石を置くことである。
その連結成分は、（オセロの角マス同様）それ以上色が変化しないためである。
そう考えると、唯一先手後手の差が出るのは、Sから端の白の連結成分までの距離と、端の白の連結成分までの距離が等しい時である。

よってそのようなパターンを数え上げよう。
両端の連結成分までの距離を決めると、間の白黒どちらでもよいマスの数が決まり、その組み合わせ数も決まる。

int N;
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll ret[202020];
ll p2[202020],r2[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	p2[0]=r2[0]=1;
	FOR(i,201010) {
		p2[i+1]=p2[i]*2%mo;
		r2[i+1]=r2[i]*(mo+1)/2%mo;
	}
	
	for(i=2;i<=(N-1)/2;i++) {
		(ret[i]=ret[i-1]+2*(2*i-1)*r2[N-(2*i-3)])%=mo;
	}
	
	FOR(i,N) {
		j=N-1-i;
		ll dif=ret[min(i,j)];
		ll pat=(N+dif)*r2[1]%mo;
		cout<<pat<<endl;
	}
	
	
}

まとめ

こちらはまだいいんだよね。