はじめに
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)
補足
終わり
質問やご指摘、ご意見はこちらまで
Twitter : Waaa1471