はじめに

ABC 167 D 問題 Teleporter を解くために考えたこと、ACできるPython3(PyPy3)コードを紹介します。

E.Teleporter

問題ページ
難易度：茶色 754

考察

$K$ 回愚直に操作を追うことはできませんが、ループ構造に注目すると高速に最終値を求めることができそうです。

最終位置を求めるためには、ループ最終周でループの始点からあといくつ進めるのかを求める必要があります。
したがって操作回数 $i$ を入力して、$i$ 回目の操作でどの町にいるのかを求められるテーブルを作成しておけば、これらを $O(1)$ で求めることができそうです。
終点の位置など、ループにまつわる情報を求めたいので、ループ位置を検知する必要があります。

状態の遷移を素直に前から見ていくと、初めて $A_i$ が重複した位置でループ構造の終点を検出できます。同時に、その $A_i$ が以前に登場した位置で始点を検出できます。
したがって $A_i$ を入力して、それが何回目の操作かを求められるテーブルを作成しておけば、これらを $O(1)$ で求めることができそうです。

操作回数は $N$ 回までありえるので、これを満たすテーブルを用意します。範囲外参照を絶対に起こさない程十分大きなサイズで余裕を持たせてもよいと思います。

コード

pypy3
260 ms/ 2000 ms

N,K=[int(xy) for xy in input().split()]
A=[0]+[int(a) for a in input().split()]
count_A=[0 for _ in range(N+1)]
count_A[0]=1
A_count=[N for _ in range(N+1)]
A_count[1]=0
for i in range(1,N+1):
    count_A[i]=A[count_A[i-1]]
    # 既出値ならば終点
    if A_count[count_A[i]]<N:
        end=i
        start=A_count[count_A[i]]
        break

    A_count[count_A[i]]=i


if K<end:
    ans=count_A[K]

else:
    rem=K-end
    # 最終周で進める数
    rem%=(end-start)
    ans=count_A[start+rem]

print(ans)

補足

類題
問題ページ
ネタバレ防止で、abc 240 ～ 245 C ～ E と記します。
こちらの問題も記事にしているのでぜひご覧ください

終わり

質問やご指摘、ご意見はこちらまで
Twitter : Waaa1471