すごいよくある感じ

問題概要

二次元平面上に $N$ 個の点 ( $(a_{i}, b_{i})$ ) と、 $M$ 個の点光源 ( $(c_{j}, d_{j})$ ) がある。今、 $N$ 個の点に対して以下の操作を行う

$N$ 個の点を一律に右に動かす
$N$ 個の点を一律に上に動かす

この操作によって、すべての点について「どの点光源の右下側にない」という状態にしたい。最小移動回数を求めよ。

制約

$1 \le N, M \le 2000$
$0 \le a_{i}, b_{i} \le 10^{6}$

考えたこと

この問題では

右に動かす量
上に動かす量

の 2 つの値を決める必要がある。このように 2 つの値を決める必要のある問題では、1 つの値を固定してしまう方法が有効っぽい。そこで、右に動かす量を固定してみる。

右に r だけ動かすとする。このとき、

$c_{j} - a_{i} \le r$ であるような $(i, j)$ に対しては上に動かす必要はない
そうでない $(i, j)$ に対しては、 $\max(0, d_{j} - b_{i} + 1)$ だけ上に動かす必要がある

という風になっている。

解法

以上を踏まえると、次のようにして解ける。

各 $(i, j)$ に対して $c_{j} \gt a_{i}$ ならば、chmax(need[ $c_{j} - a_{i}$ ], $\max(0, d_{j} - b_{i})$ ) とする
こうして得られる配列 need の累積 max (上から) をとる
- このとき、need[ r ] は、右に r だけ動かしたときの必要な「上に動かす必要のある操作回数」を表す
各 r に対する r + need[ r ] の最小値を求める

計算量は $O(NM + A)$ ( $A$ は登場する座標値の最大値)。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL<<60;
const int MAX = 1100000;
int main() {
    int N, M;
    cin >> N >> M;
    vector<long long> a(N), b(N), c(M), d(M);
    for (int i = 0; i < N; ++i) cin >> a[i] >> b[i];
    for (int j = 0; j < M; ++j) cin >> c[j] >> d[j];
    vector<long long> need(MAX, 0);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (a[i] > c[j]) continue;
            chmax(need[c[j] - a[i]], max(0LL, d[j] - b[i] + 1));
        }
    }
    for (int r = MAX - 1; r >= 1; --r) chmax(need[r-1], need[r]);
    long long res = INF;
    for (int r = 0; r < MAX; ++r) chmin(res, r + need[r]);
    cout << res << endl;
}

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

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

Grakn Forces 2020 D. Searchlights (R2000)

問題概要

制約

考えたこと

解法

コード