Codeforces Global Round 19 : E. Best Pair

6完でもこの順位か…。
https://codeforces.com/contest/1637/problem/E

問題

N要素の整数列Aが与えられる。
C(x)を、Aにおけるxの頻度とする。
f(x,y)=(x+y)*(C(x)+C(y))とするとき、f(x,y)の最大値を求めよ。
ただし、(x,y)の組のうち取ってはいけないペアが与えられるので、それ以外の範囲で求めよ。

解法

頻度は高々O(√N)通りしかない。
そこで、C(x)が同じものをまとめて扱おう。
C(x)が固定されれば、y*(C(x)+C(y))の大小順は決まるので、各xに対し、取ってはいけないペアとならない最大のyを容易に求められる。

int T,N,M;
ll A[303030],X[303030],Y[303030];
set<pair<int,int>> NG;
vector<int> CP[303030];
vector<int> cand;
map<int,int> C;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&N,&M);
		C.clear();
		
		FOR(i,N) {
			scanf("%d",&x);
			C[x]++;
		}
		
		cand.clear();
		NG.clear();
		FOR(i,M) {
			scanf("%d%d",&x,&y);
			NG.insert({min(x,y),max(x,y)});
		}
		FORR2(a,b,C) {
			CP[b].push_back(a);
			cand.push_back(b);
			NG.insert({a,a});
		}
		
		sort(ALL(cand));
		cand.erase(unique(ALL(cand)),cand.end());
		ll ret=0;
		
		FORR2(a,b,C) {
			FORR(c,cand) {
				int R=CP[c].size()-1;
				while(R>=0&&NG.count({min(a,CP[c][R]),max(a,CP[c][R])})) R--;
				if(R>=0) ret=max(ret,1LL*(b+c)*(a+CP[c][R]));
			}
		}
		
		cout<<ret<<endl;
		FORR2(a,b,C) {
			CP[b].clear();
		}
	}
}

まとめ

割と手間取ってるな…。