円の列 \(C_1, C_2, \dots, C_K\) がサイズ \(K\) のターゲットであることの必要十分条件は，左端と右端の条件として

• \(x_{C_{i + 1}} - r_{C_{i + 1}} < x_{C_i} - r_{C_i} (1 \leq i \leq K - 1)\)
• \(x_{C_i} + r_{C_i} < x_{C_{i + 1}} + r_{C_{i + 1}} (1 \leq i \leq K - 1)\)

が成り立つことです．

そこで，円を \(x_{C_i} - r_{C_i}\) の値の降順（タイの場合は \(x_{C_i} + r_{C_i}\) の降順にソートしておくことで，次の条件を満たす整数列 \(d_1, d_2, \dots, d_L\) の長さ \(L\) の最大値を求める問題に帰着できます．

• \(1 \leq d_1 < d_2 < \dots < d_L \leq N\)
• \(x_{d_1} + r_{d_1} < x_{d_2} + r_{d_2} < \dots < x_{d_L} + r_{d_L}\)

これは LIS を求める問題そのものです．これにより \(O(N \log N)\) 時間で解けます．

（タイの場合に \(x_{C_i} + r_{C_i}\) の降順 になるようにソートするのは，\(x_{C_i} - r_{C_i}\) の等しいものが \(x_{d_i} + r_{d_i}\) の列に二度以上現れることを防止するためです．このような，LIS に帰着させる際のタイブレークの扱いの工夫は頻出です．）