TopCoder SRM 653 Div2 Med: RockPaperScissorsMagicEasy

ちょっと考えた。

問題はこちら。

問題

AさんとBさんがN回じゃんけんをすることになった。AさんはN回のじゃんけんそれぞれでどの手を出すかはじめに宣言する。各じゃんけんで、BさんはAさんに勝つと1ポイント、負けか引き分けだと0ポイント手に入れる。BさんはN回のじゃんけん後の獲得ポイントをscoreに合わせたい。Bさんが出すことのできるじゃんけんの手の組み合わせは何通りあるか答えよ。

解法

scoreがNより大きいときは獲得ポイントはscoreに到達しえないので答えは0となる。

score≦Nの場合を考える。実はAさんがどの手を出すかの情報はいらない。
まずBさんがどのじゃんけんに勝つかを決める。これはN個の中からscore個を取る組み合わせの数となる。
そのあとにN-score回負けか引き分けをするのだが、この手の出し方は2^N-scoreだけある。
したがって答えはこの2つの値を掛け合わせたものになる。

def C(n, r):
    res = 1
    for i in xrange(r):
        res *= n - i
    for i in xrange(1, r + 1):
        res /= i
    return res % mod
    
def count(self, card, score):
    N = len(card)
    if score > N: return 0
    return C(N, score) * pow(2, N - score, mod) % mod

まとめ

C++とかだとDPでコンビネーションを求めないといけないね。