はじめに
どうも、yoshiki_utakata です。今回はAOJ 2011: Gather the Maps!を解きました。
いきなり今回の反省点からなのですが、全探索で解ける問題は全探索で解いた方がいい*1 、ということです。もっと言ってしまうと、全探索で解ける規模の問題は全探索でしか解けないことを疑ってかかったほうがいいということです。
Union-Find Tree ではダメ
この問題、前にも解いたことある感じがしていました。 記録上解いてないことになってたので解いてないわけなのですが。
この問題を見たとき、ぱっと思いついたのは、Union-Find Treeで予定の合う人をグルーピングしていく方法です。しかし、これではダメでした。おそらく昔にもこれで解こうとしてダメだったから解いてなかったんでしょうね。
なぜダメなのか。
A,B,C,Dの4人がいたとします。以下のような状況であったとします
- 1日目: AとBの予定が合いました
- 2日目: BとCの予定が合いました
- 3日目: AとDの予定が合いました
Union-Find Treeを使って集合にまとめていくと以下のようになります。
- 1日目:
{A, B}, {C}, {D} - 2日目:
{A, B, C}, {D} - 3日目:
{A, B, C, D}
ということは、3日目ですべての地図の断片が集まる…かとおもいきや、そうではありません！
- 1日目でAがBに地図を渡す
- 2日目にBがCに地図を渡す。ここでCが地図を3枚持っていることになる
- 3日目、DとAが合うが、Aは地図を渡してしまっているので、ここでは地図は集まらない！
じゃあ1日目の挙動を変えてみても、今度はBの地図が集まってこないですね。参照渡しでなく値渡しなので、これはUnion-Findではないのです！（わかりづらい）
つまるところ、この問題は全探索するしかありません。1日目が終わった時点で、誰がどの地図を持つことができるかを記録し、誰か一人でも全部の地図を持てるようになった時点で終了です。
実装
class Main { public static void main(String[] args) throws Exception{ Scanner sc = new Scanner(new InputStreamReader(System.in)); while(true){ int n = sc.nextInt(); if(n == 0) break; boolean[][] schedule = new boolean[n][30]; for(int i = 0; i < n; i++){ int m = sc.nextInt(); for (int j = 0; j < m; j++) { schedule[i][sc.nextInt() - 1] = true; } } System.out.println(solve(n, schedule)); } } static int solve(int n, boolean[][] schedule){ boolean[][] canHave = new boolean[n][n]; for (int i = 0; i < n; i++) { canHave[i][i] = true; } for (int day = 0; day < 30; day++) { // day日にaさんとbさんの予定が合う場合は地図を交換できる for (int a = 0; a < n; a++) { for (int b = 0; b < a; b++) { if(schedule[a][day] && schedule[b][day]){ // 地図をシェアする share(n, canHave, a, b); } } } // 地図は集まったかどうかをチェックする if(check(n, canHave)){ return day + 1; } } return -1; } static void share(int n, boolean[][] canHave, int a, int b){ for (int i = 0; i < n; i++) { boolean tmp = canHave[a][i] || canHave[b][i]; canHave[a][i] = tmp; canHave[b][i] = tmp; } } /** * 誰か一人でも、地図を全部集められる人がいたらtrue */ static boolean check(int n, boolean[][] canHave){ for (int person = 0; person < n; person++) { if(check(n, person, canHave)) return true; } return false; } /** * person番目の人が地図を全部集められるならtrue */ static boolean check(int n, int person, boolean[][] canHave){ for (int i = 0; i < n; i++) { if(!canHave[person][i]) return false; } return true; } }
結論
全探索で解ける規模の問題は全探索でしか解けないことを疑ってかかったほうがいい
*1:最強最速アルゴリズマー養成講座でchokudaiさんも似たようなことを言っていました。バグや漏れが出にくい解法を選んだほうがいいと。
