問題
D – サプリメント
回答
ちょっと手も足も出なかった感じ。
30点回答
そもそも dp の配列をどう作るのかすら分からなかった。
スライドや解説動画をじっくり眺めます。
AtCoder Beginner Contest 017 解説 from AtCoder Inc.
AtCoder Beginner Contest 017 解説配信
dp の配列の作り方が分かっても、うまいことコードにできなかった。
私と同じように30点回答がコードに落とし込めない場合は、先にしゃくとり法の考え方とコードへの落とし方を理解した方が吉です。
N, M = map(int, input().split())
f = [int(input()) for _ in range(N)]
MOD = 10**9 + 7
# dp[i]=ある日の終了時点でi番目のサプリメントまでを摂取する組み合わせ数)
# dp[i+1]=(dp[i]+ ... +dp[i-j])（i-jは同じ味のサプリがでない最大の範囲）
dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
s = set([f[0]])
right = 1
left = 0
while right < N:
if f[right] in s:
s.remove(f[left])
left += 1
else:
s.add(f[right])
dp[right+1] = sum(dp[left:right+1]) % MOD
right += 1
print(dp[N])
100点回答
しゃくとり法を使います。
しゃくとり法とは、ある配列が与えられたときに、「その配列の区間で(配列の連続する部分列) で、とある条件を満たすような区間」を求める時に使います。
「区間」が「尺取り虫」という伸び縮みしながら進む虫に例えられており、尺取虫が配列を先頭から最後まで条件を満たすように伸び縮みしながら進んでいくようなイメージです。
しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ
この問題の解説は以下が大変分かりやすかったです。
N, M = map(int, input().split())
f = [int(input()) for _ in range(N)]
MOD = 10**9 + 7
# dp[i]=ある日の終了時点でi番目のサプリメントまでを摂取する組み合わせ数)
# dp[i+1]=(dp[i]+ ... +dp[i-j])（i-jは同じ味のサプリがでない最大の範囲）
dp = [0] * (N+1)
dp[0] = 1
# 現在の区間で fi を使用している場合にTrue
using = [False] * (M+1)
# 現在の区間の左右のインデックス
right = 0
left = 0
# 現在の区間の累積和
cum_sum = dp[0]
for r in range(N):
# 現在の区間で f[r] を使っている場合は左端を移動。
while using[f[right]]:
using[f[left]] = False
cum_sum -= dp[left]
cum_sum %= MOD
left += 1
dp[right+1] = cum_sum
# 右端を移動
cum_sum += dp[right+1]
cum_sum %= MOD
using[f[right]] = True
right += 1
print(dp[N])