Codeforces #712 Div.2 D. Memory and Scores

問題

codeforces.com

要約

$a,b,k,t$ が与えられる.
$a$ : Memoryさんの初期点数
$b$ : 相手の初期点数
$k$ : 1ターンに $[-k,k]$ の点数を得ることができる
$t$ : 2tターン行う

Memoryさんがかつことができるのは何通りか(MOD 1e9+7)

以下のようなdpを組む

$dp[\mathrm{time}][\mathrm{diff}] :=$ その時間(time)で, Memoryさんのスコア-相手さんのスコアがdiffのときの場合の数

更新方法は簡単で,

$dp[t][d] := \sum_{i=d-K}^{d+K} dp[t-1][i]$

sumはしゃくとり的にやって計算量を減らす.
要素数は $2k+1$ なので注意する(1敗)

最終的に, $d>0$ の部分がMemoryさんが勝つ場合の数なので,

$\mathrm{res} = \sum_{i=1}^{配列の最大} dp[2T][i]$
が答えになる
配列の最大要素, $K*T$ くらいとっとけばいいと思ったけどなんかうまくいかなかった.
また, このままだと負の要素にアクセスすることになるので適当にオフセットかける

SourceCode

const int MOD = 1e9+7;
void solve() {
	ll A, B, K, T; cin >> A >> B >> K >> T;
	//dp[time][diff] := cnt
	vector<vector<ll> > dp(2, vector<ll>(2*1000*(210) + 1));
	int offset = 1000*(210);

	int cur = 0, tar = 1;
	if (A - B + offset <= 0) {
		cout << 0 << endl;
		return;
	}
	dp[tar][A-B+offset] = 1;
	for (int i = 0; i < 2 * T; ++i) {
		//REP(i, dp[tar].size()) cout << dp[tar][i];
		//cout << endl;
		ll sum = 0;
		//全範囲更新 TLEしそうだったら頑張る しゃくとり的に
		REP(j, 2 * K+1) sum = (sum+dp[tar][j])%MOD;
		FOR(j, K, dp[cur].size()-K-1) {
			dp[cur][j] = sum;
			sum = (sum-dp[tar][j - K] + MOD)%MOD;
			sum = (sum+dp[tar][j + K + 1])%MOD;
		}
		swap(cur, tar);
	}
	//REP(i, dp[tar].size()) cout << dp[tar][i];
	//cout << endl;
	ll res = 0;
	//REP(j, dp[tar].size()) {
	FOR(j,offset+1,dp[tar].size()){
		res = (res + dp[tar][j]) % MOD;
	}
	cout << res << endl;
}