結果

問題 No.1013 〇マス進む
コンテスト
ユーザー norioc
提出日時 2026-05-04 02:25:27
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 274 ms / 2,000 ms
コード長 1,243 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 130 ms
コンパイル使用メモリ 85,504 KB
実行使用メモリ 195,968 KB
最終ジャッジ日時 2026-05-04 02:25:45
合計ジャッジ時間 13,973 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 62
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class DoublingDP:
    def __init__(self, xs: list, f0, op, nb=60):
        size = len(xs)
        doubling = [[0] * size for _ in range(nb)]
        dp = [[0] * size for _ in range(nb)]
        for i in range(size):
            doubling[0][i] = xs[i]
            dp[0][i] = f0(i)

        for k in range(nb-1):
            for i in range(size):
                doubling[k+1][i] = doubling[k][doubling[k][i]]
                dp[k+1][i] = op(dp[k][i], dp[k][doubling[k][i]])

        self.nb = nb
        self.doubling = doubling
        self.dp = dp
        self.op = op

    def query(self, k: int, start: int, init):
        cur = start
        val = init
        for i in range(self.nb):
            if k & (1 << i):
                val = self.op(val, self.dp[i][cur])
                cur = self.doubling[i][cur]

        return cur, val


def op(a, b):
    return a + b


def f(p: int) -> int:
    # 1 周したか
    if p + P[p] >= N:
        return 1

    return 0


N, K = map(int, input().split())
P = list(map(int, input().split()))

nexts = [(i + p) % N for i, p in enumerate(P)]
d = DoublingDP(nexts, f, op)
for i in range(N):
    cur, val = d.query(K, i, 0)
    # print(f'{cur=} {val=}')
    ans = val * N + cur + 1
    print(ans)
0