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; } }