結果
問題 |
No.463 魔法使いのすごろく🎲
|
ユーザー |
![]() |
提出日時 | 2025-08-24 14:10:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 81 ms / 2,000 ms |
コード長 | 2,844 bytes |
コンパイル時間 | 297 ms |
コンパイル使用メモリ | 82,916 KB |
実行使用メモリ | 77,192 KB |
最終ジャッジ日時 | 2025-08-24 14:10:07 |
合計ジャッジ時間 | 3,825 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
import sys # sys.setrecursionlimit(200005) # sys.set_int_max_str_digits(200005) int1 = lambda x: int(x)-1 pDB = lambda *x: print(*x, end="\n", file=sys.stderr) p2D = lambda x: print(*x, sep="\n", end="\n\n", file=sys.stderr) def II(): return int(sys.stdin.readline()) def LI(): return list(map(int, sys.stdin.readline().split())) def LLI(rows_number): return [LI() for _ in range(rows_number)] def LI1(): return list(map(int1, sys.stdin.readline().split())) def LLI1(rows_number): return [LI1() for _ in range(rows_number)] def SI(): return sys.stdin.readline().rstrip() dij = [(0, 1), (-1, 0), (0, -1), (1, 0)] # dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)] # inf = -1-(-1 << 31) inf = -1-(-1 << 62) # md = 10**9+7 md = 998244353 # 基本変形のみ(破壊的) # すべて0の行は無視できる # 係数のみすべて0の行があるときは解なし # すべて0の列の変数は何でもよい def gaussian_elimination(matrix): h, w = len(matrix), len(matrix[0]) i = 0 jj = [] for j in range(w-1): if i == h: break k = i while k < h and matrix[k][j] == 0: k += 1 if k == h: continue jj.append(j) if k > i: matrix[i], matrix[k] = matrix[k], matrix[i] mi = matrix[i] if mi[j] != 1: for l in range(j+1, w): mi[l] /= mi[j] mi[j] = 1 for k in range(i+1, h): mk = matrix[k] if mk[j] == 0: continue c, mk[j] = mk[j], 0 for l in range(j+1, w): mk[l] = mk[l]-mi[l]*c i += 1 for j in jj[::-1]: i -= 1 mi = matrix[i] for k in range(i): mk = matrix[k] if mk[j] == 0: continue c, mk[j] = mk[j], 0 for l in range(j+1, w): mk[l] = mk[l]-mi[l]*c # 拡大係数行列を解く # 不定の解はNoneを返す # 解なしは空のリストを返す def linear_equation(matrix): gaussian_elimination(matrix) h, w = len(matrix), len(matrix[0]) res = [None]*(w-1) for i in range(h): mi, k = matrix[i], -1 for j in range(w-1): if mi[j]: k = j if k == -1 else w if k == -1 and mi[-1]: return [] if 0 <= k < w-1: res[k] = matrix[i][w-1] return res n,m=LI() cc=[0]+LI()+[0] if m==1: print(sum(cc)) exit() mat=[[0]*m for _ in range(m-1)] for i in range(m-1): mat[i][i]=m for j in range(i+1,i+1+m): if j==m-1:continue if j>m-1:j=2*m-2-j mat[i][j]-=1 mat[i][-1]+=cc[n-m+j] p2D(mat) dp=[[0]*n,[0]*n] dp[1][n-m:n-1]=linear_equation(mat) for i in range(n-m)[::-1]: dp[0][i]=min((sum(dp[0][i+1:i+1+m])+sum(cc[i+1:i+1+m]))/m, min(dp[1][j]+cc[j] for j in range(i+1,i+1+m))) dp[1][i]=(sum(dp[1][i+1:i+1+m])+sum(cc[i+1:i+1+m]))/m print(dp[0][0])