Codeforces #370 Div2 D. Memory and Scores

めんどいだけで面白みは少ないな…。
http://codeforces.com/contest/712/problem/D

問題

初期状態で先手はA点、後手はB点のスコアを持つ。
ゲームを一回行うと、各人[-K～K]の(2K+1)通りのいずれかのスコアを得る。
Tゲームを繰り返したのち、先手の方が合計スコアが大きくなるスコア取得の組み合わせは何通りか。

解法

以下の状態を考える。
dp(i,d) := i回ゲームを実行後、両者のスコア差がdである組み合わせ
dp(T,(正の値))の総和が解となる。

1回ゲームを行うと、スコア差がd'だけ増すようなスコアの組み合わせは(2*K+1-abs(d'))である。
よってdp(i,d) = sum(dp(i-1,d-d')*(2*K+1-abs(d')))の関係にある。
dがO(|A|+|B|+T*K)程度の値になることを考えると、このDPは真面目に行うとO(T*(|A|+|B|+T*K)*K)となりTLEする。
そこでsumの計算を高速に行うことを考えよう。

dp(i,d) = dp(i,d-1) + (dp(i-1,d)+dp(i-1,d+1)+...+dp(i-1,d+K+1)) - (dp(i-1,d-1)+dp(i-1,d-2)+...+dp(i-1,d-(K+1)))
で、後ろの項はdp(i-1,d)に対する累積和を取っておけばdp(i,d)をO(1)で更新できる。
よって全体の計算量をO(T^2*K)程度に抑えることができる。

int A,B,K,T;
ll mo=1000000007;

int pat[4040];
ll from[430000];
ll to[430000];
ll sum[430002];

ll* FF=from+210000;
ll* SS=sum+210001;
ll* TT=to+210000;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>K>>T;
	
	FF[A-B]=1;
	
	while(T--) {
		ZERO(to);
		for(i=-203000;i<=203000;i++) SS[i]=SS[i-1]+FF[i];
		ll su=0;
		for(i=-201000;i<=201000;i++) {
			if(i==-201000) {
				for(x=-2*K;x<=2*K;x++) su += (2*K+1-abs(x))*FF[i+x];
				su %= mo;
			}
			else {
				su += SS[i+2*K]-SS[i-1];
				su -= SS[i-1]-SS[i-2*K-2];
				su = (su%mo+mo)%mo;
			}
			TT[i]=su;
		}
		swap(from,to);
	}
	ll ret=0;
	for(i=1;i<=201000;i++) ret += FF[i];
	cout<<ret%mo<<endl;
	
	
}

まとめ

スコアにマイナスって必要だったのかな。