結果

問題 No.3046 White Tiger vs Monster
ユーザー qwewe
提出日時 2025-05-14 12:59:49
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,596 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 67,596 KB
最終ジャッジ日時 2025-05-14 13:01:10
合計ジャッジ時間 7,504 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 80
権限があれば一括ダウンロードができます

ソースコード

diff # 

# -*- coding: utf-8 -*-
import sys

def solve():
    # Read K, the total number of steps in the staircase.
    K = int(sys.stdin.readline())
    
    # Read N, the number of possible step sizes.
    N = int(sys.stdin.readline())
    
    # Read the N possible step sizes x_1, x_2, ..., x_N.
    # The input format guarantees x_i are sorted and positive.
    x = list(map(int, sys.stdin.readline().split()))

    # Define the modulus.
    MOD = 1000000007

    # Handle the base case K=0. There is one way to reach step 0 (by doing nothing).
    if K == 0:
      print(1)
      return

    # Initialize DP table. dp[k] will store the number of ways to reach step k.
    # The size is K+1 to store values for steps 0 through K.
    dp = [0] * (K + 1)
    
    # Base case: There is 1 way to be at step 0 (the starting point).
    dp[0] = 1
    
    # Filter the step sizes to keep only those that are relevant (<= K).
    # Since the input array x is sorted, we can stop iterating early.
    active_steps = []
    for val in x:
        # We only consider steps that are positive and not larger than K.
        # Input guarantees x_i >= 1.
        if val <= K:
            active_steps.append(val)
        else: 
             # Since x is sorted, any remaining steps will also be > K.
             break

    # If there are no possible steps (e.g., N=0 or all x_i > K),
    # and K > 0, then it's impossible to reach step K.
    if not active_steps:
        # dp[K] is already initialized to 0.
        print(0) 
        return

    # Fill the DP table iteratively.
    # Calculate dp[k] for k from 1 to K.
    for k in range(1, K + 1):
        current_sum = 0
        # To reach step k, we could have taken a final step of size `step`
        # from a previous step `k - step`.
        # Iterate through all possible active step sizes.
        for step in active_steps:
             # Check if the previous step `k - step` is valid (non-negative).
             # This is equivalent to checking if `step <= k`.
             if step <= k:
                 # Add the number of ways to reach step `k - step`.
                 current_sum = (current_sum + dp[k - step]) % MOD
             else: 
                 # Since `active_steps` is sorted, if the current `step` is already > k,
                 # all subsequent steps will also be > k. We can stop checking for this k.
                 break 
        # Store the total number of ways to reach step k.
        dp[k] = current_sum

    # The final answer is the number of ways to reach step K.
    print(dp[K])

# Execute the solve function
solve()
0