結果

問題 No.76 回数の期待値で練習
コンテスト
ユーザー mkawa2
提出日時 2020-01-13 12:40:03
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,422 ms / 5,000 ms
コード長 1,192 bytes
コンパイル時間 354 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 49,832 KB
最終ジャッジ日時 2024-12-17 13:22:59
合計ジャッジ時間 5,074 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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