結果
問題 |
No.1013 〇マス進む
|
ユーザー |
![]() |
提出日時 | 2022-08-21 09:29:46 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,321 bytes |
コンパイル時間 | 341 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 137,216 KB |
最終ジャッジ日時 | 2024-10-10 02:23:47 |
合計ジャッジ時間 | 13,366 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 2 WA * 60 |
ソースコード
def oi(): return int(input()) def os(): return input() def mi(): return list(map(int, input().split())) # import sys # input = sys.stdin.readline # import sys # sys.setrecursionlimit(10**8) # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') input_count = 0 N, K = mi() A = mi() # 最大操作回数よりも大きい2^LOGのLOGをいれる LOG = 30 # ダブリングのテーブル dp = [[0 for j in range(N)] for i in range(LOG)] dp_sum = [[0 for j in range(N)] for i in range(LOG)] # 加算していくタイプ用 # 初期条件 for i in range(N): # 初期の遷移を全て網羅することで2^i回目でも遷移できるようにする dp[0][i] = (A[i]+i)%N dp_sum[0][i] = A[i] # 加算していくタイプ用 # 遷移(2のベキ回) for i in range(1, LOG): for j in range(N): ind = dp[i - 1][j] dp[i][j] = dp[i - 1][ind] ind_dp_val = dp_sum[i - 1][j] # 加算していくタイプ用 dp_sum[i][j] = dp_sum[i - 1][ind] + ind_dp_val # 加算していくタイプ用 # 解を求める K2 = K for answer in range(N): i = 0 out = A[answer] K = K2 while K: if K & 1: out += dp_sum[i][answer] # 加算していくタイプ用 answer = dp[i][answer] K >>= 1 i += 1 print(out)