CodeIQ：カウントゲームで先手が勝つのは何通り？

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「カウントゲームで先手が勝つのは何通り？」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
某SNSにおいて、チャットでAIと対戦できる「カウントゲーム」があります。
ある数からスタートし、交互に最大3つまでの数をカウントダウンしていき、最後に「0」を言った方が負け、というゲームです。

例えば、AとBが対戦し、Aが15からスタートして、以下のように進むとBの負けとなります。
A「15, 14」
B「13, 12」
A「11, 10, 9」
B「8」
A「7」
B「6, 5, 4」
A「3, 2, 1」
B「0」

なお、自分から負けるために、「1, 0」のように言うことはないものとします。
（相手が「1」まで言って、最後に「0」だけを言って負ける）

標準入力から整数 n が与えられたとき、Aが n からスタートし、最後にBが「0」を言うパターンが何通りあるか求め、標準出力に出力してください。
なお、n は1≦n≦50を満たすものとします。

例えば、n = 5のとき、以下の7通りがあります。

(1) (2) (3) (4) (5) (6) (7)
A「5」
B「4」
A「3」
B「2」
A「1」
B「0」
 A「5」
B「4」
A「3, 2, 1」
B「0」
 A「5」
B「4, 3」
A「2, 1」
B「0」
 A「5」
B「4, 3, 2」
A「1」
B「0」
 A「5, 4」
B「3」
A「2, 1」
B「0」
 A「5, 4」
B「3, 2」
A「1」
B「0」
 A「5, 4, 3」
B「2」
A「1」
B「0」

【入出力サンプル】
標準入力
5

標準出力
7

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

$Memo = {}

def solve(n, pl)
	return $Memo[[n,pl]] if $Memo[[n,pl]] != nil
	if n == 0 then return (pl ? 0 : 1)
	elsif n < 0 then return 0
	end

	ret = 0
	for i in 1..3
		ret += solve(n-i, !pl)
	end

	$Memo[[n,pl]] = ret
	return ret
end

# main
while line = gets
	line.strip!
	next if line.empty?

	p solve(line.to_i, true)
end

解説

分かりやすいメモ化再起の問題です。

考え方

1回の操作は入力値から1〜3を引いて相手に渡す、という操作です。
これは単純に再帰で実装できます。
終了条件は渡された値が0以下の時です。
渡された値が0の時にプレイヤーが先手なら0、後手なら1を返します。渡された値が負数の場合は不正なので常に0を返します。
この返却値を全て足し上げれば答えになります。

あとは高速化のためメモ化するのですが、これは渡された値とその時のプレイヤーをキーとし、その時の結果のカウントを値とすればOKです。

main

入力値を数値にしてsolve()に渡し、結果を印字します。
solve()の第二引数はプレイヤーでtrueが先手、falseが後手を表します。

solve(m,pl)

考え方の通りに実装します。
6行目はメモに結果があった場合でメモの値を返します。
7〜9行目は終了条件です。7行目はn=0の場合で、プレイヤーが先手（true）なら0、後手（false）なら1を返します。8行目はn<0の場合で0を返します。

12〜14行目でnを1〜3減らして相手に手番を渡します。
retは先手が勝つパターン数の合計です。

雑感

ちょっとしたポイントが複数の値を宣言できる時に0を宣言しない処理の扱いでしょうか。
真面目にやると残り数が3以下になった時は宣言する数の上限を変更するのですが、引数nに負数を認めてその場合は0を返すこととし、n=0の時に終了をチェックすることで処理を簡単にできます。
分かりやすい問題でサクッとできました。