全国統一プログラミング王決定戦本戦 C - Come Together

C - Come Together

概要

H * Wマスのすべてのマスに1個ずつコマが置いてある。そこからK個のコマを取り除く。
その後全てのコマについて、縦または横に隣接したマスに動かす操作を繰り返し、ある1マスにコマを集めることを考える。
このとき、最小の操作回数を求めよ。

制約

1 <= H, W <= 10^5
1 <= K <= min(10^5, H * W - 1)

方針

コマを集めるマスを固定したとき、最小の操作回数は
①全てのコマについて、コマのマスと集めるマスとのマンハッタン距離の合計
②取り除くコマについて、コマのマスと集めるマスとのマンハッタン距離の合計
としたとき、①-②で求めることが出来る。

まず、コマを集めるマスを考える。
あるマスにコマを集めるとし、さらに集めるマスを隣接したマスに動かすことを考える。
このとき、各マスの集めるマスの変化によるマンハッタン距離の増減は下記の通り。
例：3 * 4マス、集めるマスが(2, 2)→(3, 2)に変化したときの各マスのマンハッタン距離の増減

1	1	1	1
1	1	1	1
-1	-1	-1	-1

(1, 2行目のマスは集めるマスが遠くなるのでマンハッタン距離が+1、3行目のマスは集めるマスが近くなるのでマンハッタン距離が-1)
コマを取り除いた場合も同様である。

よって、行・列ごとに、1行目・1列目からスタートして上記の「マンハッタン距離の増減」の合計が減少しなくなるまで動かせば集めるマスを求めることが出来る。

①・②のマンハッタン距離の合計について。
①は行成分と列成分にそれぞれ分けて合計すると制約をクリアできる。
例：3 * 4マス、集めるマスは(2, 2)

1	1	1	1
0	0	0	0
1	1	1	1

（行成分を合計→(1+0+1) * 4）

1	0	1	2
1	0	1	2
1	0	1	2

（列成分を合計→(1+0+1+2) * 3）

2	1	2	3
1	0	1	2
2	1	2	3

（上記2つの合計、(2, 2)からのマンハッタン距離になっている）

②はそれぞれの取り除くマスについて、集めるマスとのマンハッタン距離を計算し、合計すればよい。

解答

Submission #4308541 - 全国統一プログラミング王決定戦本戦

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll H, W, K;
	cin >> H >> W >> K;
 
	vector<ll> R, C;
	rep(i, K){
		ll x, y;
		cin >> x >> y;
		R.push_back(x);
		C.push_back(y);
		R[i]--;
		C[i]--;
	}
 
	ll r[H];
	rep(i, H) r[i] = W;
	rep(i, K) r[R[i]]--;
 
	// cout << "r:";
	// rep(i, H) cout << r[i] << " ";
	// cout << endl;
 
	ll a = H * W - K;
	ll s = 0;
	ll p = 0;
	while(p < H){
		s += r[p];
		if(s > a/2){
			if(s-r[p] > s){
				p--;
			}
			break;
		}
		p++;
	}
 
	ll c[W];
	rep(i, W) c[i] = H;
	rep(i, K) c[C[i]]--;
 
	// cout << "c:";
	// rep(i, W) cout << c[i] << " ";
	// cout << endl;
 
	ll t = 0;
	ll q = 0;
	while(q < W){
		t += c[q];
		if(t > a/2){
			if(t-c[q] > t){
				q--;
			}
			break;
		}
		q++;
	}
 
	// cout << p << " " << q << endl;
 
	ll ans = 0;
	ll d = 0;
	rep(i, H) {
		d += abs(i-p);
	}
	ans += d * W;
 
	ll e = 0;
	rep(i, W){
		e += abs(i-q);
	}
	ans += e * H;
 
	rep(i, K) ans -= abs(R[i] - p) + abs(C[i] - q);
	cout << ans << endl;
}