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

問題

アプローチ

動的計画法と再帰を組み合わせた方法を用いて、期待値を計算する。
各状態（金貨、銀貨、銅貨の枚数の組み合わせ）から終了条件までの期待値を再帰的に計算し、メモ化を行う。

解法手順

1. 入力として金貨A枚、銀貨B枚、銅貨C枚を受け取る。

2. 再帰関数 dfs(x, y, z) を定義する。この関数は現在の状態（金貨x枚、銀貨y枚、銅貨z枚）から終了条件までの操作回数の期待値を返す。

3. dfs 関数内で以下の処理を行う：

   • 終了条件（x=100 または y=100 または z=100）をチェックし、満たされていれば0を返す。
   • 現在の硬貨の総数 s を計算する（s = x + y + z）。
   • 各硬貨を選ぶ確率を計算し、次の状態の期待値を再帰的に呼び出す。
   • 期待値の計算式：p = dfs(x+1,y,z)(x/s) + dfs(x,y+1,z)(y/s) + dfs(x,y,z+1)*(z/s)
   • 現在の操作（+1）と次の状態からの期待値（p）の和を返す。

4. functools.cache デコレータを使用して、dfs 関数の結果をメモ化する。

5. 初期状態 dfs(A, B, C) を呼び出し、結果を出力する。

ACコード

ac.py

import functools

# 2. & 4. 再帰関数 dfs を定義し、メモ化を行う
@functools.cache
def dfs(x, y, z):
    # 3. dfs 関数内の処理
    # 終了条件をチェック
    if x == 100 or y == 100 or z == 100:
        return 0
    
    # 現在の硬貨の総数を計算
    s = x + y + z
    
    # 期待値を計算
    p = (
        dfs(x+1, y, z) * (x/s) +  # 金貨を選んだ場合
        dfs(x, y+1, z) * (y/s) +  # 銀貨を選んだ場合
        dfs(x, y, z+1) * (z/s)    # 銅貨を選んだ場合
    )
    
    # 現在の操作（+1）と次の状態からの期待値（p）の和を返す
    return 1 + p

if __name__=="__main__":
    # 1. 入力を受け取る
    A, B, C = map(int, input().split())
    # 5. 初期状態で dfs を呼び出し、結果を出力
    result = dfs(A, B, C)
    print(result)

一覧ページへのリンク

一覧ページ