Gather the Maps! - kyoupuro @ ウィキ

2011 : Gather the Maps!

問題文

解説

バラバラの地図を完成させるために最低限掛かる日数を答える。
ここの解説が参考になる→Gather the Maps! 解説
地図の渡し方を全通り調べるのではなく、所持できる可能性のある地図を記憶していく。

プログラム

C

C++

上の解説に載っているプログラムを参考に、というかほとんどパクったもの。実行時間は0.24secだった。

...

#include <iostream>
#include <set>
using namespace std;
 
int main() {
    int n;
    while (cin >> n, n) {
        int day[51][31] = {0}, map[51][51] = {0};
        for (int i = 0; i < n; i++) {
           int a;
            cin >> a;
            for (int j = 0; j < a; j++) {
                int b;
                cin >> b;
                day[i][b] = 1;
            }
            map[i][i] = 1;
        }
 
        int flag = 0;
        for (int i = 1; i <= 30; i++) {
            set<int> now_map;
            // 現在集められる地図を全てnow_mapにぶち込む
            for (int j = 0; j < n; j++) {
                if (!day[j][i]) continue;
                for (int k = 0; k < n; k++) {
                    if (map[j][k])  now_map.insert(k);
                }
            }
         
            //　全部集められたかどうかの判定
            if (now_map.size() == n) {
                flag = 1;
                cout << i << endl;
                break;
            }
     
            // 誰がどの地図を持っているかを記憶
            for (int j = 0; j < n; j++) {
                if (!day[j][i]) { continue; }
 
                for (set<int>::iterator it = now_map.begin(); it != now_map.end(); it++) {
                    map[j][*it] = 1;
                }
            }
 
             
        }
 
        if (!flag) {
            cout << -1 << endl;
        }                        
    }
 
    return 0;
}

自力で書いたプログラム。実行時間は1.39secだった。

...

#include <iostream>
#include <set>
using namespace std;
 
int main() {
int n;
while (cin >> n, n) {
	bool man[50+1][30+1] = {false};

	for (int i = 1; i <= n; i++) {
		int f;
		cin >> f;
		for (int j = 0; j < f; j++) {
			int d;
			cin >> d;
			man[i][d] = true;
		}
	}

	set<int> s[50+1];
	for (int i = 1; i <= n; i++) {
		s[i].insert(i);
	}

	bool flag = false;

	for (int i = 1; i <= 30; i++) {
		if (flag) break;
		for (int j = 1; j <= n; j++) {
 			if (!man[j][i]) continue;
 
	 		for (int k = 1; k <= n; k++) {
				if (man[k][i]) {
					s[j].insert(s[k].begin(), s[k].end());
				}
				}
		
				if (s[j].size() == n) {
					cout << i << endl;
					flag = true;
					break;
				}
			}
		}
 
		if (!flag) cout << -1 << endl;
	}
 
	return 0;
}

Java