[AtCoder] ABC 167 D – Teleporter

2020年5月13日2020年12月12日

問題

方針

配列は \( 0 \) を基準として考えます。

閉路を構築する問題です。頂点 \( 1 \) から出発してループになっている道を見つけるには、頂点に訪れた回数を数えれば良いです。\( 2 \) 回以上訪れた頂点の集合がループとなります。配列 \( v\) を探索で訪れた順の頂点の集合、 配列 \( l \) を閉路の頂点の集合とします。初期値は、\( v_0 = 1\)、\( v_1 = A_0\)、\( |v| = 2\) です。

\( |l| \leq |v| \) は明らかです。\( 3 \) 回訪れた頂点が出てきた時点で探索を打ち切ります。

\( K < |v| \) のとき

このとき、\( v_{K} \) が答えとなります。

\( |v| \leq K\) のとき

このとき、頂点 \( l_0 \) に \( 2 \) 回目に訪れるたときのテレポーターを使った回数は、\( |v| \) です。閉路は周期が \( |l| \) なので、答えは、

\[l_{(K – |v|) \bmod |l|}\]

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    ll K;
    cin >> N >> K;
    int A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        A[i]--;
    }
    int d[N]{};
    vector<int> l;
    vector<int> v;
    int u = 0;

    while (d[u] < 2) {
        v.push_back(u + 1);
        d[u]++;
        if (d[u] >= 2) {
            l.push_back(u + 1);
        }
        u = A[u];
    }
    if (K < v.size()) {
        cout << v[K] << "\n";
    } else {
        cout << l[(K - v.size()) % l.size()]<< "\n";
    }
    return 0;
}