TopCoder SRM 670 Div1 Medium: Treestrat

解法

ワーシャルフロイトで2点間の距離を出しておく。

Aの各コマa_iについて、以下の操作によってゲームを終わらせるのに必要なターン数を出す。

• 必要なターン数movesを固定する。
• a_i からmoves以内で行けて、かつ、Bの全ての駒がmoves以内で行けない頂点を探す。
  • このような頂点が1つでもあれば、moves以内でゲームを終わらせることは出来ない。
• そのような頂点が存在しなくなるまでmovesを増やす。これがa_iを捕まえてゲームを終わらせるのに必要なターン数である。

これらのターン数が最小値の駒を狙えば良いので、それを返せば良い。

コード

import java.util.Arrays;

public class Treestrat {

    private final int INF = (int) 1e8;

    public int roundcnt(int[] tree, int[] A, int[] B) {
	// グラフの初期化
	int N = tree.length + 1;
	int[][] graph = new int[N][N];
	for (int i = 0; i < N; i++) {
	    Arrays.fill(graph[i], INF);
	    graph[i][i] = 0;
	}

	// ワーシャルフロイト
	for (int i = 0; i < tree.length; i++) {
	    graph[tree[i]][i + 1] = graph[i + 1][tree[i]] = 1;
	}
	for (int k = 0; k < N; k++) {
	    for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
		    graph[i][j] = Math.min(graph[i][j], graph[i][k]
			    + graph[k][j]);
		}
	    }
	}

	int min = INF;
	for (int a : A) {
	    int moves = 0;
	    while (true) {
		// movesしか動かせない時に助かる頂点が存在するかどうか
		boolean existSafety = false;
		for (int safetyVertex = 0; safetyVertex < N; safetyVertex++) {
		    boolean notLose = graph[a][safetyVertex] <= moves;
		    for (int b : B) {
			notLose = notLose && graph[b][safetyVertex] > moves;
		    }
		    if (notLose) {
			existSafety = true;
			break;
		    }
		}
		if (!existSafety) {
		    break;
		}
		moves++;
	    }
	    min = Math.min(min, moves);
	}
	return min;
    }

}