このテクは他で使えるところもあるかもなぁ。
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の置き換えのテクニックは使えるようにしておきたい。