https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_c
前提知識
解説
https://atcoder.jp/contests/nikkei2019-final/submissions/4312922
まず、この問題を考える糸口だが、「マンハッタン距離の総和の最小化問題である」という所から始める。
マンハッタン距離の問題について慣れている人であれば、
- マンハッタン距離の総和が最小となるのは中央値
- 縦横独立に考えられる
というのが瞬時に出てくる。
これが出てこないとこの問題を解くのは難しい。経験を要する問題。
ここまで分かれば、後は、中央値の求め方だ。
これは二分探索で求めることができる。
(全部の個数/2の切り上げ)+1番目が求めたい中央値となるので、
check(x) := x以上の数が(全部の個数/2の切り上げ)個以上か
という比較関数で二分探索すれば求められる。
個数を集計するにはBITを使おう(計算量的には累積和の方がいい。特にBITにした意味は無い)
これをX,Yどちらにもやって、最小となる部分が見つかったら、マンハッタン距離の総和を取ればいい。
自分は全部に駒があるとして、マンハッタン距離の総和を求めて、無い部分を引くことで実現している。
ll H, W, K, R[101010], C[101010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> H >> W >> K; rep(i, 0, K) cin >> R[i] >> C[i]; rep(i, 0, K) R[i]--, C[i]--; ll tot = H * W - K; ll sx = -1, sy = -1; rep(_, 0, 2) { BIT<ll> bit(W); rep(x, 0, W) bit.add(x, H); rep(i, 0, K) bit.add(C[i], -1); ll ok = 0, ng = W; ll bor = (tot + 1) / 2; while(ok + 1 != ng) { ll md = (ng + ok) / 2; if (bor <= bit.get(md, W)) ok = md; else ng = md; } sx = ok; swap(H, W); swap(sx, sy); rep(i, 0, K) swap(R[i], C[i]); } ll ans = 0; rep(x, 0, W) ans += abs(x - sx) * H; rep(y, 0, H) ans += abs(y - sy) * W; rep(i, 0, K) ans -= abs(C[i] - sx) + abs(R[i] - sy); cout << ans << endl; }