きままにものづくり

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

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)

コード