[Codeforces] Grakn Forces 2020 D. Searchlights
問題
方針
泥棒 \( 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; }
感想
いまいち分からないです。
ディスカッション
コメント一覧
まだ、コメントがありません