問題
要約
-
高橋君がN回コイントスを行う。
-
高橋君はカウンタを持っており、初期値は0。
-
コイントスの結果によって以下のことが起こります：
- 表が出た場合：カウンタが1増え、Xi円もらう。
- 裏が出た場合：カウンタが0にリセットされ、お金はもらえない。
-
M種類の連続ボーナスがあり、i番目のボーナスではカウンタの値がCiになるたびにYi円もらえる。
-
高橋君が最大でいくら稼げるかを求める。
変数情報：
- N: コイントスの回数
- M: 連続ボーナスの種類数
- Xi: i回目のコイントスで表が出た時にもらえる金額
- Ci: i番目の連続ボーナスが発動するカウンタの値
- Yi: i番目の連続ボーナスで得られる金額
既存投稿一覧ページへのリンク
アプローチ
動的計画法（DP）を使用して、各コイントスの結果に対する最適な選択を計算する。
DPテーブルを作成し、各状態での最大獲得金額を記録していく。
解法手順
- 入力を受け取り、必要なデータ構造を初期化する。
- 連続ボーナスの情報を辞書に格納する。
- DPテーブルを作成する。dp[i][j]は、i回目のコイントスまでで、現在のカウンタがjの時の最大獲得金額を表す。
- DPテーブルを以下のように更新する：
- 表が出た場合：dp[i][j] = dp[i-1][j-1] + Xi + ボーナス金額
- 裏が出た場合：dp[i][0] = max(dp[i-1][k]) (kは0からi-1まで)
- 全てのコイントスが終了した後、dp[N][j]の最大値を求める。
- 最大獲得金額を出力する。
ACコード
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関数で問題を解く
# - 結果を出力する
数学的帰納法による証明
最適解の考え方
任意の i 回目のコイントスにおいて、以下の2つの選択肢がある：
- 表を出す：dp[i-1][j-1] + x[i-1] + b[j]
- 裏を出す：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] が正しく計算されることが証明さた。