PythonでABC167-Dを解く

はじめに

昨日解けなかったDを解きます

ABC167-DTeleporter

考えたこと
$K$が大きいのでどこかでループしていないと解けなさそう→ループ検知しよう。となり、$K$の大きさで場合分けとなります。
実装に必要なのは、訪れているかを判定するlistと訪ずれた順番を記録するlistです。前者のlistは無限ループを防ぎ、後者のlistは後の実装を楽にします。

n, k = map(int,input().split())
a = list(map(int,input().split()))

s = [True] * n #訪れているかを判定するlist
c = [1] #訪ずれた順番を記録するlist
now = 0 #現在地
while s[now]:
    s[now] = False #訪ずれた地点を記録
    now = a[now] - 1
    c.append(now+1)

start_cycle = c.index(c[-1]) #ループに入る点
loop = c[start_cycle:-1] #ループのlist
cycle = len(loop)

if k < start_cycle: #ループまで到達できないK
    print(c[k])
else:
    k -= start_cycle
    k %= cycle
    print(loop[k])

まとめ

落ち着いていればコンテスト中に解けたので悔しい。ではまた。