名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

ABC030 D - へんてこ辞書

回答

Submission #552477 - AtCoder Beginner Contest 030 | AtCoder

※ 10^10000とか配列に突っ込みたくなかったので,そういう制約のない言語を使いましたごめんなさい.

回答スライドと一緒なんですが,閉路に突っ込むまでひたすらシミュレーションしていって,もし閉路になる前に終わってしまったらそれを出力,閉路に突っ込んだら,閉路に突っ込むまでのステップ数を減らして,MOD取るみたいな方法でいけます.
ABCのD問題の中でも割と簡単な感じがしました(割とさくさくっと実装できた)

N, a = map(int, input().split())
k = int(input())
bli = [int(i) - 1 for i in input().split()]
current = a-1
visited = [current]
for i in range(k):
    current = bli[current]
    if current in visited:
        subli = visited[visited.index(current):]
        print(subli[(k - len(visited) + len(subli)) % len(subli)] + 1)
        break
    else:
        visited.append(current)
else:
    print(current + 1)