LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@o_chan_t(おー ちゃん)

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

Posted at

問題

要約

  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: 壊れている床の段数

既存投稿一覧ページへのリンク

一覧ページ

解法手順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

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

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で書くメリット

拡張性と再利用性

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()

テスト容易性

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)  # 到達不可能

可読性と保守性の向上

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()

ログとレース用クラス

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")
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?