きままにものづくり

日々の気付いたことなんかを書いてます。

SRM623Div1Medium

問題

二次元平面を考える。果物の位置が $(x_i, y_i)$ 与えられる。果物は1秒経つとy軸のマイナス方向に1移動する。(0, 0)に果物を収穫できる人がいて、一秒ごとにx軸のプラスかマイナスの方向に移動できる。収穫できる果物の最大値を求めよ。ただし、 $(x_i, y_i)$ は以下の式で生成される。

解法

現在の位置から次の果物が収穫可能か判断する式は、以下となる。
$y_1 - y_0 \geq |x_1 - x_0|$
絶対値の条件をはずすと、
$y_1 - y_0 \geq x_1 - x_0$
$y_1 - y_0 \geq x_0 - x_1$
式を整理すると、
$y_1 - x_1 \geq -x_0 + y_0$
$y_1 + x_1 \geq x_0 + y_0$
ふたつの式を両方共満たす時、次の果物は収穫可能となる。
$(s, t) = (y+x, y-x)$ とし、sについて昇順になるようにソートする。
LISを用いると最大収穫数が求まる。

計算量

ソート:O(N log N)
LIS: O(N log N)

コード