[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) \]

が答えです。

コード

感想

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