けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

全国統一プログラミング王決定戦 本選 C - Come Together (300 点)

こういうのを爆速で書けるようになりたい。問題としては

  • マンハッタン距離に関する問題では x 軸方向と y 軸方向とで独立に考えればよいことになるケースが多い (マンハッタンに限らず、各要素ごとに独立にならないかを考察することは重要)

  •  f(x) = |x - a_1| + |x - a_2| + \dots + |x - a_N| の最小値を与える  x について

  • ~のうち  k 番目の値を求めよ、と言われたときの考え方について

という典型考察を多く含んだ教育的な問題だった。

問題へのリンク

問題概要

 H ×  W のグリッドの各マスにコマを 1 個ずつ置き、そのうちの  K 箇所についてコマを取り除く。

今、各コマを上下左右に動かしながら、コマを 1 箇所のマスにすべて集めたい。最小手数でそれを実現せよ。ここで、上下左右に 1 マス分動かすのを 1 手とする。

制約

  •  1 \le H, W, K \le 10^{5}

考えたこと

105 サイズの長方形...そのすべてをメモリに乗っけることもできない。

まずよくある考察として、マンハッタン距離は「x 軸方向と y 軸方向とで独立に考えられるようになることが多い」という傾向がある。逆にこの性質が嬉しいがために、max(|x1 - x2|, |y1 - y2|) みたいな距離な世界をめるアイコン変換 (45 度回転) してマンハッタン距離な世界にして考えるようなケースもある。

今回も x 軸と y 軸とで独立に考えてよい。x 軸について考えてみると、


 HW - K 個の座標値  x_1, x_2, \dots, が与えられるので、 f(x) = |x - x_1| + |x - x_2| + \dots で定義される関数の最小値を求めよ


という問題になることがわかる。このような関数の最小値が  x_1, x_2, \dots のメディアンで与えられることは周知の事実ではあるが、導出もそれほど難しくはない。

メディアン


 N 個の整数  a_1, a_2, \dots, a_N に対して  f(x) = |x - a_1| + |x - a_2| + \dots + |x - a_N| の最小値を与える  x a_1, a_2, \dots, a_N のメディアンになる。


これを考える。例えば  a = (1, 3, 7, 8, 9, 12) x 3 7 の間だったとき

 1, 3, x, 7, 8, 9, 12

という並びになっていて、

  •  x の左側が 2 個
  •  x の右側が 4 個

という状態になっている。この状態で  x を右側に  \epsilon だけ動かすと、左側のそれぞれの値との差はそれぞれ  \epsilon だけ大きくなり、右側のそれぞれの値との差はそれぞれ  \epsilon だけ小さくなる。左側に 2 個、右側に 4 個あるなら、総合して  2\epsilon だけ小さくなることがわかる。

ここから言えることは、 x より小さい値と大きい値との個数に偏りがあるときは、それを是正する方向に  x を動かすと、関数  f(x) の値が小さくなるということ。

それが均衡するのは左右のバランスがとれているとき、すなわち  x がメディアンになっているときである。少し注意すると、 N が奇数のときはメディアンのみ正解で、 N が偶数のときは中央値をなす  a が 2 個あるので、その範囲はすべて正解になる。

元の問題に戻り

元の問題に戻って、 HW - K 個の座標値  x_1, x_2, \dots, のメディアンを求めればよい。 x の取りうる値は  0, 1, \dots, H-1 のみで、

  • 0 が  v_0
  • 1 が  v_1
  • 2 が  v_2
  • ...

といったことがわかるので、これを積算して半分になるところを求めればよい。何気にこの部分は


 k 番目 (1-indexed) の値を求めるためには、 x 以下の値の個数が  k 個以上となる最小の  x を見つければいい


という典型処理を施している。この発想は特に二分探索とセットで登場することが多い (今回は二分探索は不要)。最後まで典型要素テンコ盛りの教育的問題。

#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;
}