結果

問題 No.76 回数の期待値で練習
コンテスト
ユーザー titia
提出日時 2022-01-05 05:04:53
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 696 ms / 5,000 ms
コード長 720 bytes
コンパイル時間 129 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 50,048 KB
最終ジャッジ日時 2024-10-15 08:09:53
合計ジャッジ時間 2,563 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

E=[0,1.0000000000000000,1.0833333333333333,1.2569444444444444,1.5353009259259260,1.6915991512345676,2.0513639724794235]


# E[x]=a*E[x-1]+b*E[x-2]+c*E[x-3]+d*E[x-4]+e*E[x-5]+f*E[x-6]+1
# この漸化式の導出は、
# https://yukicoder.me/problems/84
# の漸化式を経由して考えると分かりやすい。
#
# この漸化式からa,b,c,d,e,fを求める

a=E[2]-1
b=(E[3]-E[2]*a-1)/E[1]
c=(E[4]-E[3]*a-E[2]*b-1)/E[1]
d=(E[5]-E[4]*a-E[3]*b-E[2]*c-1)/E[1]
e=(E[6]-E[5]*a-E[4]*b-E[3]*c-E[2]*d-1)/E[1]
f=1-a-b-c-d-e

# これを用いて期待値DP

for i in range(10**6):
    E.append(a*E[-1]+b*E[-2]+c*E[-3]+d*E[-4]+e*E[-5]+f*E[-6]+1)

T=int(input())
for tests in range(T):
    N=int(input())

    print(E[N])
0