Codeforces ECR #068 : F. Crossword Expert

これは良い練習になった。
https://codeforces.com/contest/1194/problem/F

問題

N個の問題があり、それぞれ解くのに基本的にt[i]分かかる。
ただし、各問題1/2の確率で1分余分、すなわち(t[i]+1)分かかる。

先頭の問題から順に解く場合、T分間に何問解けるか、その期待値を答えよ。

解法

E(i) := i問目を解ききれる確率
と考えると、sum(E(i))が解となる。
よって各E(i)を求めることを考えよう。
i問目以前が全部1分余分にかかってもT分以内ならE(i)=1だし、全部時間通り解けてもT分に収まらないならE(i)=0である。

以下、それ以外の場合を考える。
最大p問、すなわちp分までなら余分に時間がかかってもi問目が解けるとすると、

である。あとはこれを各iについて求めよう。

なお、ここではのprefixの和を求める演算が出てくるが、これを毎回答えていると重い。
ただ、であることを用いると、のprefixの和をiやkを少しずつずらしながら求めていくことはさほど難しくない。
iの上限がNまででよいことを考えると、各iにおいて合計でCombinationはO(N)回程度求めれば済む。
(パスカルの三角形中の位置をO(N)回程度移動する感覚)

int N;
ll T;
ll A[202020],S[202020];
ll P[202020];
const ll mo=1000000007;
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;
}

ll combsum(ll N,ll C) {
	static int pn=0,pc=0;
	static ll pre=1;
	
	while(N>pn) {
		pre=(pre*2+mo-comb(pn,pc))%mo;
		pn++;
	}
	while(C>pc) (pre+=comb(pn,++pc))%=mo;
	while(C<pc) (pre+=mo-comb(pn,pc--))%=mo;
	return pre;
}

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;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	FOR(i,N) {
		cin>>A[i];
		S[i+1]=S[i]+A[i];
	}
	
	ll ret=0;
	for(i=1;i<=N;i++) {
		if(S[i]>T) continue;
		ll lef=T-S[i];
		if(lef>=i) {
			P[i]=1;
		}
		else {
			P[i]=combsum(i,lef)*modpow(modpow(2),i)%mo;
		}
		
		ret+=P[i];
	}
	cout<<ret%mo<<endl;
	
}

まとめ

パスカルの三角形を辿る感覚は覚えておきたい。