結果
問題 |
No.1013 〇マス進む
|
ユーザー |
![]() |
提出日時 | 2022-08-21 09:32:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 308 ms / 2,000 ms |
コード長 | 1,330 bytes |
コンパイル時間 | 289 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 137,088 KB |
最終ジャッジ日時 | 2024-10-10 02:26:01 |
合計ジャッジ時間 | 12,491 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 62 |
ソースコード
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 = answer+1#A[answer] K = K2 while K: if K & 1: out += dp_sum[i][answer] # 加算していくタイプ用 answer = dp[i][answer] K >>= 1 i += 1 print(out)