yukicoder : No.3292 World Map Distance

これはすんなりだった。
https://yukicoder.me/problems/no/3292

問題

トーラス状に上下と左右が隣接しているH*Wのグリッドが与えられる。
そのうちN個のマスが目的地であり、その座標が与えられる。
任意のセルから、各点に至る最短マンハッタン距離の総和を考える。
その値の最大値を求めよ。

解法

マンハッタン距離の総和なので、行方向と列方向を別々に考え、和を取ればよい。
以下行方向について考える。

開始位置の行の候補と、目的地がある行から最も遠い行である。
よってそのような行を総当たりしよう。
開始位置から目的地に至るには、上移動が近い場合と下移動が近い場合があるが、あらかじめN点の行番号をソートし、その累積和をもっておけば、ソートの前処理O(NlogN)、開始位置毎の処理がO(logN) (尺取り法を使えば均しでO(N))で解ける。

int N;
ll X,Y;
vector<ll> Xs,Ys;

ll hoge(vector<ll> P,ll L) {
	int i;
	vector<ll> cand;
	vector<ll> S={0};
	sort(ALL(P));
	FOR(i,N) {
		cand.push_back(P[i]-L/2);
		cand.push_back(P[i]+L/2);
		P.push_back(P[i]+L);
	}
	FOR(i,2*N) S.push_back(S.back()+P[i]);
	ll ret=-1;
	FORR(c,cand) {
		if(c-L/2<=0) c+=L;
		if(c+L/2>=2*L) c-=L;
		ll PL,PR;
		if(L%2) {
			PL=c-L/2;
			PR=c+L/2;
		}
		else {
			PL=c-L/2;
			PR=c+L/2-1;
		}
		ll sum=0;
		{
			int a=lower_bound(ALL(P),PL)-P.begin();
			int b=lower_bound(ALL(P),c)-P.begin();
			sum+=c*(b-a)-(S[b]-S[a]);
		}
		{
			int a=lower_bound(ALL(P),c+1)-P.begin();
			int b=lower_bound(ALL(P),PR+1)-P.begin();
			sum+=(S[b]-S[a])-c*(b-a);
		}
		ret=max(ret,sum);
	}
	return ret;
		
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>Y;
	FOR(i,N) {
		cin>>x>>y;
		Xs.push_back(x-1);
		Ys.push_back(y-1);
	}
	ll ret=hoge(Xs,X)+hoge(Ys,Y);
	cout<<ret<<endl;
}

まとめ

典型問題かな。