SRM 606 DIV1 Middle - EllysPairing （復習○）
問題
ペアプログラミングのコンテストを開催する。各大学から複数の参加者がおり、２人組みのペアを作る。
ペアを作るにあたってどの大学のペアかは関係ないが、同じ名前のもの同士がペアを組まないようにしたい。
各大学iについて、参加者がcount[i]、一人目の名前がfirst[i]、
二人目以降の名前は(first[i]+mult[i]+add[i])%Mとなる。
このとき、最大となるペア数を求める。
解き方
名前の数は10^9となり配列に保存できない。
参加者数は5*10^7となりこちらも配列に保存できないので、メモリを確保できない。
そのため、うまくメモリを使う方法を考える必要がある。
今回、同じ名前が過半数を超えなければ、参加者数／２がペア数になることがわかる。
そのため、過半数となる名前が存在するかどうかを判定するとよい。
過半数となる人が存在する可能性があるかどうかを判定するアルゴリズムは、ボイヤー・ムーア法を参考にさせていただきました。
一度回しただけではその人が過半数となる可能性があるだけで必ず過半数をとっているわけではないので、一度判定し、その後数を数えて確かめる必要がある。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class EllysPairing {
public: int getMax(int M, vector<int> count, vector<int> first, vector<int> mult, vector<int> add) {
int n=count.size();
int sum=0,majority=-1,cnt=0;
long long x=-1;
FORE(i,0,n){
sum+=count[i];
FORE(j,0,count[i]){
if(j==0)x=first[i];
else x=(x*mult[i]+add[i])&(M-1);
if(majority==x){
cnt++;
}
else if(majority==-1){
majority=x;
cnt=1;
}
else{
cnt--;
if(cnt==0)majority=-1;
}
}
}
cnt=0;
FORE(i,0,n){
FORE(j,0,count[i]){
if(j==0)x=first[i];
else x=(x*mult[i]+add[i])&(M-1);
if(x==majority)cnt++;
}
}
return min(sum/2,sum-cnt);
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class EllysPairing {
public: int getMax(int M, vector<int> count, vector<int> first, vector<int> mult, vector<int> add) {
int n=count.size();
int sum=0,majority=-1,cnt=0;
long long x=-1;
FORE(i,0,n){
sum+=count[i];
FORE(j,0,count[i]){
if(j==0)x=first[i];
else x=(x*mult[i]+add[i])&(M-1);
if(majority==x){
cnt++;
}
else if(majority==-1){
majority=x;
cnt=1;
}
else{
cnt--;
if(cnt==0)majority=-1;
}
}
}
cnt=0;
FORE(i,0,n){
FORE(j,0,count[i]){
if(j==0)x=first[i];
else x=(x*mult[i]+add[i])&(M-1);
if(x==majority)cnt++;
}
}
return min(sum/2,sum-cnt);
}
};
