[Codeforces] Grakn Forces 2020 D. Searchlights

2020年10月1日2020年12月12日

問題

方針

泥棒 \( i \) の座標は \(( a_i, b_i) \) であり、サーチライト \( j \) の座標は \( (c_j, d_j) \) です。 泥棒の座標を \( ( a_i + t, b_i) \) と移動したとき、

\[ a_i + t \leq c_j \wedge b_i + u > d_j \]

を満たす最小の \( u \) を求めます。\( f(t) \) を 泥棒の \( x \) 座標を \( t \) 移動したとき、上記を満たす最小の \( u \) とします。まず初めに、\( f(t) = 0 \ ( 0 \leq t \leq 10^6 + 1)\) と初期化します。泥棒とサーチライトの座標の関係が、

\[ a_i \leq c_j \wedge b_i \leq d_j \]

を満たすとき、\( 0 \leq t \leq c_j – a_i \) について、\( f(t) \geq d_j – b_i + 1 \) となります。したがって、\( 1 \leq i \leq n \wedge 1 \leq j \leq m \) について、\( a_i \leq c_j \wedge b_i \leq d_j \)であるとき、

\[ f(c_j – a_i) \leftarrow \max (f(c_j – a_i), d_j – b_i + 1)\]

と更新します。さらに、\( i = 10^6 + 1 \) から \( i = 1 \) まで、

\[ f(i – 1) \leftarrow \max(f(i – 1), f(i)) \]

と更新します。したがって、

\[ \min_{0 \leq t \leq 10^6 + 1}(f(t) + t) \]

が答えです。

コード

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

const int MAX = 1000002;
int f[MAX]{};

int main() {
    int n, m;
    cin >> n >> m;
    pair<int, int> p[n];
    
    int a[n], b[n], c[m], d[m];
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> c[i] >> d[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i] <= c[j] && b[i] <= d[j]) {
                chmax(f[c[j] - a[i]], d[j] - b[i] + 1);
            }
        }
    }
    for (int i = MAX - 1; i >= 1; i--) {
        chmax(f[i - 1], f[i]);
    }
    int best = INT32_MAX;
    for (int i = 0; i < MAX; i++) {
        chmin(best, f[i] + i);
    }
    cout << best << "\n";
    return 0;
}

感想

いまいち分からないです。