私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「クライマックスシリーズの勝敗パターンは何通り？」（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
#!/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
#!/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
入力値を数値にしてsolve()に渡し、結果を印字します。
定数PTN_1、PTN_F、PTN_JPは上記のプログラムで求めたものを{試合数=>パターン数}の形に変えたものです。
考え方の通りにパターン数を計算します。
1stステージとファイナルステージには試合数の上限があるので試合数が上限を超えない様にします。
この問題は1stステージ、ファイナルステージと日本シリーズでそれぞれ漸化式を求めて計算だけで求める様にできないと時間が足りない様に思えます。
かなり難しいんじゃないかなぁ。