[AtCoder] ABC 030 D – へんてこ辞書

2020年12月4日2020年12月12日

問題

方針

\( k \) 回シミュレーションを行うことはできないので、シミュレーションを高速化の考えます。\( k \) が十分大きければ、探索の過程で同じ単語を調べることになるので、閉路が存在することになります。下記の問題がこの問題と非常に似ています。

したがって、\( k \) から閉路に入るまでのステップ数を引いたものを、閉路の距離で剰余を計算すれば良いです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int N, a;
    string k;
    cin >> N >> a >> k;
    int b[N];
    for (int i = 0; i < N; i++) {
        cin >> b[i];
        b[i]--;
    }
    int d[N]{};
    vector<int> v, w;
    int u = a - 1;
    while (d[u] < 2) {
        v.push_back(u);
        d[u]++;
        if (d[u] >= 2) {
            w.push_back(u);
        }
        u = b[u];
    }
    if (k.length() <= 7) {
        int c = atoi(k.c_str());
        if (c < v.size()) {
            cout << v[c] + 1<< "\n";
        } else {
            c -= v.size();
            cout << w[c % w.size()] + 1<< "\n";
        }
        return 0;
    }
    int g = 1;
    int id = 0;
    for (int i = 0; i < k.length(); i++) {
        id = (id + g * (k[k.length() - i - 1] - '0')) % w.size();
        g = (g * 10) % w.size();
    }
    id -= v.size();
    while (id < 0) id += w.size();
    cout << w[id] + 1 << "\n";
    return 0;
}