TopCoder SRM 606 Div1 Medium EllysPairing
問題
世の中にはM種類の名前がある。
n個の大学があって、i番目の大学にはcount[i]人の生徒がパーティに参加する。
i番目の大学の人の名前は、一人目がfirst[i],
二人目以降は(前の人の名前) * mul[i] + add[i] mod Mという風に生成する。
パーティでは、同じ名前の人がペアを組んではいけない。(大学は関係ない)
このとき、最大でいくつのペアが作れるか、答えよ。
制約条件
Mは2のべき乗であることが保証されている
1≦M≦1,073,741,824
大学の数≦50
count[i]≦100000
方針
一種類の名前が半数を超えるだけいたら、明らかに全員分のペアが作れない。
逆に全ての名前が半数を超えないとする。
このとき、貪欲に一番多い名前の人 + 二番目に多い名前の人のペアを作ると、
(1番多い人の数) * 2≦(会場の人数)だったので、この二人を取り除くと、
(1番多い人の数 - 1) * 2 ≦(会場の人数 - 2)という式がまた成り立っている。
すなわち、このように貪欲にとっていけば残りが0人(奇数の場合は1人あまる)まで必ずペアが作れることになる。
なので、一番多い名前が半数を超えないかどうかを見ればよい。
で、人が5000万人もいるので、愚直に数えるのは空間計算量的に無理。
自分は乱択で10000人取り出した。
で、その中で多い候補二つについてだけ、その人数を真面目に数えた。
(最初一番多い候補だけ数えたら、一番目と二番目がほぼ同数のときに落ちて酷かった。同数に近い場合があるので二つの候補について数えないとだめ)
....
で、忘れていたのだけど、実は数列の過半数があるかを空間計算量O(1)で計算する方法があった。
まず最初の数aを覚える。出てきた回数cも覚える。最初c = 1
で、二番目以降の数で、aがもう一度出てきたらc = c + 1
aじゃない数が出てきたらc = c - 1
c == 0のときに次の数を見たら、aをその数に変更してc = 1とする。
というアルゴリズムを実行すると、過半数が存在するときは、aは必ずその数になっている。
(存在しないときは、一番多いものになっているわけではない)
のでそのaだけ調べればいい。これはとっても実装楽。
ソースコード
class EllysPairing { public: int getMax(int M, vector <int> count, vector <int> first, vector <int> mult, vector <int> add) { int n = count.size(); ll tot = accumulate(all(count), 0ll); map<int, int> sample; rep(i, n){ ll d = first[i]; rep(j, count[i]){ if(xor128() % 131072 * tot <= (ll)10000 * 131072) sample[d]++; d = (d * mult[i] + add[i]) & (M - 1); } } vector<pi> cands; vi cnt(2); each(i, sample) cands.pb(mp(-i->second, i->first)); sort(all(cands)); int check = min(2, (int)cands.size()); rep(i, n){ ll d = first[i]; rep(j, count[i]){ rep(k, check) if(d == cands[k].second) cnt[k]++; d = (d * mult[i] + add[i]) & (M - 1); } } if(max(cnt[0], cnt[1]) * 2 <= tot) return tot / 2; return tot - max(cnt[0], cnt[1]); } };