結果

問題 No.76 回数の期待値で練習
ユーザー mkawa2mkawa2
提出日時 2020-01-13 12:40:03
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,435 ms / 5,000 ms
コード長 1,192 bytes
コンパイル時間 125 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 49,964 KB
最終ジャッジ日時 2024-05-09 19:59:27
合計ジャッジ時間 4,842 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,435 ms
49,700 KB
testcase_01 AC 1,422 ms
49,964 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def II(): return int(sys.stdin.readline())

def main():
    # サンプルから、1~6の目が出る確率を求める
    # ev[i]が、あと何回で目の和がi以上になるか
    # pp[i]が、さいころのiの目が出る確率
    # 例えばev4=1+ev3*pp1+ev2*pp2+ev1*pp3+(これ以降はevが0なので省略)なので、変形して
    # pp3=(ev4-1-ev3*pp1-ev2*pp2)/ev1
    # ev1=1なのでpp3=ev4-1-ev3*pp1-ev2*pp2
    # 一般化するとpp[i]=ev[i+1]-1-ev[i]*pp[1]-ev[i-1]*pp[2]・・・ev[2]*pp[i-1]
    # これでpp[5]まで求めて、pp[6]=1-sum(pp[1]~pp[5])
    n = 10 ** 6
    ev = [0, 1.0000000000000000, 1.0833333333333333, 1.2569444444444444, 1.5353009259259260, 1.6915991512345676,
          2.0513639724794235] + [0] * n
    pp = [0] * 7
    for i in range(1, 6):
        pp[i] = ev[i + 1] - 1 - sum(pp[dice] * ev[i + 1 - dice] for dice in range(1, i))
    pp[6] = 1 - sum(pp)
    # print(pp)
    # ev[n]のnが最大10**6なので、そこまでDPして、クエリに答える
    for i in range(7, n + 1):
        ev[i] = 1 + sum(pp[dice] * ev[i - dice] for dice in range(1, 7))
    t = II()
    for _ in range(t):
        print(ev[II()])

main()
0