ntk log ntk

競プロや非競技プロのやったことを書いています.

ABC030 D - へんてこ辞書

頭がバグる.人に説明できるくらい理解したい.

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()

類題

類題のすぬけさんの解説がわかりやすいです. これの文字起こしをすればいいか?