Codeforces Round #627 (Div. 3) E. Sleeping Schedule (R1700)

codeforces.com

問題概要

一日の長さはh時間である。
a_i時間起きて、h時間寝る、をi=1,2,...nと繰り返す人がいる。
起きている時間は毎回、a_iか(a_i)-1を選択できる（つまり寝るのを1時間前倒しできる）。
l時以上r時以下に寝はじめたときを、良い睡眠とする。
最大でいくつの良い睡眠を取れるか？

制約

1 ≤ n ≤ 2000
3 ≤ h ≤ 2000
0 ≤ l ≤ r < h
1 ≤ a_i < h

考察・解法

dp[i][j]を、i日目にj時に寝始める場合の良い睡眠の数の最大値（その時点までの累計）とし、-1で埋めておき、dp[0][0]=1とする。
以下、時間については (mod h) とする。

入眠を前倒ししない場合のi日目からi+1日目への推移を考えると、a[i]時間起きているので、
i日目のj-a[i]時 → i+1日目のj時という風に答えが引き継がれていくことがわかる。（こう推移できないときはdp[i][j-a[i]]==-1になっている）
このとき、i+1日目の入眠時間jがl以上r以下なら、良い睡眠だから1を足す。

（↑完成してから気づいたけど画像にした意味なかった）

答えはmax(dp[n])。
計算量はO(nh)。

# Codeforces Round #627 (Div. 3) E. Sleeping Schedule

n, h, l, r = map(int,input().split())
a = list(map(int,input().split()))
dp = [[-1]*(h) for k in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(h):
        if dp[i][(j-a[i])%h] != -1:
            dp[i+1][j] = max(dp[i+1][j],dp[i][(j-a[i])%h]+(l<=j<=r))
        if dp[i][(j-a[i]+1)%h] != -1:
            dp[i+1][j] = max(dp[i+1][j],dp[i][(j-a[i]+1)%h]+(l<=j<=r))
print(max(dp[n]))