読者です 読者をやめる 読者になる 読者になる

くれなゐの雑記

身の回りの人や自分が困っていたことを記事にしています

Codeforces #712 Div.2 D. Memory and Scores

要約

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

謝辞, 参考

arrogantldiotさんのソースコードを参考にさせていただきました
codeforces.com