私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「今週のお題：回数指定のじゃんけん」（CodeIQ）を参照してください。
問題を引用します。
標準入力から「Aのコインの枚数」「Bのコインの枚数」「上限の回数」がコンマ区切りで与えられます。（引用者注：コインは負けた方から勝った方に移動します）
（いずれも0以上の整数とし、上限の回数は最大24回とします。）
上限の回数以下で一方のコインがなくなるパターンが全部で何通りあるかを求め、標準出力にパターン数を出力してください。
Pythonで解答しています。
#!/usr/local/bin/python3
import fileinput
# 1回のじゃんけんの結果の組み合わせ数を保持するdictを作成
# キーは勝ち越し数で、-mx〜-1はBが勝ち越した回数、1〜mxはAが勝ち越した回数。0は引き分け状態
def initCnt(mx):
cnt = {}
for i in range(mx+1):
cnt.update({i:0, (-1*i):0})
return cnt
# じゃんけんをする
# mx 最大勝負回数
# ca Aのコイン
# cb Bのコイン
# return 1〜mx回までの結果のリストを返す
def play(mx, ca, cb):
result = [] # 勝負回数0〜mxまでの結果リスト
cur = initCnt(mx)
if mx == 0 or ca == 0 or cb == 0:
return result
for i in range(1,mx+1):
nxt = initCnt(mx)
if i==1:
nxt[-1] = 1; nxt[0] = 1; nxt[1] = 1
else:
for t in range(i):
e = t; r = t+1; l = t-1 # e：あいこ、r：勝ち、l：負けの加算位置
if t == 0:
nxt[l] += cur[e]; nxt[e] += cur[e]; nxt[r] += cur[e]
else:
if e < cb: # A側
nxt[l] += cur[e]; nxt[e] += cur[e]; nxt[r] += cur[e]
if -e > -1*ca: # B側
nxt[-l] += cur[-e]; nxt[-e] += cur[-e]; nxt[-r] += cur[-e]
cur = nxt
result.append(cur)
return result
# 結果を集計する
def calcResult(result, ca, cb):
s = 0
for r in result:
s += r[cb] + r[-1*ca]
return s
if __name__ == "__main__":
for line in fileinput.input():
if not line.strip():
continue;
ac, bc, mx = list(map(int, line.strip().split(",")))
ret = play(mx,ac, bc)
print(calcResult(ret, ac, bc))
それでは説明してゆきます。このプログラムの本体はplay()関数です。
この問題では1回の勝負毎にコインは負けた側から勝った側に移動します。なので、1回目から勝負回数の上限まで全パターンを試行すれば良いことは明らかです。
そして、n回目の勝負でそれぞれ何枚のコインを持っているかは勝ち負けの順序は関係ありません。例えば3回勝負が終わった時点でAのコインが1枚増えているとした場合、勝-勝-負でも勝-負-勝でも引分-勝-引分でもなんでもよくて、1枚増えているということだけが重要です。
| 回数 | A勝 | 引分 | B勝 | ||||||
|---|---|---|---|---|---|---|---|---|---|
| 4 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 2 | 3 | 2 | 1 | 0 | 0 |
| 3 | 0 | 1 | 3 | 6 | 8 | 6 | 3 | 1 | 0 |
さて、コインの枚数を有限にしたらどうなるかというと、単に枚数が0になった以上の場所には加算しなければよいだけです。そしてコインが0になるというのは負け越し数がコインの枚数に等しくなった場合です。
なので、勝負回数ごとに履歴を残しておいて負け越し数がコインの枚数に当たる列の値を足し合わせれば問題の答えになります。
実際のコードは上記のロジックをプログラムにしています。play()関数で勝負の履歴を作成しています。履歴は1回の勝負ごとの結果を、Aが勝った場合を+1〜最大勝負回数まで、Bが勝った回数を-1〜-最大勝負回数まで、0はトータルイーブンのdictionaryとし、その配列を勝負全体の履歴としています。
initCont()は履歴用の領域を作成するための関数です。
そして勝負回数だけループして結果を作成します（24行目〜38行目）。
実際のコードでは負け越し回数がコイン枚数に達した場合より1回勝ち越しが多いところまで値が入ります。そしてその値はコインを無限に持っているとした場合、正しい値にはなりません。しかし、その部分の値は使用しないので問題はありません。
ループ回数は勝負回数上限までで、この計算はO(n)で完了します。
結果の集計をしているのがcalcResult()関数です。
負け越し数がコインがなくなった場合なので履歴データの相手側（Aならマイナス側、Bならプラス側）に自分が最初持っていたコインの枚数を指定して値を取り出し、合計すれば答えになります。
この問題を解凍したあたり(2016/2/3)では私もこの手の問題に結構慣れてきていて、割とすんなりと解けました。
私は動的計画法で解きましたがメモ化再帰でも同じように解けますし、コードはそちらの方がシンプルになるかもしれません。ただ、メモ化再帰よりも動的計画法の方が若干早いこととデバッグしやすいため、私はメモ化再帰よりも動的計画法の方が好きです。