Edit

【pythonでABC179を解説】D - Leaping Tak

問題概要

問題ページ

問題文

一列に並んだ \(N\) マスから成るマス目があり、マスには左から順番に\(1, 2, \ldots, N\) の番号がついています。

このマス目で暮らしている高橋君は、現在マス \(1\) にいて、後述の方法で移動を繰り返してマス \(N\) へ行こうとしています。

\(10\) 以下の整数 \(K\) と、共通部分を持たない \(K\) 個の区間 \([L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]\) が与えられ、これらの区間の和集合を \(S\) とします。ただし、区間 \([l, r]\) は \(l\) 以上 \(r\) 以下の整数の集合を表します。

  • マス \(i\) にいるとき、\(S\) から整数を \(1\) つ選んで (\(d\) とする)、マス \(i + d\) に移動する。ただし、マス目の外に出るような移動を行ってはならない。

高橋君のために、マス \(N\) に行く方法の個数を \(998244353\) で割った余りを求めてください。

制約

  • \(2 \leq N \leq 2 \times 10^5\)
  • \(1 \leq K \leq \min(N, 10)\)
  • \(1 \leq L_i \leq R_i \leq N\)
  • \([L_i, R_i]\) と \([L_j, R_j]\) は共通部分を持たない (\(i \neq j\))
  • 入力はすべて整数である

問題の考察

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 998244353
    n, k = list(map(int, input().rstrip('\n').split()))
    lr = sorted([list(map(int, input().rstrip('\n').split())) for _ in range(k)])
    dp = [0] * n
    ac = [0] * n
    dp[0] += 1
    ac[0] += 1
    for i in range(1, n):
        for l, r in lr:
            if i - l >= 0:
                t = ac[i-l] - (ac[i-r-1] if i - r - 1 >= 0 else 0)
                dp[i] += t
            else:
                break
        ac[i] += ac[i-1] + dp[i]
        ac[i] %= mod
        dp[i] %= mod
    print(dp[-1])


if __name__ == '__main__':
    solve()

プログラミング

-Edit
-