問題
N個の要素をもつ正の整数の集合S := {S1, S2, ... SN}が与えられる。Sの異なる任意の2つの部分集合TとUを考える。Tの要素の総和とUの要素の総和が同じになる場合、T、Uの要素を出力せよ。そのようなTとUが作れない場合は、"impossible"と出力せよ。
方針
smallは、N=20でSの要素が105程度だったから、DPで解いた。largeは、N=500でSの要素が最大で1012だったので、DPでは無理。乱択アルゴリズムを使ってる人が多かった。
N=500だけど、最初の50個だけ見る。このとき作れる部分集合の個数は250 > 500 * 10 12なので、鳩ノ巣原理から確実に衝突するペアが存在する。仮に106個部分集合を作ったとすると、部分集合からペア2つを選ぶ選び方は、1012/2通り、一つのペアにおいて衝突が起こる確率は低く見積もっても1/1012なので、106個の部分集合のなかで衝突するようなペアの数の期待値は、1012/2 * 1/1012でほぼ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; }
0 件のコメント:
コメントを投稿