kmjp's blog

競技プログラミング参加記です

TopCoder SRM 606 Div1 Medium EllysPairing

1発正解ならず。
http://community.topcoder.com/stat?c=problem_statement&pm=11036

問題

N個の大学の生徒が集まっている。
生徒の名前は2の累乗である整数Mに対し、0~(M-1)のM通りある。

各大学にはcount[i]人の生徒がおり、最初の生徒の名前はfirst[i]である。
各大学で、名前がxの生徒の次の生徒の名前は、(x*mul[i]+add[i]) % M である。

全大学合計で(count[i]の総和)人の生徒で、2人組を作りたい。所属する大学は同じでも異なっていても良い。
この時、同じ名前の生徒を組にすることはできない。
最大で2人組を何組作れるか。

解法

同じ名前の生徒が全大学で過半数を占めていなければ、全生徒の半分の数の2人組を作れる。
全生徒数をMとしたとき、生徒を名前順にソートしてi番とi+M/2番の生徒で組ませれば、2人の名前は異なるためである。

過半数を占める名前の生徒がいた場合、その名前の生徒と、他の名前の生徒を組ませることで、他の名前の生徒の数だけ2人組を作ることができる。

よって、あとは過半数を占める名前の有無とその人数を調べることである。
残念ながらMは最大2^30で、メモリは16MBしかないので全部の名前の数を覚えることはできない。
メモリを絞って頻度の多い名前だけを覚えることにする。

全体で過半数を占める名前なら、どこか1つ以上の大学で過半数を占めるはずである。
よって、各大学内で過半数となる名前を探すとその候補は最大N個になる。
あとは全大学の生徒の名前のうち、それた過半数の可能性のある名前をカウントすればよい。

最初各大学で過半数を占める数を数えるさい、全部の名前を列挙してカウントするとやはり16MBに収まらないので、先頭1000個だけ生成することにした。
first=1、mult=2だったりすると、M=2^30の時31人目以降ずっと名前が0になったりするので、30個の倍以上は生成しておくと良い。

class EllysPairing {
	public:
	int getMax(int M, vector <int> count, vector <int> first, vector <int> mult, vector <int> add) {
		int N=first.size();
		int i,x,y,tot=0;
		map<int,int> cand;
		
		FOR(i,N) tot+=count[i];
		FOR(i,N) {
			map<int,int> MM;
			int tt=first[i];
			MM[(int)tt]++;
			FOR(x,min(count[i]-1,1000)) {
				tt=(tt*mult[i]+add[i])&(M-1);
				MM[(int)tt]++;
			}
			int ma=0;
			ITR(it,MM) ma=max(ma,it->second);
			ITR(it,MM) if(ma==it->second && ma>=min(count[i],1000)/2-1) cand[it->first]=0;
		}
		
		FOR(i,N) {
			int tt=first[i];
			if(cand.find(tt)!=cand.end()) cand[tt]++;
			FOR(x,count[i]-1) {
				tt=(tt*mult[i]+add[i])&(M-1);
				if(cand.find(tt)!=cand.end()) cand[tt]++;
			}
		}
		
		int ma=0;
		ITR(it,cand) ma=max(ma,it->second);
		return min(tot/2,(tot-ma));
	}
};

まとめ

最初各大学で全部名前を生成して過半数の候補を探したらTLEした。
1M要素のsetやmapを考えなしに扱ってはダメだね。