CodeIQ:クライマックスシリーズの勝敗パターンは何通り?

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「クライマックスシリーズの勝敗パターンは何通り?」(CodeIQ)を参照してください。

問題の概要

問題を引用します。
いよいよプロ野球の「クライマックスシリーズ」が始まります。
ファーストステージ、ファイナルステージが行われ、さらに日本シリーズまで日本一を決める戦いが続きます。

【ファーストステージ】
セ・リーグ、パ・リーグともに各リーグの2位と3位の球団が対戦し、3試合制で行われます。
ただし、「どちらかの球団が2勝した」もしくは「2位球団が1勝1分」の場合には2試合で終了します。
3試合終了時点で「1勝1敗1分」「0勝0敗3分」のように勝敗が同じ場合は、2位球団が勝者となります。

【ファイナルステージ】
セ・リーグ、パ・リーグともに各リーグの1位とファーストステージの勝者が対戦し、6試合制で行われます。
1位の球団には先に1勝が与えられ、先に4勝したチームが日本シリーズに進出します。
ファーストステージ同様、6試合終了時点で同じ勝ち数になった場合は、1位球団が勝者となります。
また、6試合が行われる前でも進出が決定した時点で終了し、残りの試合は行われません。

【日本シリーズ】
どちらかが4勝するまで行われます。
このため、引き分けが入ると7試合で終わらない場合もあります。

標準入力から合計の試合数が与えられるとき、その勝敗パターンが何通りあるか求め、標準出力に出力してください。
(あくまでも勝敗パターンのみを考え、勝ち残ったチームは考えないものにします。)
なお、入力される試合数は14以上30以下の整数とします。

例えば、合計14試合のとき、以下のそれぞれ以下のパターンがあり、全部で512通りです。
(ファーストステージがセ・リーグ、パ・リーグともに2試合ずつ行われ、それぞれ以下の4通り。
 ファイナルステージはセ・リーグ、パ・リーグともに3試合ずつ行われ、それぞれ以下の4通り。
 日本シリーズは4試合で2通りのため、4×4×4×4×2=512)

以下の表で、〇は勝ち、×は負け、△は引き分けとします。

ファーストステージ
パターン 球団 1試合目 2試合目 3試合目
1 リーグ2位 なし
リーグ3位 × × なし
2 リーグ2位 なし
リーグ3位 × なし
3 リーグ2位 なし
リーグ3位 × なし
4 リーグ2位 × × なし
リーグ3位 なし

ファイナルステージ
パターン 球団 (0試合目) 1試合目 2試合目 3試合目 4試合目 5試合目 6試合目
1 リーグ1位 (〇) なし なし なし
ファーストステージ勝者 (×) × × × なし なし なし
2 リーグ1位 (〇) なし なし なし
ファーストステージ勝者 (×) × × なし なし なし
3 リーグ1位 (〇) なし なし なし
ファーストステージ勝者 (×) × × なし なし なし
4 リーグ1位 (〇) なし なし なし
ファーストステージ勝者 (×) × × なし なし なし

日本シリーズ
パターン 球団 1試合目 2試合目 3試合目 4試合目 5試合目 6試合目 7試合目
1 セ・リーグ勝者 なし なし なし
パ・リーグ勝者 × × × × なし なし なし
2 セ・リーグ勝者 × × × × なし なし なし
パ・リーグ勝者 なし なし なし

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

標準出力
512

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

PTN_1 = {2=>4, 3=>15}
PTN_F = {3=>4, 4=>20, 5=>72, 6=>225}
PTN_JP = {4=>2, 5=>16, 6=>80, 7=>320, 8=>1050, 9=>2912, 10=>7056,
          11=>15360, 12=>30690, 13=>57200, 14=>100672, 15=>168896,
          16=>272090, 17=>423360, 18=>639200, 19=>940032, 20=>1350786}

def solve(n)
	x1_c = n - (2 + 3 + 3 + 4)
	st1_c = (x1_c > 3) ? 3 : x1_c

	ret = 0
	for i1 in 2..st1_c
		x1_p = n - (i1 + 3 + 3 + 4)
		st1_p = (x1_p > 3) ? 3 : x1_p

		for i2 in 2..st1_p
			x2_c = n - (i1 + i2 + 3 + 4)
			st2_c = (x2_c > 6) ? 6 : x2_c

			for j1 in 3..st2_c
				x2_p = n - (i1 + i2 + j1 + 4)
				st2_p = (x2_p > 6) ? 6 : x2_p

				for j2 in 3..st2_p
					x3 = n - (i1 + i2 + j1 + j2)
					r = PTN_1[i1] * PTN_1[i2] * PTN_F[j1] * PTN_F[j2] * PTN_JP[x3]
#					printf("%d, %d, %d, %d, %d, r=%d\n", i1, i2, j1, j2, x3, r)
					ret += r
				end
			end
		end
	end

	return ret
end

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

	p solve(line.to_i)
end

解説

答えをみてから答えだけをプログラミングしたのではなく、全入力パターンに対して答えを出せますが、完全なイカサマコードです。

考え方

まず、全体のパターン数は
セ・リーグの1stステージのパターン数×パ・リーグの1stステージのパターン数×セ・リーグのファイナルステージのパターン数×パ・リーグのファイナルステージのパターン数×日本シリーズのパターン数
です。

問題の試合数は最小の試合数なのでわかりにくいですが、1試合増やすと試合数のパターンは、
3試合*2試合*3試合*3試合*4試合
2試合*3試合*3試合*3試合*4試合
2試合*2試合*4試合*3試合*4試合
2試合*2試合*3試合*4試合*4試合
2試合*2試合*3試合*3試合*5試合
のパターン数の合計になります。

つまり、1stステージは2以上3以下、ファイナルステージは3以上6以下、日本シリーズは4試合以上で、かつ、1stステージとファイナルステージは残りの試合数が足りなくならない範囲の試合数でパターン数を求めれば良いわけです。

しかし、私は各ステージのパターン数を求めると時間が間に合わなくなったので、各ステージのパターン数をあらかじめ計算してしまい、その結果から答えを求めています。

1st、ファイナルステージのパターン数

これらのステージのパターン数は次のコードで求めています。
#!/usr/bin/ruby

$Memo = {}

def stage(rest, a, b, ptn)
	if rest != 0 then
		if (a >= (b+rest)) || ((a+rest) < b)
			printf("rest=%d, a=%d, b=%d, ptn=%s\n", rest, a, b, ptn.to_s)
			$Memo[rest] = 0 if $Memo[rest] == nil
			$Memo[rest] += 1
			return
		end
	else
		printf("rest=%d, a=%d, b=%d, ptn=%s\n", rest, a, b, ptn.to_s)
		$Memo[rest] = 0 if $Memo[rest] == nil
		$Memo[rest] += 1
		return
	end

	stage(rest-1, a+1, b, ptn + ['a'])
	stage(rest-1, a, b+1, ptn + ['b'])
	stage(rest-1, a, b, ptn + ['-'])
end

#stage(3, 0, 0, [])
#p $Memo

stage(6, 1, 0, [])
p $Memo

stage(rest, a, b, ptn)の引数は、
rest: 最大試合数。
a: 優先順位の高いチームの勝ち数。
b: 優先順位の低いチームの勝ち数。
ptn: デバッグ用に勝ちチームの配列。引き分けは'-'。
です。
結果は{残り試合数=>パターン数}で印字されます。

25〜26行目は1stステージのパターン、28〜29行目はファイナルステージのパターンを求めます。

日本シリーズのパターン数

日本シリーズのパターン数は次のコードで求めています。
#!/usr/bin/ruby

$MemoJS = {}

def japanSerise(rest, cw, pw)
	if (cw == 4) || (pw == 4) then
		$MemoJS[rest] = 0 if $MemoJS[rest] == nil
		$MemoJS[rest] += 1
		return
	elsif rest == 0
		return
	end

	japanSerise(rest-1, cw+1, pw)
	japanSerise(rest-1, cw, pw+1)
	japanSerise(rest-1, cw, pw)
end

# main
japanSerise(20, 0, 0)
p $MemoJS

stage(rest, a, b, ptn)の引数は、
rest: 最大試合数。
cw: セ・リーグの勝ち数。
pw: パ・リーグの勝ち数。
です。
結果は{残り試合数=>パターン数}で印字されます。

main

入力値を数値にしてsolve()に渡し、結果を印字します。
定数PTN_1、PTN_F、PTN_JPは上記のプログラムで求めたものを{試合数=>パターン数}の形に変えたものです。

solve(m, n)

考え方の通りにパターン数を計算します。
1stステージとファイナルステージには試合数の上限があるので試合数が上限を超えない様にします。

雑感

この問題は1stステージ、ファイナルステージと日本シリーズでそれぞれ漸化式を求めて計算だけで求める様にできないと時間が足りない様に思えます。
かなり難しいんじゃないかなぁ。