AtCoder Beginner Contest 167 [ D - Teleporter ] https://atcoder.jp/contests/abc167/tasks/abc167_d

abc167_d.py

'''
[問題]
https://atcoder.jp/contests/abc167/tasks/abc167_d

[解説]
https://blog.hamayanhamayan.com/entry/2020/05/10/232914
 dpでダブリングを用いるのが想定解答のようだが、周期性を用いたコードで何とか解けた。

'''

import sys

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

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


dict = {}   # ループになる数字のインデックスを保存
loop_mae = 0    # ループになる数字の前の数
loop = 0        # ループの長さ
i = 0           # 次にいく場所のインデックス
R = [1]         # 町番号の出現順に保存
dict[1] = 0     # 1番目の町はインデックス0
j = 1           # 何個目か。

while True:

    a = A[i]
    if (a in dict) == False:
        dict[a] = j
        i = A[i] - 1
        R.append(a)
    else:
        loop = j - dict[a]
        loop_mae = dict[a]
        break

    j += 1
    if j >= N:
        break

if loop_mae >= K:
    # ループは発見されているがKよりループ前のほうが長い
    print(R[K])
else:
    # 素直なループ計算
    num = (K - loop_mae) % loop
    print(R[loop_mae + num])