yukicoder : No.1060 素敵な宝箱

後半がえらく難しかった回。
https://yukicoder.me/problems/no/1060

問題

N個の箱があり、それぞれM種類の宝石がいくつか入っている。
これらの箱を2人で交互に1つずつ選択し、中の宝石を取得する、ということを行う。
最終的なスコアは、同種の宝石数の2乗和である。
両者(自分のスコア-相手のスコア)を最大化しようと選択したとき、(先手のスコア-後手のスコア)の最終的な値を求めよ。

解法

スコア自体は2乗和で扱いにくいので、スコアの差を見てみる。
ある宝石が合計でC個あって、先手がx個取ったとすると、スコアの差はx^2-(C-x)^2=2Cx-C^2である。
となると、結局1個当たりのスコアへの寄与は固定で2Cと考えることができる。

後は、各箱について、この値の総和の大きい順に取るようにすればよい。

int H,W;
int A[303][303],S[303];
int vis[303];
int C[2][303];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) {
		cin>>A[y][x];
		S[x]+=A[y][x];
	}
	
	FOR(y,H) {
		int tar=-1;
		int ma=-1<<30;
		FOR(x,H) if(vis[x]==0) {
			int add=0;
			FOR(i,W) add+=2*S[i]*A[x][i];
			if(add>ma) ma=add, tar=x;
		}
		
		vis[tar]=1;
		FOR(x,W) C[y%2][x]+=A[tar][x];
	}
	
	ll ret=0;
	FOR(y,2) {
		FOR(x,W) {
			ret+=C[y][x]*C[y][x]*((y==0)?1:-1);
		}
	}
	cout<<ret<<endl;
		
	
	
}

まとめ

差を取るのは、まぁこれしかないだろうなという感じであまり迷わなかった。