結果
問題 |
No.1013 〇マス進む
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:18:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 253 ms / 2,000 ms |
コード長 | 1,233 bytes |
コンパイル時間 | 193 ms |
コンパイル使用メモリ | 82,524 KB |
実行使用メモリ | 137,468 KB |
最終ジャッジ日時 | 2025-03-20 20:18:54 |
合計ジャッジ時間 | 13,016 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 62 |
ソースコード
import sys def main(): n, k = map(int, sys.stdin.readline().split()) p = list(map(int, sys.stdin.readline().split())) p = [0] + p # 1-based indexing log_max = 30 # sufficient for K up to 1e9 dp_sum = [[0] * (n + 1) for _ in range(log_max)] dp_next = [[0] * (n + 1) for _ in range(log_max)] # Initialize for j=0 for r in range(1, n + 1): step = p[r] dp_sum[0][r] = step new_r = (r + step - 1) % n new_r += 1 dp_next[0][r] = new_r # Precompute for j >= 1 for j in range(1, log_max): for r in range(1, n + 1): mid_r = dp_next[j-1][r] dp_sum[j][r] = dp_sum[j-1][r] + dp_sum[j-1][mid_r] dp_next[j][r] = dp_next[j-1][mid_r] # Calculate results for each i from 1 to n results = [] for i in range(1, n + 1): current_r = i total = 0 remaining = k for j in reversed(range(log_max)): if remaining >= (1 << j): total += dp_sum[j][current_r] current_r = dp_next[j][current_r] remaining -= (1 << j) results.append(i + total) print('\n'.join(map(str, results))) if __name__ == "__main__": main()