読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 525 Div1 Medium: Rumor

解法

Aだけ知っているときはAを,Bだけ知っているときはBを自分の仲間全員に伝えたほうが良い.両方知っている場合は先にどちらかを全員に伝えることになるが,どちらを先にするかはbitmaskで管理して全探索する.

コード

import java.util.Arrays;

public class Rumor {

	public int getMinimum(String knowledge, String[] graph) {
		int N = knowledge.length();
		boolean[][] map = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = graph[i].charAt(j) == 'Y';
			}
		}

		int min = N * 2;
		for (int mask = 0; mask < (1 << N); mask++) {
			/*
			 * ABの片方しか知らないウサギは知っている方を広めれば良い。 両方知っているウサギはどちらを伝えるべきか迷うので,
			 * Aを優先的に伝える場合、Bを優先的に伝える場合で総当りする
			 */
			int[] know = new int[N];
			int[] sent = new int[N];
			for (int j = 0; j < N; j++) {
				if (knowledge.charAt(j) == 'Y') {
					know[j] = 3;
				}
			}

			// シミュレーション
			for (int day = 0; day < min; day++) {
				// 終わっているかどうか
				boolean end = true;
				for (int j = 0; j < N; j++) {
					if (know[j] != 3) {
						end = false;
					}
				}
				if (end) {
					min = day;
					break;
				}

				int[] next = Arrays.copyOf(know, N);
				for (int j = 0; j < N; j++) {
					if (know[j] == 3) {
						// jが既に2つとも知っている場合
						if (sent[j] == 3) {
							// 特に話すこともないので何もしない
							continue;
						}
						int s;
						if (sent[j] == 0) {
							// jがAとBどちらを優先的に広めるかをmaskから取り出す
							s = ((mask >> j) & 1) == 0 ? 1 : 2;
						} else if (sent[j] == 1) {
							// Aについて広め終わっていれば、Bについて話す
							s = 2;
						} else {
							// Bについて広め終わっていれば、Aについて話す
							s = 1;
						}

						// 選んだ方をできるだけ広める
						for (int k = 0; k < N; k++) {
							if (map[j][k]) {
								next[k] |= s;
							}
						}
						sent[j] |= s;
					} else if (know[j] == 1) {
						// jがAだけ知っている場合
						// 知り合い全員にAを広める
						int s = 1;
						for (int k = 0; k < N; k++) {
							if (map[j][k]) {
								next[k] |= s;
							}
						}
						// Aを広められるだけ広めたので、jは2度にAついて話さない
						sent[j] |= s;
					} else if (know[j] == 2) {
						// jがBだけ知っている場合
						// 知り合い全員にBを広める
						int s = 2;
						for (int k = 0; k < N; k++) {
							if (map[j][k]) {
								next[k] |= s;
							}
						}
						// Bを広められるだけ広めたので、jは2度にBついて話さない
						sent[j] |= s;
					}
				}
				know = next;
			}
		}
		if (min == N * 2)
			return -1;
		return min;
	}
}