JOI難易度6 階段
問題原文
https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day1_20.pdf
問題要旨
段の階段があり、 段目の高さは mmである。
また、段差の和が mm 以下であれば1歩で登ることができる。
段の階段を上りきる通り数を求めよ。また、用いた段が同じ時に同じ上り方とみなす。
解法
段目に登るための通り数
というdpがとりあえず浮かぶ。
ただし一度に複数段登れることがあるので、どこまで登れるかを見てそれら全てについて遷移を愚直にやっては間に合わない。
毎回どこまで登れるか〜を数えるところで無駄があるので、ここをまとめられないか考える。
配るdpでなく拾うdpに切り替えると、 「どこから登ったことにできるか」と「それらの通り数合計」がまとめて計算できそうに見えて、尺取り法っぽく計算できる。
図を書くのがめんどくさかったので、絵を書いてみました。
実装
良い名前が思いつかなくてカス命名をしてしまった。。。
import sys my_input = sys.stdin.readline N, P = map(int, my_input().split()) H = [int(my_input()) for _ in range(N)] MOD = 1234567 # dp[i] := i段目まで登る通り数 dp = [0] * (N + 1) dp[0] = 1 # 左マーカー, 登ろうとしている段の高さ総和カウント, 加算される通り数 l, S, V = 0, 0, 1 for i in range(1, N + 1): S += H[i - 1] while (S > P) and (l < N): S -= H[l] V -= dp[l] l += 1 dp[i] += V dp[i] %= MOD V += dp[i] V %= MOD print(dp[-1] % MOD)
感想
こういうの解けるようになると成長したなぁって思います。
1年前は絶対に不可能だった。