結果

問題 No.1688 Veterinarian
ユーザー 👑 rin204rin204
提出日時 2022-01-25 17:09:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 790 ms / 3,000 ms
コード長 1,025 bytes
コンパイル時間 399 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 181,608 KB
最終ジャッジ日時 2024-12-16 08:49:19
合計ジャッジ時間 4,285 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
51,840 KB
testcase_01 AC 41 ms
51,712 KB
testcase_02 AC 48 ms
58,368 KB
testcase_03 AC 43 ms
51,968 KB
testcase_04 AC 43 ms
51,712 KB
testcase_05 AC 40 ms
51,712 KB
testcase_06 AC 68 ms
68,096 KB
testcase_07 AC 38 ms
51,840 KB
testcase_08 AC 790 ms
181,608 KB
testcase_09 AC 723 ms
177,884 KB
testcase_10 AC 236 ms
92,112 KB
testcase_11 AC 131 ms
80,140 KB
testcase_12 AC 37 ms
51,840 KB
testcase_13 AC 152 ms
79,504 KB
testcase_14 AC 46 ms
58,112 KB
testcase_15 AC 325 ms
104,020 KB
testcase_16 AC 47 ms
57,472 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

memo = {}
def dfs(a, b, c, n):
    if (a, b, c, n) in memo:
        return memo[(a, b, c, n)]
    tot = a + b + c
    if n == 0 or tot <= 1:
        return 0, 0, 0
    ret = [0, 0, 0]
    
    div = tot * (tot - 1) // 2
    dif = div
    if a >= 2:
        aa = a * (a - 1) // 2
        dif -= aa
        tmp = dfs(a - 1, b, c, n - 1)
        ret[0] += aa / div
        for i in range(3):
            ret[i] += tmp[i] * aa / div
    if b >= 2:
        bb = b * (b - 1) // 2
        dif -= bb
        tmp = dfs(a, b - 1, c, n - 1)
        ret[1] += bb / div
        for i in range(3):
            ret[i] += tmp[i] * bb / div
    if c >= 2:
        cc = c * (c - 1) // 2
        dif -= cc
        tmp = dfs(a, b, c - 1, n - 1)
        ret[2] += cc / div
        for i in range(3):
            ret[i] += tmp[i] * cc / div
    tmp = dfs(a, b, c, n - 1)
    for i in range(3):
        ret[i] += tmp[i] * dif / div
    memo[(a, b, c, n)] = ret
    return ret
    

a, b, c, n = map(int, input().split())    
print(*dfs(a, b, c, n))
0