AtCoderBeginnerContest030 D へんてこ辞書 （メモ用）

問題

abc030.contest.atcoder.jp

考え

単語を調べるステップ数kが(1 ≦ k ≦ 10^100000)の範囲なので、long型でも収まらない。だけど今回は公式の解説でもあるように多倍長を使わずに解ける。
参考：AtCoder Beginner Contest 030 解説

• 一度調べた単語をもう一度調べるということは、また同じ単語を繰り返し調べ始めるということ。

• つまり調べる単語を頂点とし、単語間の参照関係を辺にすると、同じ単語を繰り返し調べ始めるということはグラフとして「閉路」が発生するということ。

• ステップ数kが辞書内の単語の数Nより大きい場合は必ず閉路が発生し、全ステップ終了時には閉路内に到達しているということ。もちろん閉路が存在しない場合もある。

• 閉路に到達するまでの単語の個数Tと閉路内の単語の個数Cを求めておく。

import java.util.*;
public class Main
{
	Scanner cin = new Scanner(System.in);
	//http://abc030.contest.atcoder.jp/tasks/abc030_d
	int N,A;
	String K;
	int[] B;
	public void solve()
	{
		N = cin.nextInt();
		A = cin.nextInt() - 1;
		K = cin.next();
		B = new int[N];
		for(int i = 0;i < N;i++)
		{
                        //0-indexedに合わせる
			B[i] = cin.nextInt() - 1;
		}
                //閉路に到達するまでの単語と閉路内の単語を格納する
		ArrayList<Integer> list = new ArrayList<Integer>();
                //閉路に到達するまでの単語の数
		int preLength = 0;

		int next = A;
		boolean[] used = new boolean[N];
                //シュミレーションをして実際に単語をたどっていく
		for(int i = 0;i < N;i++)
		{
			if(used[next])
			{
				for(int j = 0;j < list.size();j++)
				{
					if(list.get(j) == next)
					{
						preLength = j;
						break;
					}
				}
				break;
			}else
			{
				list.add(next);
				used[next] = true;
				next = B[next];
			}
		}
		int mod = 0;
                //ステップ数kが全単語の個数Nより大きいかどうかのフラグ
		boolean f = false;
		for(int i = 0;i < K.length();i++)
		{
			mod = (mod * 10 + K.charAt(i) - '0');
　　　　　　　　　　　　//全単語の個数より現在のステップ数が大きい場合
			if(mod > N)
			{
                                 //現在のステップ数を閉路内の単語の個数で割ったあまりを現在のステップ数とする
				 mod %= (list.size() - preLength);
				 f = true;
			}
		}
                //ステップ数kが全単語の個数Nより大きい場合
		if(f)
		{
			int add = 0;
                        //閉路内の単語の個数を足していく
                        //あらかじめ閉路内の単語の個数で割っているので、足していっても最終的に到達する単語は変わらない
			while(add < N)add += (list.size() - preLength);
			mod += add;
		}
		next = A;
                //再度シュミレーションで最終的に到達する単語を求める
		for(int i = 0;i < mod;i++)
		{
			next = B[next];
		}
		System.out.println(next + 1);
	}
	public static void main(String[] args)
	{
		new Main().solve();
	}
}