結果

問題 No.463 魔法使いのすごろく🎲
コンテスト
ユーザー titia
提出日時 2026-07-20 08:58:27
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 87 ms / 2,000 ms
+ 284µs
コード長 1,964 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 237 ms
コンパイル使用メモリ 95,596 KB
実行使用メモリ 84,348 KB
最終ジャッジ日時 2026-07-20 08:58:33
合計ジャッジ時間 4,784 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

n,m=list(map(int,input().split()))
C=[0]+list(map(int,input().split()))+[0]

A=[[0]*(n) for i in range(n)]

for i in range(n-1):
    now=i
    plus=1
    for j in range(m):
        if now==n-1:
            plus=-1

        now+=plus
        A[now][i]-=1/m

for i in range(n):
    A[i][i]+=1

#for a in A:
#    print(*a)

# 行列の計算（numpyを使えないとき）
def prod(A,B,k,l,m):# A:k*l,B:l*m
    C=[[None for i in range(m)] for j in range(k)]

    for i in range(k):
        for j in range(m):
            ANS=0
            for pl in range(l):
                ANS=(ANS+A[i][pl]*B[pl][j])

            C[i][j]=ANS

    return C

def plus(A,B,k,l):# a,B:k*l
    C=[[None for i in range(l)] for j in range(k)]

    for i in range(k):
        for j in range(l):
            C[i][j]=(A[i][j]+B[i][j])

    return C


# 逆行列を掃き出し法で計算（floatで計算）
# ※どこがバグってそう！
def inv_transformation(A,x): # xは正方行列の行数
    for i in range(x):
        A[i]+=[0]*x
        A[i][i+x]=1
    
    for i in range(x):  
        for j in range(x):
            if i==j:
                continue

            base=A[i][i]
            if base!=1:
                for k in range(x*2):
                    A[i][k]/=base
                    
            target=A[j][i]
            if target==0:
                continue

            for k in range(x*2):
                    A[j][k]-=A[i][k]*target

    B=[[0]*x for i in range(x)]

    for i in range(x):
        for j in range(x):
            B[i][j]=A[i][j+x]

    return B

B=inv_transformation(A,n)

X=prod([C],B,1,n,n)

#print(X)

ANS=[1<<63]*n

for i in range(n-1,-1,-1):
    if i+m>=n-1:
        ANS[i]=C[i]
    else:
        for j in range(1,m+1):
            ANS[i]=min(ANS[i],C[i]+X[0][i+j])

        score=C[i]
        for j in range(1,m+1):
            score+=ANS[i+j]/m

        ANS[i]=min(ANS[i],score)

print(ANS[0])
0