こういうのを爆速で書けるようになりたい。問題としては
マンハッタン距離に関する問題では x 軸方向と y 軸方向とで独立に考えればよいことになるケースが多い (マンハッタンに限らず、各要素ごとに独立にならないかを考察することは重要)
の最小値を与える について
~のうち 番目の値を求めよ、と言われたときの考え方について
という典型考察を多く含んだ教育的な問題だった。
問題概要
× のグリッドの各マスにコマを 1 個ずつ置き、そのうちの 箇所についてコマを取り除く。
今、各コマを上下左右に動かしながら、コマを 1 箇所のマスにすべて集めたい。最小手数でそれを実現せよ。ここで、上下左右に 1 マス分動かすのを 1 手とする。
制約
考えたこと
105 サイズの長方形...そのすべてをメモリに乗っけることもできない。
まずよくある考察として、マンハッタン距離は「x 軸方向と y 軸方向とで独立に考えられるようになることが多い」という傾向がある。逆にこの性質が嬉しいがために、max(|x1 - x2|, |y1 - y2|) みたいな距離な世界をめるアイコン変換 (45 度回転) してマンハッタン距離な世界にして考えるようなケースもある。
今回も x 軸と y 軸とで独立に考えてよい。x 軸について考えてみると、
個の座標値 が与えられるので、 で定義される関数の最小値を求めよ
という問題になることがわかる。このような関数の最小値が のメディアンで与えられることは周知の事実ではあるが、導出もそれほど難しくはない。
メディアン
個の整数 に対して の最小値を与える が のメディアンになる。
これを考える。例えば で が と の間だったとき
という並びになっていて、
- の左側が 2 個
- の右側が 4 個
という状態になっている。この状態で を右側に だけ動かすと、左側のそれぞれの値との差はそれぞれ だけ大きくなり、右側のそれぞれの値との差はそれぞれ だけ小さくなる。左側に 2 個、右側に 4 個あるなら、総合して だけ小さくなることがわかる。
ここから言えることは、 より小さい値と大きい値との個数に偏りがあるときは、それを是正する方向に を動かすと、関数 の値が小さくなるということ。
それが均衡するのは左右のバランスがとれているとき、すなわち がメディアンになっているときである。少し注意すると、 が奇数のときはメディアンのみ正解で、 が偶数のときは中央値をなす が 2 個あるので、その範囲はすべて正解になる。
元の問題に戻り
元の問題に戻って、 個の座標値 のメディアンを求めればよい。 の取りうる値は のみで、
- 0 が 個
- 1 が 個
- 2 が 個
- ...
といったことがわかるので、これを積算して半分になるところを求めればよい。何気にこの部分は
番目 (1-indexed) の値を求めるためには、 以下の値の個数が 個以上となる最小の を見つければいい
という典型処理を施している。この発想は特に二分探索とセットで登場することが多い (今回は二分探索は不要)。最後まで典型要素テンコ盛りの教育的問題。
#include <iostream> #include <vector> #include <cmath> using namespace std; int main() { // 入力 H = N[0], W = N[1] long long N[2], K; cin >> N[0] >> N[1] >> K; // num[0]: x 軸方向に見て各座標に何個のコマがあるか、num[1] は y 軸方向 vector<long long> num[2]; num[0].assign(N[0], N[1]); num[1].assign(N[1], N[0]); for (int k = 0; k < K; ++k) { int r, c; cin >> r >> c; --r, --c; num[0][r]--; num[1][c]--; } // 各軸ごとに long long total = 0; for (int iter = 0; iter < 2; ++iter) { // メディアンを求める long long mid = 0; long long sum = 0; for (mid = 0; mid < N[iter]; ++mid) { sum += num[iter][mid]; if (sum >= (N[0] * N[1] - K + 1) / 2) break; } // 関数値を求める long long val = 0; for (long long i = 0; i < N[iter]; ++i) val += num[iter][i] * abs(i - mid); // 合計する total += val; } cout << total << endl; }