コンテンツにスキップ

DOJ Beginner Contest 12 E - Shirogane Wants to Sing

サイト
DOJ
コンテスト
DOJ Beginner Contest 12
問題
E - Shirogane Wants to Sing

長さ NN の非負整数列 AA が与えられます。次の条件をすべて満たす長さ NN の非負整数列 BB の個数を 109+710^9 + 7 で割った余りを求める問題です。

  • B1=0B_1 = 0。
  • すべての 1≤i<N1 \le i < N について ∣Bi−Bi+1∣≤K|B_i - B_{i+1}| \le K。
  • ∑i=1N∣Ai−Bi∣≤E\sum_{i=1}^{N} |A_i - B_i| \le E。

制約は 2≤N≤1002 \le N \le 100、0≤K≤200 \le K \le 20、0≤E≤500 \le E \le 50、0≤Ai≤500 \le A_i \le 50 です。

BB を前から 1 つずつ決めていく DP をします。次の値を決めるのに必要なのは、直前の値 BiB_i と、それまでの誤差の合計だけです。そこで

dpi[e][b]=(B1,…,Bi のうち、誤差の合計が e で Bi=b であるものの個数)\mathrm{dp}_i[e][b] = (B_1, \dots, B_i \text{ のうち、誤差の合計が } e \text{ で } B_i = b \text{ であるものの個数})

とします。dp1\mathrm{dp}_1 は dp1[A1][0]=1\mathrm{dp}_1[A_1][0] = 1 だけが 11 です(A1>EA_1 > E なら答えは 00 です)。dpi[e][b]\mathrm{dp}_i[e][b] から、∣b−b′∣≤K|b - b'| \le K を満たす各 b′b' について、e′=e+∣Ai+1−b′∣≤Ee' = e + |A_{i+1} - b'| \le E なら dpi+1[e′][b′]\mathrm{dp}_{i+1}[e'][b'] に足します。答えは dpN\mathrm{dp}_N の値の総和です。

BiB_i のとりうる範囲は有限です。∣Ai−Bi∣≤E|A_i - B_i| \le E なので、Bi≤Ai+E≤max⁡A+EB_i \le A_i + E \le \max A + E です。よって bb は 00 以上 M=max⁡A+E≤100M = \max A + E \le 100 以下だけを考えれば十分です。

計算量は O(NEMK)O(NEMK) で、最大でも 100×51×101×41≈2×107100 \times 51 \times 101 \times 41 \approx 2 \times 10^7 回程度です。

Python
MOD = 10**9 + 7
N, K, E = map(int, input().split())
A = list(map(int, input().split()))
if A[0] > E:
print(0)
exit(0)
M = max(A) + E
dp = [[0 for i in range(M + 1)] for j in range(E + 1)]
dp[A[0]][0] = 1
for a in A[1:]:
ndp = [[0 for i in range(M + 1)] for j in range(E + 1)]
for i in range(E + 1):
for j in range(M + 1):
for k in range(j - K, j + K + 1):
if k not in range(M + 1):
continue
if abs(a - k) + i > E:
continue
ndp[abs(a - k) + i][k] += dp[i][j]
ndp[abs(a - k) + i][k] %= MOD
dp = ndp
print(sum(sum(a) % MOD for a in dp) % MOD)

dp[i][j] が、誤差の合計が i で直前の値が j である数列の個数です。k が次の値 Bi+1B_{i+1} の候補で、範囲 [0,M][0, M] から外れるものと、誤差の合計が EE を超えるものを飛ばしています。