Codeforces Round #627 Div.3 E. Sleeping Schedule : 周回するDP

6851 ワード
動的計画法 codeforces codeforces テキストリンク

概要

  • 1日はh時間であり、$l$から$r$時の間に寝ると良い睡眠である
  • あなたは今からn回ねることを計画しており、それぞれi回目の睡眠は$a_i$時間あるいは$a_i - 1$時間後に取る。
    • 訳注: h=24として、3,4,5となっている場合(もし、全部-1しないなら)3, 7, 12時になることになる。(何時間寝るかはここで問題にならないらしい)
  • あなたは最大で何回の良い睡眠をとれるか？

こう考えた

DPで考える。

  • dp[寝た回数][時間] = 良い睡眠の数。として考える。
  • 次の睡眠をとると、$a_{i}$時間後あるいは$a_{i}-1$時間後に、その良い睡眠の数を引き継げる。これは最大を取ればいい(max)。
  • 各DPの計算後、計算したDP列の良い睡眠の時間に値が入っているなら1加算する。
    • 値が入っているなら、がポイントで、その時間に到達しないのに加算すると変なことになる

コード

from pprint import pprint
n, h, l, r = map(int, input().split())
data = list(map(int, input().split()))
dp = [[-1] * h for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    x = data[i]
    for j in range(h):
        if dp[i][j] == -1: # not visit
            continue
        dp[i+1][(j + x    ) % h] = max(dp[i][j], dp[i+1][(j + x    ) % h] )
        dp[i+1][(j + x - 1) % h] = max(dp[i][j], dp[i+1][(j + x - 1) % h])
    x = 0
    for j in range(h):
        if dp[i+1][j] == -1: # not visit
            continue
        if l <= (j + x    ) % h <= r:
            dp[i+1][(j + x  ) % h] += 1
print(max(dp[n]))