ABC167 D - Teleporter

はじめに

ありがとう、ミカミくん

問題のリンク

D - Teleporter

コンテスト中の思考過程

・これは最近見たことある！延々と辞書を引かされ続けるミカミくんだ！！

D - へんてこ辞書

・ありがとう、ミカミくん

解法１ : ループを見つけて周期性を利用する

・方針としては、ループを見つけてループ開始点までの距離と、ループの長さを調べる。
・Kがループ開始点までの距離より小さいなら愚直にやる。ループに突入するなら周期性を利用する。具体的には、( K - (ループ開始点までの距離) ) % (ループの長さ) がループ内での位置に対応する。
・以下ループを見つけるタイプの実装

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
typedef long long ll;
class Graph{
private:
  int n;// 頂点数
  int m;// 辺の数
  vector<vector<int>> edge;// 辺
  vector<int> d;
  int start;
  vector<int> rev;
  vector<int> loop;
public:
  // 頂点数_nのグラフを作成
  Graph(int _n){ n = _n; edge.resize(n);  }
  // 辺コストありのグラフ作成、_n頂点、_m辺、a[i]->b[i]の辺がある。
  Graph(int _n,int _m,vector<int> a,vector<int> b){
    n = _n;m = _m;edge.resize(n);
    rep(i,m){
      add_edge(a[i], b[i]);
      add_edge(b[i], a[i]); //無向辺
    }
  }  

  // 辺の追加 コストなし
  void add_edge(int from,int to){ edge[from].push_back(to);}

  void dfs(int v) {
    int w = edge[v][0];
    if(d[w] >= 0) {
      start = w;
      return ;
    }
    else {
      d[w] = d[v] + 1;
      rev[d[w]] = w;
      dfs(w);
    }
  }

  void dfs_loop(int v) {
    loop.push_back(v);
    int w = edge[v][0];
    if(w == start) return;
    dfs_loop(w);
  }

  
  void solve(int s,ll k){
    rev.resize(n+1);
    d.resize(n, -1);
    d[s] = 0;
    dfs(s);
    if(d[start] >= k) {
      cout << rev[k]+1 << "\n";
      return ;
    }
    dfs_loop(start);
    int num = loop.size();
    cout << loop[ (k - d[start]) % num] + 1 << "\n";
  }

  
};
int main()
{
  int n;cin >> n;
  ll k; cin >> k;
  vector<int> b(n);
  rep(i,n) {
    cin >> b[i];
    b[i]--;
  }

  
  Graph gp(n);
  rep(i,n) gp.add_edge(i, b[i]);
  gp.solve(0, k);
  
  return 0;
}

解法2 : ダブリングの利用

ダブリングとは？

・N回同じ操作を繰り返す（ex. ある数をN乗する）操作をO(logN) でやるテクニック。
・今回は、aⁿ[i] := 町i からn 回テレポートしてたどり着く町の番号、とする。
・ここで、a²ⁿ [i] はaⁿ[i] を用いて計算することができる。a²ⁿ [i] = aⁿ [ aⁿ [i] ]。
・0 <= K <= 2ⁿ を満たす任意のKは、2ⁿ までの2の冪の足し合わせで表現することができる。
・今回は、K <= 2⁶⁰ 程度なので、{ a²ⁱ | 0 <= i <= 60 } の値さえ持っておけば、任意のKにおいてa^K [i]を求めることができる。
・以下実装

#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
typedef long long ll;
int main()
{
  int n; cin >> n;
  ll k; cin >> k;
  vector<int> a(n);
  rep(i,n) {
    cin >> a[i];
    a[i]--;
  }

  int s = 0;
  while(k > 0) {
    if(k & 1) s = a[s];
    vector<int> na(n);
    rep(i,n) {
      na[i] = a[a[i]];
    }
    a = na;
    k >>= 1;
  }
  
  cout << s+1 << "\n";
  
  return 0;
}

おわりに

ダブリングの方が実装がだいぶ楽。ループ見つける方をコンテスト中にイチから実装してたら絶対バグらせてた。ありがとう、ミカミくん。