CodeIQ：取られたら取り返す！

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「取られたら取り返す！」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
卓球では11点先取、バレーボールでは25点先取で1セットを取るようなルールがあります。
ただ、この得点よりも1点少ない得点以上の得点で同点となると「デュース」と呼ばれることがあり、その後は2点差を付けるまで続けられます。
（卓球やバドミントンにはデュースという言葉はありませんが、同様に進められます。）

A と B がn 点先取の試合を行ったとき、それぞれの点数が a 対 b になるまでの点数の推移を考えます。
例えば、n = 3, a = 4, b = 2 のとき、点数の推移は以下の6通りがあります。
（下記の記号は点数を取った側を表すものとします。）

(1) A -> A -> B -> B -> A -> A
(2) A -> B -> A -> B -> A -> A
(3) A -> B -> B -> A -> A -> A
(4) B -> A -> A -> B -> A -> A
(5) B -> A -> B -> A -> A -> A
(6) B -> B -> A -> A -> A -> A

このとき、以下のように点数が推移することはありません。
（途中で3点を先取してしまい、セットが終了するため）
A -> A -> B -> A -> B -> A

標準入力から n, a, b がスペース区切りで与えられるとき、点数の推移が何通りあるかを求め、標準出力に出力してください。
なお、n, a, b はいずれも0以上25以下の整数とします。

【入出力サンプル】
標準入力
3 4 2

標準出力
6

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

$Memo = {}

def solve(n,a,b,pa,pb)
	return $Memo[[pa,pb]] if $Memo[[pa,pb]] != nil

	if (a == pa) && (b == pb) then
		return 1
	else
		if ((pa == n) && (pb <= n-2)) || ((pb == n) && (pa <= n-2)) then return 0
		elsif ((pa > n) && (pa-pb >= 2)) || ((pb > n) && (pb-pa >= 2)) then return 0
		elsif (pa > a) || (pb > b) then return 0
		end
	end

	ret = 0
	ret += solve(n,a,b,pa+1,pb)
	ret += solve(n,a,b,pa,pb+1)

	$Memo[[pa,pb]] = ret

	return ret
end

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

	n,a,b = line.split.map{|v| v.to_i}
	p solve(n,a,b,0,0)
end

解説

再びメモ化再帰の問題です。

考え方

デュースのことはとりあえず置いておいて、得点パターンを列挙するのは再帰で簡単に実装できます（AかBのどちらかが得点したとして同じことを繰り返せば良いので）。

正しいパターンになるのはA、Bの得点が入力値に等しくなった時です。
間違ったパターンになるのはAかBの得点が入力値を超えてしまった時というのは明らかですが、ここでデュースのことを考えなければなりません。

デュースになっても正しいパターンの条件は変わらずA、Bの得点が入力値に等しくなった時です。
なので、デュースになるはずなのに条件を満たせない場合をエラーにすれば良いわけです。
まず、一方の点数が入力値nに等しい時、その時点で負けている方の得点が2点以上少ない場合、デュースにならず終わるのでダメです。
そして、デュースに突入した時（一方の点数がnより大きくなった時）に、AかBの得点が入力値a、bに達していないにも関わらず2点差になった時もダメです。

以上が終了条件になるのでこれをコード化します。
あとは高速化のためにメモ化すれば大丈夫です。

main

入力値を数値にしてsolve()に渡し、結果を印字します。

solve(m,n)

考え方に書いた通りの実装です。
引数に工夫があり、n,a,bは入力値をそのままずっと保持し続け、pa,pbがそれぞれABの得点で、0からカウントアップします。n,a,bをカウントダウンしながら再帰処理すれば良さそうに思えますが、それだとデュースの処理をうまく扱えないためこのようにしました。
$Memoは高速化のためのメモで[pa,pb]をキーとしてその得点からのパターン数を値にして計算量を減らしています。

雑感

メモ化再帰でOKというのはすぐに思いつきましたが、実装の説明でも書いた通りカウントダウンするとデュースの処理がうまく行かず少し手間取りました。