kmjp's blog

競技プログラミング参加記です

yukicoder : No.1919 Many Monster Battles

このテクは他で使えるところもあるかもなぁ。
https://yukicoder.me/problems/no/1919

問題

N*Nのマス目があり、2人のプレイヤーAlice,Bobがそれぞれモンスターを1対ずつ置く。
整数列A,Bを用いて、

  • Aliceがマス(r,c)に置くモンスターの能力は|A[r]-A[c]|
  • Bobがマス(r,c)に置くモンスターの能力は|B[r]-B[c]|

各マスにおいて、能力値が高い方のモンスターのみ残る。
能力値が同等の場合、両者とも消滅する。
両者残されたモンスターの能力値の総和を求めよ。

解法

あるマスにおいてAliceが置いたモンスターの能力をX、Bobが置いたモンスターの能力をYとする。
X>YであるXの総和を取りたい。
これを再現するためには、十分大きな整数Mを使い
max( (M+1)X,MY)-max(MX,MY)をとると、X≧Yの時X、そうでないとき0が返る。
もう少し変形してmax(X,Y)-(max(MX,(M+1)Y)-max(MX,MY) )=max( (M+1)X,(M+1)Y)-max(MX,(M+1)Y)を取ると、X>Yの時X、そうでないとき0が返る。

S_ij=|Pi-Pj|、T_ij=|Qi-Qj|である数列に対し、sum(max(S_ij,T_ij))を取ることを考えると、カッコ内は
max(S_ij,T_ij)=(|(P_i-Q_i)-(P_j-Q_j)|+|(P_i+Q_i)-(P_j+Q_j)|)/2となるので、U_i=P_i-Q_i、V_i=P_i+Q_iを考えると、UとVそれぞれ昇順にソートすればsum(max(S_ij,T_ij) )を取ることができる。

max( (M+1)X,(M+1)Y)-max(MX,(M+1)Y)の総和はいずれも上記sum(max(S_ij,T_ij) )の形で表現できるので、上記手順でX>YであるXの総和を計算できる。

int N;
vector<ll> A,B,MA,MB,M1A,M1B;
const ll mo=1000000007;
const ll M=1000000000;

ll hoge(vector<ll> A,vector<ll> B) {
	vector<ll> X,Y;
	int i;
	FOR(i,A.size()) {
		X.push_back(A[i]+B[i]);
		Y.push_back(A[i]-B[i]);
	}
	sort(ALL(X));
	sort(ALL(Y));
	ll ret=0;
	int num=0;
	ll sum=0;
	FORR(x,X) {
		x=(x%mo+mo)%mo;
		(ret+=num*x-sum)%=mo;
		(sum+=x)%=mo;
		num++;
	}
	num=sum=0;
	FORR(x,Y) {
		x=(x%mo+mo)%mo;
		(ret+=num*x-sum)%=mo;
		(sum+=x)%=mo;
		num++;
	}
	return (ret%mo+mo)%mo;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		MA.push_back(M*x);
		M1A.push_back((M+1)*x);
	}
	FOR(i,N) {
		cin>>x;
		MB.push_back(M*x);
		M1B.push_back((M+1)*x);
	}
	cout<<(hoge(M1A,M1B)-hoge(MA,M1B)+mo)%mo<<" "<<(hoge(M1A,M1B)-hoge(M1A,MB)+mo)%mo<<endl;
}

まとめ

このmaxの置き換えのテクニックは使えるようにしておきたい。