Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2009-10-12SRM424 DIV2, SRM423 DIV2

SRM424 DIV2 Level Three(900pt.) リベンジ

| 15:08

昨日TLEになってしまった問題の再チャレンジ。

TopSubmissionと比較したところ、私のが「優先度の高い道から選択していく」アルゴリズムでTopSubmissionのは「まず全都市をつなげてから優先度の高い道を追加していく」アルゴリズムになっていることがわかりました。確かにこの方法ならば、組み合わせを考えることなく答えを導くことができます。計算量を考慮してあらかじめアルゴリズムの青写真を描くことが重要と痛感できました。


TopSubmissionを私なりに書き換えたコードを載せておきます。

public class BestRoads {
	public int[] numberOfRoads(String[] roads, int M) {
		final int citiesNum = roads.length;
		final boolean hasRoad[][] = createFlags(roads);
		int[] result = new int[citiesNum];
		int selectedRoads = selectMinRoads(hasRoad, result);
		if (selectedRoads < citiesNum - 1) {
			// 接続不可能な都市があった
			return new int[0];
		} else if (selectedRoads == M) {
			// 既に充分な道が選択されている
			return result;
		} else {
			// まだ道を選ぶ必要があるので優先順位の高いものから順に選択する
			selectedRoads += selectMoreRoads(hasRoad, result, M - selectedRoads);
			if (selectedRoads == M) {
				return result;
			} else {
				// 道の総数がMに満たなかった
				return new int[0];
			}
		}
	}

	/**
	 * すべての都市を接続し、かつ最も優先度の高い道を最小限(街の数-1個)選択しようとする。
	 * 選択できなかった場合は戻り値が(街の数-1)よりも小さくなる。
	 * 
	 * @param hasRoad    街の間に道があるかどうかを表す2次元真偽値配列
	 * @param roadsCount 街に接続している選択した道の本数
	 * @return 選択された道の総数
	 */
	private int selectMinRoads(final boolean[][] hasRoad, final int[] roadsCount) {
		int result = 0;
		final int citiesNum = hasRoad.length;
		final boolean visited[] = new boolean[citiesNum];
		visited[0] = true;
		while (true) {
			boolean found = false;
			x: for (int i = 0; i < citiesNum; i++) {
				for (int j = 0; j < citiesNum; j++) {
					if ((visited[i] && hasRoad[i][j] && !visited[j])
							|| (!visited[i] && hasRoad[i][j] && visited[j])) {
						check(hasRoad, roadsCount, i, j);
						visited[i] = true;
						visited[j] = true;
						result++;
						found = true;
						break x;
					}
				}
			}
			if (!found) {
				break;
			}
		}
		return result;
	}

	/**
	 * 指定された数だけ優先度の高い道路を選択する。
	 * 選択できなかった場合は戻り値が(指定された数)よりも小さくなる。
	 * @param hasRoad    街の間に道があるかどうかを表す2次元真偽値配列
	 * @param roadsCount 街に接続している選択した道の本数
	 * @param needs 選択したい道の数(1以上)
	 * @return 選択した道の数
	 */
	private int selectMoreRoads(boolean[][] hasRoad, int[] roadsCount, int needs) {
		final int citiesNum = hasRoad.length;
		int count = 0;
		for (int j = 0; j < citiesNum; j++) {
			for (int k = 0; k < citiesNum; k++) {
				if (hasRoad[j][k]) {
					check(hasRoad, roadsCount, j, k);
					if (++count == needs) {
						return count;
					}
				}
			}
		}
		return count;
	}

	/**
	 * 特定の都市と都市の間にある道を選択する処理。道を再選択不可能にするとともに、
	 * 街に接続している道の本数をインクリメントする。
	 * 
	 * @param hasRoad    街の間に道があるかどうかを表す2次元真偽値配列
	 * @param roadsCount 街に接続している選択した道の本数
	 * @param cityA 選択した街の番号
	 * @param cityB 選択した街の番号
	 */
	private void check(final boolean[][] hasRoad, final int[] roadsCount,
			int cityA, int cityB) {
		++roadsCount[cityA];
		++roadsCount[cityB];
		hasRoad[cityA][cityB] = false;
		hasRoad[cityB][cityA] = false;
	}

	/**
	 * プログラム実行時に渡された文字列配列より、街の間に道があるかどうかを表す
	 * 2次元真偽値配列を生成する。
	 * 
	 * @param roads プログラム実行時に渡された文字列配列(仕様は問題文参照)
	 * @return 街の間に道があるかどうかを表す2次元真偽値配列
	 */
	private boolean[][] createFlags(String[] roads) {
		final boolean[][] result = new boolean[roads.length][roads.length];
		for (int i = 0; i < roads.length; i++) {
			for (int j = 0; j < roads.length; j++) {
				result[i][j] = roads[i].charAt(j) == 'Y';
			}
		}
		return result;
	}
}