かしのブログ

競技プログラミングとか

M-SOLUTIONS プロコンオープン 2020 F - Air Safety

AtCoder 座標二分探索

問題

格子状の点上に配置された飛行機が4方向のうち決められたほうに飛ぶとき、衝突するか判定する。衝突する場合は、その中で最も早い衝突が何秒後に起こるか求める。

考察

衝突には正面衝突と直行する衝突の2種類があるので、それぞれの解の最小値が答えになる。

正面衝突

$x$ 方向に向かう飛行機 $(X_1, Y_1)$ と $-x$ 方向に向かう飛行機 $(X_2, Y_2)$ が衝突を起こす条件は、明らかに $Y_1 = Y_2 \land X_1 \lt X_2$ で、衝突までの時間は $5(X2-X1)$ 秒。

$X_1 \lt X_2$ の判定には二分探索を用いる。実装にc++のsetを使えばupper_boundを用いる。

$y$ 方向も同様。

直行する衝突

$y$ 方向に向かう飛行機とx方向に向かう飛行機の衝突を考える。

$x$ 方向に向かう飛行機 $(X, Y)$ が衝突する点 $(x, y)$ と秒数 $s$ の組み合わせ $(x, y ,s)$ は $(X+1, Y, 1), (X+2, Y, 2), \cdots, (X+s, Y, s), \cdots$ の点。 $y$ 方向に向かう飛行機が $(X+s, Y, s)$ にあるなら、初期値は $(X+s, Y-s)$ であることがわかる。よって、半直線 $l: x + y = X + Y \land x \gt X$ 上にある $y$ 方向に向かう飛行機はあるか判定すればよいことがわかる。衝突までの時間は $10s$ 秒。

$x \gt X$ の判定も二分探索。

あとの組み合わせは回転で同じ問題になる。

実装