Google Code Jam 2012 1B Equal Sums

問題

　N個の要素をもつ正の整数の集合S := {S1, S2, ... SN}が与えられる。Sの異なる任意の２つの部分集合TとUを考える。Tの要素の総和とUの要素の総和が同じになる場合、T、Uの要素を出力せよ。そのようなTとUが作れない場合は、"impossible"と出力せよ。

方針

　smallは、N=20でSの要素が10⁵程度だったから、DPで解いた。largeは、N=500でSの要素が最大で10¹²だったので、DPでは無理。乱択アルゴリズムを使ってる人が多かった。
　N=500だけど、最初の50個だけ見る。このとき作れる部分集合の個数は2⁵⁰ > 500 * 10 ¹²なので、鳩ノ巣原理から確実に衝突するペアが存在する。仮に10⁶個部分集合を作ったとすると、部分集合からペア２つを選ぶ選び方は、10¹²/2通り、一つのペアにおいて衝突が起こる確率は低く見積もっても1/10¹²なので、10⁶個の部分集合のなかで衝突するようなペアの数の期待値は、10¹²/2 * 1/10¹²でほぼ1くらいのオーダーになる。ということで適当に部分集合を生成してその和をmapで管理していれば100万個くらいループまわせばそのうち衝突するでしょう。という方針でいく。

ソースコード

　setやmapは要素数が100万くらいになると急激に遅くなる場合があるので、今回のようなケースではハッシュを使ったmapを使った方がいいと思います。以下では、boostのunordered_mapを使って実装しています。

view plainprint?

1. using namespace std;  
2.   
3. #define REP(i, n) for(int i=0; i<(int)(n); i++)  
4. #define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)  
5.   
6. int N;  
7. long long x[500];  
8.   
9. void printNums(unsigned long long use) {  
10.     bool fst = true;  
11.   
12.     REP (i, N) {  
13.         if (use & 1LL << i) {  
14.             if (fst)  
15.                 fst = false;  
16.             else  
17.                 cout << " ";  
18.             cout << x[i];  
19.         }  
20.     }  
21.     cout << endl;  
22. }  
23.   
24.   
25. void solve() {  
26.     unsigned long long use = 0;  
27.     boost::unordered_map<long long, unsigned long long> vis;  
28.   
29.     N = min(N, 50);  
30.     unsigned long long use2 = 0;  
31.     for (;;) {  
32.         use = use * 23 + 17542197;  
33.         long long sum = 0;  
34.         REP(i, N) if (use & 1LL<<i) sum += x[i];  
35.   
36.         if (sum && vis.count(sum)) {  
37.             use2 = vis[sum];  
38.             break;  
39.         }  
40.         vis[sum] = use;  
41.     }  
42.   
43.     printNums(use);  
44.     printNums(use2);  
45. }  
46.   
47. #define SUBMIT  
48. int main() {  
49. #ifdef SUBMIT  
50.     freopen("./test.in", "r", stdin);  
51.     freopen("./test.out", "w", stdout);  
52. #endif  
53.   
54.     int T;  
55.     cin >> T;  
56.     REP(t, T) {  
57.         cout << "Case #" << t+1 << ":" << endl;  
58.         cerr << "Case #" << t+1 << ":" << endl;  
59.   
60.         cin >> N;  
61.         REP(i, N) cin >> x[i];  
62.         solve();  
63.     }  
64.   
65. #ifdef SUBMIT  
66.     fflush(stdout);  
67.     cerr << "all done!" << endl;  
68. #endif  
69.     return 0;  
70. }  

using namespace std;

#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)

int N;
long long x[500];

void printNums(unsigned long long use) {
    bool fst = true;

    REP (i, N) {
        if (use & 1LL << i) {
            if (fst)
                fst = false;
            else
                cout << " ";
            cout << x[i];
        }
    }
    cout << endl;
}


void solve() {
    unsigned long long use = 0;
    boost::unordered_map<long long, unsigned long long> vis;

    N = min(N, 50);
    unsigned long long use2 = 0;
    for (;;) {
        use = use * 23 + 17542197;
        long long sum = 0;
        REP(i, N) if (use & 1LL<<i) sum += x[i];

        if (sum && vis.count(sum)) {
            use2 = vis[sum];
            break;
        }
        vis[sum] = use;
    }

    printNums(use);
    printNums(use2);
}

#define SUBMIT
int main() {
#ifdef SUBMIT
    freopen("./test.in", "r", stdin);
    freopen("./test.out", "w", stdout);
#endif

    int T;
    cin >> T;
    REP(t, T) {
        cout << "Case #" << t+1 << ":" << endl;
        cerr << "Case #" << t+1 << ":" << endl;

        cin >> N;
        REP(i, N) cin >> x[i];
        solve();
    }

#ifdef SUBMIT
    fflush(stdout);
    cerr << "all done!" << endl;
#endif
    return 0;
}