2020-08-13

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$ の判定も二分探索。

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

実装

atcoder.jp

2020-06-10

第三回アルゴリズム実技検定 N - 入れ替えと並び替え

AtCoder PAST 転倒数

問題

長さ $N$ の数列 $a = \{a_i | a_i = i\}$ に、以下の合計 $Q$ 個のクエリを実行した結果を求める。

$a_x$ と $a_{x+1}$ をスワップ
$a_x, a_{x+1}, \cdots, a_y$ を昇順に並び替える

atcoder.jp

考察

1つ目のクエリは $\mathcal{O}(1)$ で実行可能なので、2つ目のクエリを高速に行う方法を考える。

数列 $a$ の転倒数は、1つ目のクエリでは1増減し、2つ目のクエリでは発生するスワップの回数分だけ減少することがわかる。よって、全ての2つ目のクエリで発生するスワップの合計は高々 $Q$ 回であることがわかった。また、2つ目のクエリでは $a_i > a_{i+1}$ となる箇所でスワップされるので、このような $i$ の集合 $\mathcal{I}$ を知っておく必要がありそう。

1つ目のクエリで $a_x$ と $a_{x+1}$ をスワップすることを考える。 $a_i > a_{i+1}$ かどうかの関係が変わる可能性があるのは、 $(x-1, x), (x, x+1), (x+1, x+2)$ の3箇所なので、これらの関係が $a_i > a_{i+1}$ か判定し、 $\mathcal{I}$ を更新する。

2つ目のクエリで昇順にソートすることを考える。 $x \leq z \lt y \land z \in \mathcal{I}$ なる $z$ があるとき、 $a_z, a_{z+1}$ を更新し、 $(z-1, z), (z, z+1), (z+1, z+2)$ の関係を元に $\mathcal{I}$ を更新する。