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を使って実装しています。

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