Dytechlab Cup 2022 : E. Ela Goes Hiking

出来がいまいちだった回。
https://codeforces.com/contest/1737/problem/E

問題

左右に展開される1本路の道路に、N体の蟻が要る。
初期状態で各蟻の重さは同じである。

各蟻は、それぞれ等確率で左右いずれかに移動を開始する。
道路は終点があり、終点に到達した蟻は反転して動き続ける。
もし2体の蟻が衝突すると、重い方の蟻が軽い方の蟻を食べ、重さを吸収しながら移動し続ける。
もし2体の蟻の重さが同じなら、右側が左側を食べる。

蟻の移動方向は2^N通りある。
各蟻が最後の１対として残るのは何通りか。

解法

一番右の蟻を除けば、最初に右に行くと必敗である。
左に行った場合、左側をすべて吸収する確率を求めよう。
その後、折り返して右側の蟻をすべて吸収できないケースを引く。

int T,N;
const ll mo=1000000007;

ll p2[1010101],r2[1010101];
ll dp[1010101],sum[1010101];



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=r2[0]=1;
	p2[1]=2;
	r2[1]=(mo+1)/2;
	for(i=2;i<=1000001;i++) {
		p2[i]=p2[i-1]*2%mo;
		r2[i]=r2[i-1]*r2[1]%mo;
	}
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		if(N==1) {
			cout<<1<<endl;
			continue;
		}
		
		//まず過半数勝つ
		for(i=2;i<=N;i++) {
			int win=(i+1)/2-1;
			if(i==N) dp[i]=r2[win];
			else dp[i]=r2[win+1];
			sum[i]=0;
		}
		sum[N+1]=0;
		for(i=N;i>=2;i--) { //右に負ける確率を引く
			(sum[i]+=sum[i+1])%=mo;
			dp[i]=dp[i]*(mo+1-sum[i])%mo;
			int win=(i+1)/2;
			
			(sum[i-win]+=dp[i])%=mo;
		}
		
		for(i=1;i<=N;i++) cout<<dp[i]<<"\n";
	}
	
}

まとめ

もうちょい問題文短くならないかな…。