Codeforces #767 : Div1 D2. Game on Sum (Hard Version)

本番Easyはどうにか解いているが。
https://codeforces.com/contest/1628/problem/D2

問題

整数N,M,Kが与えられるので、以下の問いに答えよ。
2人で以下をN回繰り返す。

初期状態でスコアは0である。
先手は0以上K以下の任意の実数を選択する。
その後、後手はそれをスコアに加算するか減算するか選択する。ただし、N回中M回は加算を選択しなければならない。

先手はスコアの最大化、後手は最小化を図るとき、両者が最適手を取ると最終的なスコアはどうなるか。

解法

dp(i,j) := あとi回手番があり、加算がj回できる場合のスコアの値
とする。

• dp(i,0) := 0
• dp(i,i) := K*i
• dp(i,j) = (dp(i-1,j-1)+dp(i-1,j))/2

で遷移する。このままこのDPを解くとO(N^2)なので、Easyは通る。

最後のパターンを2で割る部分を無視すると、これはよくあるグリッド上の経路の数え上げみたいな問題になる。
とすると、dp(a,b)→dp(i,j)の寄与は、Comb(i+j-a-b,i-a)/2^(i+j-a-b)といえる。

そこで、dp(i,i)→dp(N,M)の寄与分を各iごとに加算すればよい。

int T;
ll N,M,K;
const ll mo=1000000007;

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 comb(ll N_, ll C_) {
	const int NUM_=2400001;
	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 dp[2020][2020];
ll F[1010101];
ll G[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=1000000;i++) {
		F[i]=i*modpow(2,i-1)%mo;
		G[i]=(F[i]+mo-F[i-1])%mo;
	}
	
	
	
	cin>>T;
	while(T--) {
		cin>>N>>M>>K;
		
		ll ret=0;
		FOR(i,M+1) {
			ret+=G[i]*comb(N-M+(M-i),M-i)%mo;
		}
		ret=ret%mo*modpow(modpow(2,N-1))%mo;
		cout<<ret*K%mo<<endl;
	}
}

まとめ

DPの形からグリッド上の経路の形に変形するの、今後も時々ありそうだな…。