「今週のお題：取られたら取り返す！」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 空白区切りで入力される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のべき乗を計算する関数です。
終わりに
デュースって、巴戦と並んで、勝率の計算で出てきた印象が強いですね。
