結果

問題 No.1013 〇マス進む
ユーザー NoneNone
提出日時 2021-10-29 14:42:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 588 ms / 2,000 ms
コード長 1,892 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 247,480 KB
最終ジャッジ日時 2024-04-16 13:22:29
合計ジャッジ時間 21,027 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
52,352 KB
testcase_01 AC 42 ms
52,096 KB
testcase_02 AC 41 ms
52,352 KB
testcase_03 AC 54 ms
62,080 KB
testcase_04 AC 48 ms
59,392 KB
testcase_05 AC 54 ms
62,080 KB
testcase_06 AC 53 ms
61,696 KB
testcase_07 AC 59 ms
63,744 KB
testcase_08 AC 55 ms
62,848 KB
testcase_09 AC 59 ms
64,256 KB
testcase_10 AC 57 ms
63,104 KB
testcase_11 AC 54 ms
62,208 KB
testcase_12 AC 60 ms
64,256 KB
testcase_13 AC 77 ms
74,496 KB
testcase_14 AC 266 ms
144,896 KB
testcase_15 AC 441 ms
198,512 KB
testcase_16 AC 404 ms
187,316 KB
testcase_17 AC 247 ms
139,904 KB
testcase_18 AC 286 ms
153,680 KB
testcase_19 AC 190 ms
120,064 KB
testcase_20 AC 518 ms
225,224 KB
testcase_21 AC 222 ms
128,000 KB
testcase_22 AC 314 ms
156,132 KB
testcase_23 AC 141 ms
100,864 KB
testcase_24 AC 551 ms
230,172 KB
testcase_25 AC 537 ms
226,984 KB
testcase_26 AC 139 ms
101,888 KB
testcase_27 AC 218 ms
127,104 KB
testcase_28 AC 127 ms
97,408 KB
testcase_29 AC 506 ms
221,348 KB
testcase_30 AC 199 ms
123,392 KB
testcase_31 AC 341 ms
165,512 KB
testcase_32 AC 259 ms
143,744 KB
testcase_33 AC 266 ms
146,048 KB
testcase_34 AC 423 ms
195,464 KB
testcase_35 AC 403 ms
187,052 KB
testcase_36 AC 90 ms
81,536 KB
testcase_37 AC 88 ms
81,536 KB
testcase_38 AC 459 ms
206,416 KB
testcase_39 AC 168 ms
111,232 KB
testcase_40 AC 433 ms
196,584 KB
testcase_41 AC 145 ms
103,424 KB
testcase_42 AC 259 ms
146,304 KB
testcase_43 AC 175 ms
112,512 KB
testcase_44 AC 269 ms
147,584 KB
testcase_45 AC 248 ms
140,160 KB
testcase_46 AC 152 ms
106,624 KB
testcase_47 AC 256 ms
145,024 KB
testcase_48 AC 312 ms
156,184 KB
testcase_49 AC 426 ms
197,588 KB
testcase_50 AC 345 ms
169,828 KB
testcase_51 AC 324 ms
163,148 KB
testcase_52 AC 99 ms
82,432 KB
testcase_53 AC 128 ms
95,232 KB
testcase_54 AC 407 ms
191,728 KB
testcase_55 AC 163 ms
107,648 KB
testcase_56 AC 498 ms
224,472 KB
testcase_57 AC 348 ms
169,000 KB
testcase_58 AC 588 ms
242,452 KB
testcase_59 AC 568 ms
244,196 KB
testcase_60 AC 579 ms
247,480 KB
testcase_61 AC 549 ms
234,080 KB
testcase_62 AC 542 ms
230,740 KB
testcase_63 AC 42 ms
52,096 KB
testcase_64 AC 42 ms
52,096 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Doubling:
    def __init__(self, A, K_max=10**18 + 1):
        """
        :param A: 初期条件（写像 A:i->j を定義）
        :param K_max: K_max まで参照する可能性がある

        doubling[i][k] := dp[2^i][k]

        ダブリングを考える際、初期値は[0,1,2,....,N-1] (=dp[i][k] の添え字 k)と考えるべき
        """
        self.k_max = K_max.bit_length()
        self.n = len(A)
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.doubling[0]=A

        for i in range(1, self.k_max):
            self.doubling[i] = self.merge(self.doubling[i-1],self.doubling[i-1])

    def merge(self,dp_i,dp_j):
        """
        :return dp[i+j] = merge(dp[i],dp[j])
        """
        dp_ij=[0]*self.n
        for k in range(self.n):
            if dp_j[k]!=-1:
                dp_ij[k]=dp_i[(dp_j[k]+k)%N] + dp_j[k]
        return dp_ij

    def apply_all(self, K):
        """
        :param K: K回進む
        0~N-1の全ての要素を同時にK回進める
        ダブリングを考える際、初期値は[0,1,2,....,N-1] (=dp[i][k] の添え字 k)と考えるべき
        """
        res=P
        for k in range(K.bit_length()):
            if K&(1<<k):
                res = self.merge(self.doubling[k],res)
        return res

################################################################################
def example():
    global input
    example=iter(
        """
5 2
1 2 3 4 5

        """
            .strip().split("\n"))
    input=lambda:next(example)

"""
1->3->4->1->3->4
"""

################################################################################
import sys
input = sys.stdin.readline

# example()

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

doubling = Doubling(P, K_max = 10**18 + 1)
res=doubling.apply_all(K-1)
for i,r in enumerate(res):
    print(i+r+1)
0