読者です 読者をやめる 読者になる 読者になる

「今週のお題:取られたら取り返す!」問題解答 ( CodeIQ )

はじめに

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

codeiq.jp

問題

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

  • 空白区切りで入力されるn,a,b ( いずれも0以上25以下 ) に対して、n点先取デュースありの試合でa点対b点になる時の点数の推移が何通りあるか出力する。

プレイヤーをA,Bとすると、例えばn=3,a=4,b=2に対しては、AABBAA,ABABAA,ABBAAA,BAABAA,BABAAA,BBAAAA の6通りの得点順がありますので、6が答えとなります

解説

まず、デュースを考えなくても良い点数、つまり両者ともn-1点以下の場合は、単純に組み合わせ ${}_{a+b}C_{a}$ で済みます。

また、一方が丁度n点になる場合、そこで試合が終わってしまいますので、最後に得点してnになるようにする必要があります。つまり、n-1に目減りしたものと考えても同じです。

問題は、デュースになった場合です。
しかしこれは、まず n-1:n-1 になった後、( どちらが先に得点しても良いので ) 1点ずつ取り合う展開を続けているものとみなすことができます。なので、最後の1点でアドバンテージを取るか、2点連取で勝負を決める部分を除くと2のべき乗で計算できます。

後は、ありえない点数 ( デュースで2点以上離れるとか ) の場合をケアして、次のコードを提出しました。fcが組み合わせC、ffが2のべき乗を計算する関数です。

終わりに

デュースって、巴戦と並んで、勝率の計算で出てきた印象が強いですね。