CodeIQ 挑戦の記録 : 第80回「今週のアルゴリズム：回数指定のじゃんけん」
CodeIQというサイトで問題に挑戦した記録です。
第80回「今週のアルゴリズム：回数指定のじゃんけん」
問題文を要約すると以下の通り
- 標準入力よりAさん、Bさんそれぞれの持っているコインの枚数、上限の回数が与えられる。
- Aさん、Bさんがじゃんけんをして、勝った方が負けた方からコインを1枚受け取る
- いずれかのコインがなくなるか、上限に達するまでじゃんけんを繰り返した時、いずれかのコインが無くなるパターンが何通りかを解答する。
方針
(1)メモ化再帰によりじゃんけんでコインの枚数が変化するパターンをシミュレートする
題意の通り、じゃんけんで <Aが勝つ> <Bが勝つ> <あいこ> それぞれを試したものが最初に提出したコード。
何も考えず引数を3つ取った再帰で実装したが、少し考えれば2人のどちらが勝つかは、1人のコインの増減にまとめられるので引数は2つにできた。
メモ化は3重のハッシュを用いており、この程度の大きさの入力であれば問題無かったが、安直なコードだと思う。
(2)動的計画法によりシミュレートする
動的計画法を用いて再提出したもの
- 二次元配列dpを用意する（縦軸はじゃんけんの回数0からn、横軸はAのコインの枚数。Bは総数から引けば分かるので無視。0からA+Bの総数）
- 初期値としてAのコインの枚数を示す要素dp[0][枚数]に1を代入。
- 二重ループにて順に （負け）dp[i+1][枚数-1]、（あいこ）dp[i+1][枚数]、（勝ち）dp[i+1][枚数+1] それぞれに dp[i][枚数]の要素を代入する。
- コインの枚数が0またはA+Bの総数に達した場合は、別の変数に代入しておき、最終的にこの変数の値を解答とする。
コードは以下の通り
実行速度はほとんど変わらなかった。
なお、この問題は簡単なシミュレーションであるが、同じアルゴリズムで株取引（信用取引）などをシミュレートして期待値を計算できると思ったので計算してみた。
よければこの記事も御覧ください。
