【競技プログラミング】AtCoder Beginner Contest 261_D問題

# 問題

https://atcoder.jp/contests/abc261/tasks/abc261_d

## 要約

1. 高橋君がN回コイントスを行う。

2. 高橋君はカウンタを持っており、初期値は0。

3. コイントスの結果によって以下のことが起こります：
   - 表が出た場合：カウンタが1増え、Xi円もらう。
   - 裏が出た場合：カウンタが0にリセットされ、お金はもらえない。

4. M種類の連続ボーナスがあり、i番目のボーナスではカウンタの値がCiになるたびにYi円もらえる。

5. 高橋君が最大でいくら稼げるかを求める。

変数情報：
- N: コイントスの回数
- M: 連続ボーナスの種類数
- Xi: i回目のコイントスで表が出た時にもらえる金額
- Ci: i番目の連続ボーナスが発動するカウンタの値
- Yi: i番目の連続ボーナスで得られる金額

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


# アプローチ

動的計画法（DP）を使用して、各コイントスの結果に対する最適な選択を計算する。
DPテーブルを作成し、各状態での最大獲得金額を記録していく。

# 解法手順

1. 入力を受け取り、必要なデータ構造を初期化する。
2. 連続ボーナスの情報を辞書に格納する。
3. DPテーブルを作成する。dp[i][j]は、i回目のコイントスまでで、現在のカウンタがjの時の最大獲得金額を表す。
4. DPテーブルを以下のように更新する：
   - 表が出た場合：dp[i][j] = dp[i-1][j-1] + Xi + ボーナス金額
   - 裏が出た場合：dp[i][0] = max(dp[i-1][k]) (kは0からi-1まで)
5. 全てのコイントスが終了した後、dp[N][j]の最大値を求める。
6. 最大獲得金額を出力する。

# ACコード
```python:ac.py
from collections import defaultdict

def io_func():
    # 入力を受け取る
    n, m = map(int, input().split())  # コイントスの回数とボーナスの種類数
    x = list(map(int, input().split()))  # 各コイントスで得られる金額
    b = defaultdict(int)  # ボーナス情報を格納する辞書
    for _ in range(m):
        c, y = map(int, input().split())
        b[c] = y  # 連続回数cに対するボーナス金額yを格納
    return n, m, x, b

def solve(n, m, x, b):
    # DPテーブルを初期化
    dp = [[0] * (n + 1) for _ in range(n + 1)]  # dp[i][j]: i回目までで連続j回表の時の最大金額

    # DPテーブルを更新
    for i in range(1, n + 1):
        for j in range(1, i + 1):
            # 表が出た場合の更新
            dp[i][j] = dp[i - 1][j - 1] + x[i-1] + b[j]

        # 裏が出た場合の更新
        dp[i][0] = 0
        for j in range(i):
            dp[i][0] = max(dp[i][0], dp[i - 1][j])

    # 最大獲得金額を計算
    ans = 0
    for i in range(n + 1):
        ans = max(ans, dp[n][i])

    return ans

if __name__=="__main__":
    # メイン処理
    n, m, x, b = io_func()  # 入力を受け取る
    result = solve(n, m, x, b)  # 問題を解く
    print(result)  # 結果を出力

########################################################################
# 変数:
# n: コイントスの回数
# m: ボーナスの種類数
# x: 各コイントスで得られる金額のリスト
# b: 連続回数とボーナス金額の対応を格納した辞書
# dp: 動的計画法のテーブル
# ans: 最大獲得金額

# 1. io_func関数:
#    - 標準入力から必要なデータを読み込む
#    - コイントスの回数、ボーナスの種類数、各コイントスの金額、ボーナス情報を取得
# 2. solve関数:
#    - 動的計画法を用いて最大獲得金額を計算
#    - DPテーブルを初期化し、各状態での最大金額を更新
#    - 表が出た場合と裏が出た場合の両方を考慮
#    - 最終的な最大獲得金額を計算
# 3. メイン処理:
#    - io_func関数で入力を受け取る
#    - solve関数で問題を解く
#    - 結果を出力する
```

## オブジェクト指向版1
```python:ac_object.py
from collections import defaultdict
import logging

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
    formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
    
    file_handler = logging.FileHandler('program_trace.log')
    file_handler.setFormatter(formatter)
    logger.addHandler(file_handler)
    
    return logger

class InputReader:
    @staticmethod
    def read_input():
        # 入力を受け取る
        n, m = map(int, input().split())  # コイントスの回数とボーナスの種類数
        x = list(map(int, input().split()))  # 各コイントスで得られる金額
        b = defaultdict(int)  # ボーナス情報を格納する辞書
        for _ in range(m):
            c, y = map(int, input().split())
            b[c] = y  # 連続回数cに対するボーナス金額yを格納
        return n, m, x, b

class CoinTossSolver:
    def __init__(self, n, m, x, b, debug_mode=False):
        self.n = n
        self.m = m
        self.x = x
        self.b = b
        self.logger = setup_logger(debug_mode)

    def solve(self):
        self.logger.debug("動的計画法の計算を開始します")
        # DPテーブルを初期化
        dp = [[0] * (self.n + 1) for _ in range(self.n + 1)]  # dp[i][j]: i回目までで連続j回表の時の最大金額

        # DPテーブルを更新
        for i in range(1, self.n + 1):
            self.logger.debug(f"{i}回目のコイントスの計算を開始")
            for j in range(1, i + 1):
                # 表が出た場合の更新
                dp[i][j] = dp[i - 1][j - 1] + self.x[i-1] + self.b[j]
                self.logger.debug(f"表が出た場合: dp[{i}][{j}] = {dp[i][j]}")

            # 裏が出た場合の更新
            dp[i][0] = 0
            for j in range(i):
                dp[i][0] = max(dp[i][0], dp[i - 1][j])
            self.logger.debug(f"裏が出た場合: dp[{i}][0] = {dp[i][0]}")

        # 最大獲得金額を計算
        ans = max(dp[self.n])
        self.logger.debug(f"最大獲得金額: {ans}")
        return ans

class OutputWriter:
    @staticmethod
    def write_output(result):
        print(result)  # 結果を出力

def main(debug_mode=False):
    # 入力を読み込む
    input_reader = InputReader()
    n, m, x, b = input_reader.read_input()

    # 問題を解く
    solver = CoinTossSolver(n, m, x, b, debug_mode)
    result = solver.solve()

    # 結果を出力する
    output_writer = OutputWriter()
    output_writer.write_output(result)

if __name__ == "__main__":
    main(debug_mode=True)  # デバッグモードをTrueに設定
```

### オブジェクト図
![sequence_diagram.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/65c1cf58-5936-a716-8121-f2d417af9c63.png)




# 数学的帰納法による証明
## 最適解の考え方

任意の i 回目のコイントスにおいて、以下の2つの選択肢がある：
1. 表を出す：dp[i-1][j-1] + x[i-1] + b[j]
2. 裏を出す：max(dp[i-1][k] for k in range(i))

### n=1の場合を考える。

#### dp[1][0]（1回目で裏）:
dp[1][0] = max(0, dp[0][j]) = 0
これは正しい。
なぜなら、1回目で裏が出た場合、獲得金額は0になるため。

#### dp[1][1]（1回目で表）:
dp[1][1] = dp[0][0] + x[0] + b[1] = x[0] + b[1]
これも正しい。
1回目で表が出た場合、x[0]の金額と1回連続の表に対するボーナスb[1]を獲得する。

### 帰納仮定

k回目までのコイントスについて、dp[k][j]（0 ≤ j ≤ k）が正しく計算されていると仮定します。

### 帰納ステップ（k+1回目）

#### 表が出た場合（dp[k+1][j]、1 ≤ j ≤ k+1）

dp[k+1][j] = dp[k][j-1] + x[k] + b[j]

この式が正しいことを示す：
- dp[k][j-1]は、k回目までで連続j-1回表が出た時の最大金額（帰納仮定より正しい）
- x[k]は、k+1回目のコイントスで得られる金額(kは0インデックス)
- b[j]は、連続j回表に対するボーナス

これらを合計することで、k+1回目で表が出て、連続j回表になった場合の最大金額が正しく計算される。

#### 裏が出た場合（dp[k+1][0]）

dp[k+1][0] = max(dp[k][j] for j in range(k+1))

この式が正しいことを示す：
- dp[k][j]（0 ≤ j ≤ k）は、k回目までの各状態での最大金額（帰納仮定より正しい）
- k+1回目で裏が出た場合、連続回数はリセットされるため、k回目までの全ての状態の中から最大値を選ぶ

したがって、この式は k+1 回目で裏が出た場合の最大金額を正しく計算される。

### 結論

数学的帰納法により、すべての i（1 ≤ i ≤ n）について、dp[i][j] が正しく計算されることが証明さた。