AtCoder ABC 129 C - Typical Stairs (Python)

irisruneです。今回不参加でしたがトラブルがあって大変だったみたいですね。

問題

atcoder.jp

当のトラブルがあった問題です。問題自体は最近珍しい気もする典型問題です。

import sys
import numpy as np

MOD = 1000000007

def main():
    n, m = [int(x) for x in input().split()]
    pattern = [1]
    broken = -1
    brokencnt = 0
    if brokencnt < m:
        broken = int(input())
        brokencnt += 1
    for i in range(1, n + 1):
        if i == broken:
            pattern.append(0)
            if brokencnt < m:
                broken = int(input())
                brokencnt += 1
            continue
        if i == 1:
            pattern.append(pattern[i - 1])
        if i > 1:
            pattern.append((pattern[i - 1] + pattern[i - 2]) % MOD)
    print(pattern[n])


main()

アルゴリズム的には典型的なDPで、追加条件として壊れた段については移動できない（=移動方法が0通り）という扱いにするだけです。見た感じ正解者数が少なく見えるのはトラブルの影響…なんですかね。

色々考えるのが面倒になったので処理を行いながら入力を読み込むという手法を取っています。Pythonの配列アクセスにかかる時間を考えると多少速くなるのかもしれないですが、公式解説のコードに比べて（の場合分けが必要など）記述が少し複雑になっている気がします。

雑記

• D問題、E問題はアルゴリズム的には難しくなさそうですが実装に少し時間かかりそうなのと少し忙しいのでまた後ほど。
• 先週Paiza練習問題を扱うと言っていたのは忘れていました。とりあえず今週に何か書く予定です。