TDPC K - ターゲット

考え方

ABCでいうと、E問題級。

同時に採用できる円は、円の左端と右端で大小関係が逆転しているものである。
つまり、左端が大きい順にソートして、右端の最長増加部分列の長さを求めれば答え。

ただし、入力には左端や右端が同じであるものが含まれるため、これらを適切に処理しなければならない。
左端が同じ場合、最初のソートのタイブレークで右端が大きい順になるようにすればよい。
右端については、最長増加部分列を求めるときに、一致するものは採用しないようにすればよい。

計算量は $O(N\log N)$ である。

入力を受け取る。

n: 3
x: {1, 0, 3}
r: {1, 3, 2}

各円について、左端を $x-r$、右端を $x+r$ とする。

円1: (0, 2)
円2: (-3, 3)
円3: (1, 5)

左端が大きい順にソートする。

(1, 5), (0, 2), (-3, 3)

右端だけを取り出すと、次の数列になる。

vec: {5, 2, 3}

この数列の最長増加部分列の長さは $2$ である。
例えば、$2,3$ を採用できる。

したがって、作れるターゲットの最大サイズは $2$ となる。

特になし。

特になし。