読者です 読者をやめる 読者になる 読者になる

CodeIQ 挑戦の記録 : 第80回「今週のアルゴリズム:回数指定のじゃんけん」

CodeIQ

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の総数に達した場合は、別の変数に代入しておき、最終的にこの変数の値を解答とする。

コードは以下の通り

実行速度はほとんど変わらなかった。
なお、この問題は簡単なシミュレーションであるが、同じアルゴリズムで株取引(信用取引)などをシミュレートして期待値を計算できると思ったので計算してみた。
よければこの記事も御覧ください。

t.co