私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「回数指定のじゃんけん２」（CodeIQ）を参照してください。
m 人が「じゃんけん」をします。
1回対戦するたびに、勝った人だけが残り、負けた人は次から参加しないものとします。
ちょうど n 回のじゃんけんをしたときに、一人だけが残るような出し方の組み合わせが何通りあるかを求めます。
なお、「あいこ」も1回とカウントします。
このとき、個人は識別しないものとし、その場に出ている手の組み合わせが何通りあるかをカウントします。
つまり、m = 3 で、
・Aさんがパー、BさんとCさんがグーを出した場合
・Bさんがパー、AさんとCさんがグーを出した場合
・Cさんがパー、AさんとBさんがグーを出した場合
は全部で一通りとカウントします。
m = 3, n = 2 のときは、以下の表のように
・1回目があいこで2回目に1人だけが勝つ … 4通り×3通り＝12通り
・1回目で2人が勝ち、2回目に1人が勝つ … 3通り×3通り＝9通り
なので、全部で21通りがあります。
例）
1回目があいこのパターン グー・グー・グー
チョキ・チョキ・チョキ
パー・パー・パー
グー・チョキ・パー
その後、2回目に1人だけが勝つパターン グー・チョキ・チョキ
チョキ・パー・パー
パー・グー・グー
1回目で2人が勝つパターン グー・グー・チョキ
チョキ・チョキ・パー
パー・パー・グー
その後、2回目に1人が勝つパターン グー・チョキ
チョキ・パー
パー・グー
標準入力から m と n がスペースで区切って与えられますので、出し方の組み合わせが何通りあるかを標準出力に出力してください。
なお、m, n は10以下の正の整数とし、出力は32bitの整数で表現できるような範囲で入力が与えられますので、巨大な数に対応する必要はありません。
【入出力サンプル】
標準入力
3 2標準出力
21
Rubyで解答しています。
#!/usr/bin/ruby
# 組み合わせを計算する
def combin(n, r)
a = 1
b = 1
n.downto(n-r+1){|i| a*=i}
r.downto(1){|i| b*=i}
return a/b
end
# m人の時の全部の手のパターン
def totalPattern(m)
return combin(3+m-1, m)
end
def getRest(arr, m)
results = Array.new(m+1, 0)
# 残り人数2人以上の場合について処理する
for i in 2..m
if arr[i] == 0 then next end
total = totalPattern(i)
# printf("i=%d, total=%d\n", i, total)
# a人の中でw人が勝ち残るパターンを計算する
# アイコでない場合は勝ち人数ごとに3パターンずつしかない
for w in 1...i
results[w] += (3*arr[i])
total -= 3
end
results[i] = (arr[i]*total)
# printf(" %s\n", results.to_s)
end
return results
end
def init(m)
a = Array.new(m+1, 0)
a[m] = 1
return a
end
def solve(m,n)
results = [init(m)] # 残りの人数リスト。添字が残りの人数。値がパターン数
for i in 0...n
# puts "----- " + i.to_s + " -----"
results << getRest(results[i], m)
end
return results.last[1]
end
# main
while line = gets
line.strip!
if line.empty? then next end
m,n = line.split.map{|a| a.to_i}
p solve(m,n)
end
プルグラム的にはそれほど難しくはありませんが、やはり数学能力が要求されます。
基本的には1回目〜n回目まで勝ち残る（アイコで残るのも含む）人数ごとにパターン数を求め、n回目が終わったところで1人残っている場合のパターン数を返せば良いわけです。
x人いる時の勝負に関して問題のように数えた場合の全パターン数は3Hx（3パターンのものからx個を選ぶ重複組み合わせ）になります。誰が何を出したかを考慮した場合、重複順列なのは容易に分かると思います。今回の問題は誰が何を出したかを考慮しない＝順番を考慮しないので順列ではなく組み合わせになるわけです。
| x | 勝つ人数ごとのパターン | |||
|---|---|---|---|---|
| 1 | 2 | 3 | 4 | |
| 2 | GC, CP, PG | 3H2-3 | - | - |
| 3 | GCC, CPP, PGG | GGC, CCP, PPG | 3H3-6 | - |
| 4 | GCCC, CPPP, PGGG | GGCC, CCPP, PPGG | GGGC, CCCP, PPPG | 3H4-9 |
そしてi回目の勝負が終わった時点に次の勝負に残る人数のパターン数をr1,r2,…,rxとするとi+1回目に残る人数は次のようになります。
1人残る：3*(r2+r3+…+rx)
2人残る：r2*(3H2-3)+3*(r3+r4+…+rx)
3人残る：r3*(3H3-6)+3*(r4+r5+…+rx)
…
x人残る：3Hx-3*(x-1)
なので、これを実装すれば良いわけです。
組み合わせnCrを計算します。
m人の場合に考えられる手のパターン数の総数を計算します。
実際はnHrの計算なのですが、nHr = n+r-1Crなのでこれを返します。
この問題ではn=3, r=m（引数）なので3+m-1Cmという式になります。
前回の結果から今回の勝負で残る人数ごとのパターン数を計算します。
arrは前回のパターン数の配列で、添字番号が残っている人数、各要素が人数ごとのパターン数を表します。残る人数が0の場合は無駄な領域ですが添字番号を人数と一致させるため常に0をとるものとして含めます。
mは入力値のmです。
resultsは結果を保持する領域です。引数arrと同じ構成なので要素数はm+1になります。この後の処理でパターン数を加算するので0で初期化しておきます。
23〜38行目のループで前回のパターンから今回の勝負結果のパターンを計算します。
残り人数1の場合は前回の勝負で勝者が確定しているので無視します。なのでループカウンタは2からになります。
i人残っているパターンが0の場合、計算する必要がないので無視します（24行目）。
i人の場合に出し得る手のパターンの総数を計算します（26行目）。
i人のうちw人（1〜i-1）が勝つ場合を求め（31〜34行目）、結果に加算します（32行目）。考え方に書いた通り、3パターンずつしかないのでwの値ごとに(3*arr[i])になります。同時に、アイコになる場合を求めるため勝ちが決まったパターン数をtotalから引きます（33行目）。
次回にw人が残る（アイコの場合）を設定します（36行目）。ここは
results[i] += (arr[i]*total)
とした方がわかりやすかったかもしれません。wのループカウンタが1から始まるので「+=」としても0に加算される場合しかないため「=」でも同じことになります。
全部の計算が終わったらresultsを返します。
開始時点の人数ごとのパターン数の配列を作ります。
[0,0,0,…,0,1]と要素数が(m+1)で最後だけ1の配列を作るだけです。
初期状態はm人がいる1パターンしかないのでこのようになります。
n回getRest()を呼んで結果を計算します。
毎回前回の結果を引数に渡すことで次回の結果を求めることができます。
resultsには0〜n回目の結果が記録されているので、results.last[1]がn回じゃんけんをした時に1人が勝ち残っているパターン数になります。
このコードを書いた後で、検算用にほぼ総当たりのコードを（solve()でパターン数だけを管理するのは同じで、getRest()のパターン数を求める部分をrepeated_combination()を使って全部数える）を書いたのですが、こちらでもm=10,n=10で問題ないだけの性能が出ました。
出題者の意図としては動的計画法でパターンを列挙して数えるようなコードを想定していたのでしょうか？ この出題者の傾向からするとあまりそういう感じもしないのですが。