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

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

No.250 atetubouのzetubou

No.250 atetubouのzetubou - yukicoder

難しかったです…。


見たことあるような感じだったんですが、どうも組み合わせの数が合わないと思って解説を読んだら、自分が考えた組み合わせがめちゃくちゃだったみたいですね…。(小さいケースで全部試してみて、数の計算をしてみたけどだめ)


本質的には重複組み合わせの問題でした。


重複組合せと気付けば指定回数と比べてすぐ、とおもいきや10^15超えた時の処理などがおかしく、なかなかAC出来ませんでした。
最初C++で組んでいたのですが、打ち切り処理などが甘く、結局Pythonを使って階乗のリストを作り、計算しました。多倍長ってすげー


他の人の回答を見ると、パスカルの三角形みたいにして、組み合わせを求めておいて、大きすぎるものは全てINFにしてしまう、みたいな方法が取れるみたいです。賢いなあ。(自分には出来なかった)
この方法でもまた解き直してみたいですね。


それとそもそも自分でfact求めなくても、math.factorialを使えば階乗求まるので、ライブラリの知識も甘いなあと実感させられたのでした。

math.factorical使った版。ただ、毎回計算を呼び出すので遅い。。。
#82094 No.250 atetubouのzetubou - yukicoder


自分で階乗求めたバージョンの解答。Python3です。

#80851 No.250 atetubouのzetubou - yukicoder

def solve():
    fact = [1]*3001
    s = 1
    for i in range(1, 3001):
        s *= i
        fact[i] = s

    for i in range(int(input())):
        d, x, t = map(int, input().split())
        n = (d + x - 1)
        r = x if (n//2 > x) else (n - x)
        ans = fact[n] // (fact[n - r] * fact[r])
        """
        print(list(str(ans)))
        print(list(str(t)))
        print(n, r, n-r)
        """
        print("AC" if ans <= t else "ZETUBOU")


if __name__=="__main__":
    solve()