ABC030 D - へんてこ辞書
頭がバグる.人に説明できるくらい理解したい.
解法
dfsして閉路検出.ダブリングでやるにはKが大きすぎると思ったけれど,上手くできたりするんでしょうか?
類題として解いたのに1時間くらい実装にかかってしまった.反省.
以下、ぐちゃぐちゃなメモ.
すべて1-indexedとします.
1ステップ目はaにいる.Kステップ後にどこにいるかを知りたい.出力する答えはb_kになる. 閉路が見つかるまでdfsをしたいので,(i,b_i)を辺として持つ有向グラフを考える. また,「何番目にどの点を訪れたか」を記録したリストh_visitedと,「ある点を訪れたのは何番目であるか」を記録したリストp_dicを用意する. どちらも-1で初期化.点aから閉路が見つかるまで(=p_dicが-1でない点を訪れるまで)dfsをする.
dfsは閉路に入ったときのステップ数と閉路長を返す.それらの和がKを超えていたら,Kステップ目にどこにいるかはh_visitedにそのまま記録されているのでb_(h_visited_k)を出力する.超えていなければ,Kから閉路に入ったときのステップ数を引いたものに対して閉路長で余りを取る.この値と閉路に入った時のステップ数の和をインデックスに取ったもののbの値が答え.
え、言語化が難しすぎませんか………
def main(): import sys sys.setrecursionlimit(10**5+5) N, a = (int(i) for i in input().split()) K = int(input()) B = [int(i) for i in input().split()] G = [[] for _ in range(N+1)] for i, b in enumerate(B): G[i+1].append(b) h_visited = [-1]*(N+1) p_dic = [-1]*(N+1) def dfs(v, i=1): if p_dic[v] != -1: return p_dic[v], i-p_dic[v] h_visited[i] = v p_dic[v] = i for nv in G[v]: prec_length, c_length = dfs(nv, i+1) return prec_length, c_length pl, cl = dfs(a) if K < pl+cl: print(B[h_visited[K]-1]) else: K -= pl K %= cl print(B[h_visited[pl+K]-1]) if __name__ == '__main__': main()
類題のすぬけさんの解説がわかりやすいです. これの文字起こしをすればいいか?