TopCoder SRM 668 Div1 Medium: WalkingToSchool

解法

そもそも0->1->0のルートが作れなければ無理である．

ルートが作れる場合，シミュレーションによって 0->0 のルートの距離をリストアップする．この距離を組み合わせて1を作ることが出来れば，ある数以上で1刻みの距離を作ることができるので，それを調べる．「組み合わせて1を作ることができる」とは，最大公約数が1であるということなので，それをとってやれば良い．

コード

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class WalkingToSchool {
	private ArrayList<Integer>[] graph;
	private final int INF = 4000;

	public String canWalkExactly(int N, int[] from, int[] to) {
		graph = new ArrayList[N];
		for (int i = 0; i < N; i++) {
			graph[i] = new ArrayList<Integer>();
		}

		int M = from.length;
		for (int i = 0; i < M; i++) {
			graph[from[i]].add(to[i]);
		}

		// そもそも0->1->0の移動が出来ない時は終了
		int[] from0 = dijkstra(0);
		int[] from1 = dijkstra(1);
		if (from0[1] == INF || from1[0] == INF) {
			return "Chores";
		}

		/*
		 * シミュレーションして0->0のループのGCDをとる． GCDが1であれば十分大きいkについて任意のk-routeを作ることができる．
		 */
		boolean[] nowOn = new boolean[N];
		nowOn[0] = true;
		int gcd = 0;
		for (int turn = 1; turn <= 10000; turn++) {
			boolean[] next = new boolean[N];
			for (int i = 0; i < M; i++) {
				if (nowOn[from[i]]) {
					next[to[i]] = true;
				}
			}
			if (next[0]) {
				gcd = gcd(gcd, turn);
			}
			nowOn = next;
		}
		return gcd == 1 ? "Freedom" : "Chores";

	}

	// ダイクストラ
	private int[] dijkstra(int start) {
		int N = graph.length;
		int[] dist = new int[N];
		Arrays.fill(dist, INF);
		dist[start] = 0;

		PriorityQueue<Edge> priorityQueue = new PriorityQueue<>();
		priorityQueue.add(new Edge(start, 0));
		while (!priorityQueue.isEmpty()) {
			Edge edge = priorityQueue.poll();
			int from = edge.to;

			if (edge.dist > dist[from]) {
				continue;
			}

			for (Integer to : graph[from]) {
				if (dist[to] > dist[from] + 1) {
					dist[to] = dist[from] + 1;
					priorityQueue.add(new Edge(to, dist[to]));
				}
			}
		}

		return dist;
	}

	private int gcd(int a, int b) {
		if (b == 0) {
			return a;
		}
		return gcd(b, a % b);
	}
}

class Edge implements Comparable<Edge> {
	int to, dist;

	public Edge(int to, int dist) {
		this.to = to;
		this.dist = dist;
	}

	@Override
	public int compareTo(Edge o) {
		return this.dist - o.dist;
	}
}