結果

問題 No.1013 〇マス進む
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0