kmjp's blog

競技プログラミング参加記です

AtCoder ARC #132 : E - Paw

FよりEの方がずっと難しい…。
https://atcoder.jp/contests/arc132/tasks/arc132_e

問題

N個のマスが左右1列に並んでおり、一部のマスには左向きまたは右向きのマークがついている。
この状態で、以下を繰り返す。

  • マークがついていないマスを1つ等確率で選び、猫をそこに配置する。その後、左右どちらかを1/2の確率で選択して、その向きに猫を動かす。
  • 別のマークがついてないマスか、両端に到達するまで猫は移動し続ける。その際、既存のマークは猫の移動方向に上書きされる。
    • もし猫が別のマークがついてないマスに到着したら、まだ1/2の確率で左右どちらかに移動する
    • 猫が端に到達した場合、1行目に戻る

全マスにマークがついた時、左向きのマークとなるマス数の期待値を求めよ。

解法

細かい証明はおいておいて解き方だけ。
最終的には、マス目は以下の形になる

<<<<(左向きで上書き)<<<<....(元のまま)....>>>>>(右向きで上書き)>>>>

マークのついてないマスで領域を区切ったとき、それぞれの領域が元のままである確率を求められれば、その時左向きのマークがついたマス数の期待値が求められる。
初期状態でマークのついてないマスがk個あるとする。
L(x)を、x個マークのついてないマスがあるとき、それら全部が左向きになるような猫の配置・移動経路選択の組み合わせとする。
R(x)を、同じく右向きのケースとする。L(x)=R(x)なのは自明。
ここで、L(x)=L(x-1)*(2x-1)となる。
左にx個、右に(k-x)個マークのついてないマスがある領域でできる猫の配置・移動経路選択の手順は、L(x)*R(k-x)*Binom(k,x)となる。

猫の初期配置と移動経路は、全部で2K!!通りあるので、(手順数)×(左向きマスの数)の総和をこれで割ることで期待値を算出できる。

int N;
string S;
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 L[202020];
ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	vector<pair<int,int>> V={{0,0}};
	vector<int> sum={0,0};
	FORR(s,S) {
		if(s=='<') V.back().first++,sum.back()++;
		if(s=='>') V.back().second++,sum.back()++;
		if(s=='.') {
			V.push_back({0,0});
			sum.push_back(sum.back());
		}
	}
	
	L[0]=1;
	for(i=1;i<=200000;i++) L[i]=L[i-1]*(2*i-1)%mo;
	
	ll ret=0;
	FOR(i,V.size()) {
		x=i;
		y=V.size()-(i+1);
		
		ll pat=L[x]*L[y]%mo*comb(x+y,y)%mo;
		(ret+=(sum[i]+i+V[i].first)*pat)%=mo;
	}
	
	for(i=1;i<=V.size()-1;i++) ret=ret*modpow(2*i)%mo;
	
	cout<<ret<<endl;
}

まとめ

L(x)の漸化式や総数の計算がすんなりできないなぁ。