「今週のお題：回数指定のじゃんけん」問題解答 ( CodeIQ )

CodeIQ

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • A,Bがじゃんけんする時、決着がつくまでの勝敗分のパターンが何通りあるか出力する。
  • A,Bどちらかの「敗数-勝数」が一定値に達した時点で決着となる。引き分けは決着に影響しない。
    ※コインの遣り取りをして、コインがなくなったら決着、という風になっています
  • 試合数には上限があり、上限に達した時点で決着しなかったケースはカウントしない。
  • A,Bの決着する時の「敗数-勝数」のライン ( コイン所持数 )、試合数上限はカンマ区切りで入力される。

解説

方針

引き分けのことを忘れて勝敗だけで考えると、 試合数の上限のある中で、一定の勝敗数差がついた時点で打ち切りとなる勝負であり、 制限のあるグラフ上でのグラフの辿り方を考えるのと同じです。

制限は次の通り。

  • 最後の試合に負けた方がトータル負けで決着する
  • 最後の負けを除き、試合数上限を$u$、A,Bのコインを$a,b$、負け数を$l_a,l_b$とした時、
    $l_a-l_b\lt a,\,\,l_b-l_a\lt b,\,\,l_a+l_b\lt u$

例えば $a,b,u=4,3,10$ の例であれば、次のグラフのような経路の数え方ができます。
※2016/2/17追記: すいません。図中の数字に一部計算間違いがあります。198,353はそれぞれ197,352が正しいです。後ほど現れる類似の図も同様です。

f:id:ange1:20160217014927p:plain

格子点で上・左両方からの経路がある場合は上と左の格子の数を足して行く、という手法で、グラフの格子点に場合の数を書き込んで行くことで、各勝敗数における状況が分かります。例えばAの1勝5敗で決着するのは4通り、といった具合です。

ここから引き分けも組み込んでいくわけですが、「勝敗が決した後は全て引き分けの消化試合として扱う」と考えて不整合は生じません。
どういうことかと言うと、次の図のようになります。

f:id:ange1:20160217022324p:plain

これは1勝5敗の一例ですが、実際には決着までの引き分け数が2であっても、決着後を全て引き分けで4分けにしてしまうのです。そうすれば単純に「制限数一杯試合をした場合、引き分けがどこに発生するか」を考えるのと同じですから、引き分けの発生状況を単純に組み合わせ C で計算することができるのです。
この例ならば${}_{10}C_{4}$通りですね。

10戦上限で1勝5敗の場合、勝ち・負けの経緯が4通り、引き分けが${}_{10}C_{4}$通りということで、$4\times{}_{10}C_{4}$となります。この計算を全ケースで行い合計を求めれば答えになります。

実装

実装としては、場合の数を保持したグラフの格子点を管理し、勝敗の合計の増加につれスライドさせる方法を採ります。そうすれば、その時々で管理すべき格子サイズは$a\times b$で済むからです。

f:id:ange1:20160217022402p:plain

格子の右上・左下の隅の数字が、引き分け抜きでの勝ち・負けの経緯が何通りになるかの数字ですから、後は引き分けの組み合わせを計算していきます。

試合数上限に抵触するまで、格子の上端・左端を削って、代わりに下・右を拡張していくことでスライドを実現します。 なお、試合数上限に達したかどうかは、「引き分けの発生の仕方」が計算上0通りになったかどうかで分かります。しかも一旦0になったら後は計算を繰り返してもずっと0ですから、答えに影響することなく、A負け/B負け両方のケースで試合数上限に達するまでそのまま同じ処理で済みます。

提出版は次のRubyのコードです。なお、今回golfは特にやってません。

# コイン数を保持する配列ab,試合数上限u
*ab,u=gets.split(?,).map &:to_i
ans=0
# 格子mを初期化
m=(2..ab[1]).reduce([[1]*ab[0]]){|s|t=0;s<<s[-1].map{|e|t+=e}}
# A全敗/B全敗での引き分けの場合の数 uCa,uCb を保持
d=ab.map{|x|(1..x).reduce(1){|t,i|t*(u+1-i)/i}}
while d.any?{|e|e>0}
  [0,1].each do |i|
    # 格子の隅 ( 引き分け抜きでの場合の数 ) と引き分けの場合の数を乗じて答えに累積
    ans+=d[i]*m[-i][i-1]
    # uCx から uC(x+2) を計算
    d[i]=d[i]*(u-ab[i])*(u-ab[i]-1)/((ab[i]+1)*(ab[i]+=2))
  end
  # 格子を更新
  m.shift
  t=0;m.each{|r|r.shift;r<<t+=r[-1]}
  t=0;m<<m[-1].map{|e|t+=e}
end
puts ans

おわりに

正方形の対角線を超えない経路だとカタラン数が出てきますが、今回のようにどこにラインが来るか分からない場合、何かうまい計算方法はあるんでしょうかね?? 気になるところです。