結果

問題 No.76 回数の期待値で練習
ユーザー titiatitia
提出日時 2022-01-05 05:04:53
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 657 ms / 5,000 ms
コード長 720 bytes
コンパイル時間 140 ms
コンパイル使用メモリ 10,948 KB
実行使用メモリ 47,360 KB
最終ジャッジ日時 2023-08-05 11:02:10
合計ジャッジ時間 2,532 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 624 ms
47,248 KB
testcase_01 AC 657 ms
47,360 KB
権限があれば一括ダウンロードができます

ソースコード

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