AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

JOI難易度6 階段

問題原文

https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day1_20.pdf

問題要旨

 N 段の階段があり、  i 段目の高さは  H_immである。
また、段差の和が  P mm 以下であれば1歩で登ることができる。
 N 段の階段を上りきる通り数を求めよ。また、用いた段が同じ時に同じ上り方とみなす。

  •   1 \leq N \leq 10^{5}
  •  1 \leq P \leq 5 × 10^{8}
  •  sum({H_i}) \leq 5 × 10^{8}

解法

 dp[i\rbrack :=  i 段目に登るための通り数
というdpがとりあえず浮かぶ。
ただし一度に複数段登れることがあるので、どこまで登れるかを見てそれら全てについて遷移を愚直にやっては間に合わない。

毎回どこまで登れるか〜を数えるところで無駄があるので、ここをまとめられないか考える。
配るdpでなく拾うdpに切り替えると、 「どこから登ったことにできるか」と「それらの通り数合計」がまとめて計算できそうに見えて、尺取り法っぽく計算できる。

図を書くのがめんどくさかったので、絵を書いてみました。

f:id:AT274:20200404162044j:plain
配るdp → 拾うdp

f:id:AT274:20200404162135j:plain
尺取り法のイメージ

実装

良い名前が思いつかなくてカス命名をしてしまった。。。

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年前は絶対に不可能だった。