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を考えなしに扱ってはダメだね。