yukicoder : No.1726 [Cherry 3rd Tune B] ジャマイカビアポン

こちらは割とすんなりだった。
https://yukicoder.me/problems/no/1726

問題

2次元座標中でM個のピンポン玉の落下地点と、各ピンポン玉のスコアが与えられる。
また、それとは別にN個のコップの位置が与えられる。

これからピンポン玉を一斉に落とすので、もし同じ座標にコップが存在する場合、ピンポン玉に相当するスコアが得られる。
その際、ピンポン玉を落とす前に、以下の処理を行える。

• Y軸に平行な任意の直線に対し、全コップを同時に対称の位置に移動する
• X軸に平行な任意の直線に対し、全コップを同時に対称の位置に移動する

得られる最高スコアを求めよ。

解法

コップについて、平行な直線を2本使えば平行移動ができることがわかる。
そこで、Y軸及びX軸における反転の有無4通りに対し、それぞれコップをどう移動させるとスコアが最大になるかを考えよう。
i番のピンポン玉をj番のコップに入れることを考えると、必要な平行移動量が求まる。
そこで、全ピンポン玉：コップの組み合わせに対し、平行移動量を求めよう。

同じ平行移動量の組み合わせについては、そのピンポン玉：コップの組み合わせは同時に達成できることになる。
そこで、平行移動量毎にスコアの総和を求め、最大値を求めよう。

int N,M;
int P[808];
int X[808],Y[808];
int S[808],T[808];

unordered_map<ll,ll> C;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>P[i];
	FOR(i,N) cin>>X[i]>>Y[i];
	FOR(i,M) cin>>S[i]>>T[i];
	ll ma=0;
	FOR(k,4) {
		if(k==2) {
			FOR(i,M) S[i]=-S[i];
		}
		if(k==1||k==3) {
			FOR(i,M) T[i]=-T[i];
		}
		C.clear();
		FOR(x,N) FOR(y,M) {
			i=X[x]-S[y];
			j=Y[x]-T[y];
			ll a=(((ll)i)<<31)+j;
			C[a]+=P[x];
		}
		FORR2(a,b,C) ma=max(ma,b);
	}
	cout<<ma<<endl;
}

まとめ

ビールの設定は何だったんだろう。