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