【競技プログラミング】AtCoder Beginner Contest 129_C問題

# 問題
https://atcoder.jp/contests/abc129/tasks/abc129_c

## 要約
1. N段の階段がある。
2. 高橋君は現在、0段目（上り口）にいる。
3. 高橋君は1歩で1段か2段上ることができる。
4. a1, a2, a3, ..., am段目の床は壊れており、踏んではいけない。
5. 最上段（N段目）にたどり着くまでの移動方法の数を求める。
6. 求めた総数を1,000,000,007で割った余りを出力する。

- N: 階段の総段数
- M: 壊れている床の数
- a1, a2, a3, ..., am: 壊れている床の段数


# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)


# 解法手順1

動的計画法を用いて、各段に到達する方法の数を計算し、最終的にN段目に到達する方法の総数を求める。
再帰的なアプローチを採用し、メモ化を行うことで計算の効率化を図る。

1. 入力値N（階段の総段数）とM（壊れている床の数）を受け取る。
2. 壊れている床の段数を集合aに格納する。
3. メモ化のための辞書memoを用意する。
4. 再帰関数dp(k)を定義する。この関数はk段目に到達する方法の数を返す。
5. dp(k)内で以下の処理を行う：
   - kがmemoに存在する場合、その値を返す（メモ化された結果の利用）。
   - kが壊れている床の場合、0を返す。
   - kが0未満の場合、0を返す（範囲外）。
   - kが0の場合、1を返す（初期状態）。
   - それ以外の場合、dp(k-1) + dp(k-2)を計算する（1段上る場合と2段上る場合の和）。
   - 計算結果を1,000,000,007で割った余りを求める。
   - 結果をmemoに保存し、返す。
6. dp(N)を呼び出し、結果を出力する。


# ACコード1
```python:ac.py
import sys

# 再帰の深さ制限を設定
sys.setrecursionlimit(10**6)

def io_func():
    # 入力値N（階段の総段数）とM（壊れている床の数）を受け取る
    n, m = map(int, input().split())
    
    # 壊れている床の段数を集合aに格納する
    a = set()
    for _ in range(m):
        ai = int(input())
        a.add(ai)
    
    return n, m, a

def solve(n, m, a):
    # 余りを計算するための定数
    MOD = 10**9 + 7
    
    # メモ化のための辞書
    memo = {}
    
    def dp(k):
        # kがmemoに存在する場合、その値を返す（メモ化された結果の利用）
        if k in memo:
            return memo[k]
        
        # kが壊れている床の場合、0を返す
        if k in a:
            return 0
        
        # kが0未満の場合、0を返す（範囲外）
        if k < 0:
            return 0
        
        # kが0の場合、1を返す（初期状態）
        if k == 0:
            return 1
        
        # dp(k-1) + dp(k-2)を計算する（1段上る場合と2段上る場合の和）
        res = dp(k-1) + dp(k-2)
        
        # 計算結果を1,000,000,007で割った余りを求める
        res %= MOD
        
        # 結果をmemoに保存し、返す
        memo[k] = res
        return res
    
    # dp(N)を呼び出し、結果を返す
    return dp(n)

# 入力を受け取る
n, m, a = io_func()

# 結果を計算し、出力する
print(solve(n, m, a))

###
# n: 階段の総段数
# m: 壊れている床の数
# a: 壊れている床の段数を格納した集合
# MOD: 余りを計算するための定数 (1,000,000,007)
# memo: メモ化のための辞書
# k: 現在の段数（dp関数の引数）
# res: 各段に到達する方法の数

# 1. io_func関数: 標準入力から必要なデータを読み込む
# 2. solve関数: メインの処理を行う
#    - dp関数: 動的計画法による再帰計算を行う
#      - メモ化を利用して計算の効率化を図る
#      - 壊れている床、範囲外、初期状態の処理
#      - 1段上る場合と2段上る場合の和を計算
#      - 結果を1,000,000,007で割った余りを求める
# 3. 入力を受け取り、solve関数を呼び出して結果を出力する

```
## オブジェクト指向版1
```python:ac_object.py
import sys
from abc import ABC, abstractmethod
from typing import Set, Dict

# 再帰の深さ制限を設定
sys.setrecursionlimit(10**6)

# 入力インターフェース（単一責任の原則、インターフェース分離の原則）
class InputReader(ABC):
    @abstractmethod
    def read_input(self) -> tuple:
        pass

# 標準入力からの読み込みクラス（開放閉鎖の原則）
class StandardInputReader(InputReader):
    def read_input(self) -> tuple:
        # 入力値N（階段の総段数）とM（壊れている床の数）を受け取る
        n, m = map(int, input().split())
        
        # 壊れている床の段数を集合aに格納する
        a = set()
        for _ in range(m):
            ai = int(input())
            a.add(ai)
        
        return n, m, a

# ソルバーインターフェース（単一責任の原則、インターフェース分離の原則）
class Solver(ABC):
    @abstractmethod
    def solve(self, n: int, m: int, a: Set[int]) -> int:
        pass

# 動的計画法を用いたソルバークラス（開放閉鎖の原則）
class DPSolver(Solver):
    def __init__(self):
        self.MOD = 10**9 + 7
        self.memo: Dict[int, int] = {}

    def solve(self, n: int, m: int, a: Set[int]) -> int:
        return self._dp(n, a)

    def _dp(self, k: int, a: Set[int]) -> int:
        # kがmemoに存在する場合、その値を返す（メモ化された結果の利用）
        if k in self.memo:
            return self.memo[k]
        
        # kが壊れている床の場合、0を返す
        if k in a:
            return 0
        
        # kが0未満の場合、0を返す（範囲外）
        if k < 0:
            return 0
        
        # kが0の場合、1を返す（初期状態）
        if k == 0:
            return 1
        
        # dp(k-1) + dp(k-2)を計算する（1段上る場合と2段上る場合の和）
        res = self._dp(k-1, a) + self._dp(k-2, a)
        
        # 計算結果を1,000,000,007で割った余りを求める
        res %= self.MOD
        
        # 結果をmemoに保存し、返す
        self.memo[k] = res
        return res

# メイン処理クラス（依存性逆転の原則）
class StairClimber:
    def __init__(self, input_reader: InputReader, solver: Solver):
        self.input_reader = input_reader
        self.solver = solver

    def run(self):
        # 入力を受け取る
        n, m, a = self.input_reader.read_input()
        
        # 結果を計算し、出力する
        result = self.solver.solve(n, m, a)
        print(result)

# メイン処理
if __name__ == "__main__":
    input_reader = StandardInputReader()
    solver = DPSolver()
    stair_climber = StairClimber(input_reader, solver)
    stair_climber.run()

###
# n: 階段の総段数
# m: 壊れている床の数
# a: 壊れている床の段数を格納した集合
# MOD: 余りを計算するための定数 (1,000,000,007)
# memo: メモ化のための辞書
# k: 現在の段数（_dp関数の引数）
# res: 各段に到達する方法の数

# 1. InputReader: 入力を読み込むためのインターフェース
# 2. StandardInputReader: 標準入力から必要なデータを読み込むクラス
# 3. Solver: 問題を解くためのインターフェース
# 4. DPSolver: 動的計画法を用いて問題を解くクラス
#    - _dp: 動的計画法による再帰計算を行うメソッド
#      - メモ化を利用して計算の効率化を図る
#      - 壊れている床、範囲外、初期状態の処理
#      - 1段上る場合と2段上る場合の和を計算
#      - 結果を1,000,000,007で割った余りを求める
# 5. StairClimber: メイン処理を行うクラス
#    - 入力の読み込みとソルバーの実行を管理

```

### オブジェクト指向版1で書くメリット
#### 拡張性と再利用性
```python:ac_object.py
import logging

class LoggingStairClimber(StairClimber):
   def __init__(self, input_reader: InputReader, solver: Solver):
       super().__init__(input_reader, solver)
       self.logger = logging.getLogger(__name__)

   def run(self):
       self.logger.info("Starting stair climbing calculation")
       n, m, a = self.input_reader.read_input()
       self.logger.debug(f"Input: n={n}, m={m}, a={a}")
       result = self.solver.solve(n, m, a)
       self.logger.info(f"Calculation result: {result}")
       print(result)

# 使用例
logging.basicConfig(level=logging.DEBUG)
input_reader = StandardInputReader()
solver = DPSolver()
stair_climber = LoggingStairClimber(input_reader, solver)
stair_climber.run()

```

#### テスト容易性
```python:ac_object.py
import unittest

class TestDPSolver(unittest.TestCase):
   def setUp(self):
       self.solver = DPSolver()

   def test_solve_simple_case(self):
       n, m, a = 6, 1, {3}
       result = self.solver.solve(n, m, a)
       self.assertEqual(result, 4)  # 入力例1

   def test_solve_no_broken_steps(self):
       n, m, a = 5, 0, set()
       result = self.solver.solve(n, m, a)
       self.assertEqual(result, 8) 

   def test_solve_all_steps_broken(self):
       n, m, a = 5, 5, {1, 2, 3, 4, 5}
       result = self.solver.solve(n, m, a)
       self.assertEqual(result, 0)  # 到達不可能
```

#### 可読性と保守性の向上
```python:ac_object.py
class FileInputReader(InputReader):
    def __init__(self, filename):
        self.filename = filename

    def read_input(self) -> tuple:
        with open(self.filename, 'r') as f:
            n, m = map(int, f.readline().split())
            a = set(int(f.readline()) for _ in range(m))
        return n, m, a

# 使用例
file_reader = FileInputReader("input.txt")
solver = DPSolver()
stair_climber = StairClimber(file_reader, solver)
stair_climber.run()
```

#### ログとレース用クラス
```python:ac_object.py
import os
from typing import Dict, Set

class DPSolverWithLogging(Solver):
    def __init__(self, log_file: str = "dp_log.txt"):
        self.MOD = 10**9 + 7
        self.memo: Dict[int, int] = {}
        self.log_file = log_file
        # ログファイルを初期化
        with open(self.log_file, 'w') as f:
            f.write("動的計画法ソルバーのログ\n")
            f.write("====================\n\n")

    def solve(self, n: int, m: int, a: Set[int]) -> int:
        result = self._dp(n, a)
        self._log(f"最終結果: {result}")
        return result

    def _dp(self, k: int, a: Set[int]) -> int:
        self._log(f"k = {k} の計算を開始")

        if k in self.memo:
            self._log(f"  k = {k} の結果はメモ化済み: {self.memo[k]}")
            return self.memo[k]
        
        if k in a:
            self._log(f"  k = {k} は壊れている床なので、0を返します")
            return 0
        
        if k < 0:
            self._log(f"  k = {k} は範囲外なので、0を返します")
            return 0
        
        if k == 0:
            self._log(f"  k = 0 なので、1を返します")
            return 1
        
        res = self._dp(k-1, a) + self._dp(k-2, a)
        res %= self.MOD
        
        self.memo[k] = res
        self._log(f"  k = {k} の計算結果: {res}")
        return res

    def _log(self, message: str):
        with open(self.log_file, 'a') as f:
            f.write(message + "\n")
```