問題概要

問題文はこちらを参照してください。

ＤＰの問題として有名なLISを使います。

解法

ｘ軸上の円の列が次々に前の円の内部になければならないということなので、簡単にするため円の右端の座標で降順に並べ替えます。すると、ある円は前の円の左にはみ出すか、内部にあるかのどちらかになります。左にはみ出すということは円の左端の座標が前の円の左端の座標より小さいということになり、内部にあるということは左端の座標が大きいということになります。

ということで、左端の座標の列の中で、増加している部分列の最大サイズを求める問題、つまりLIS(Longest Increasing Subsequence)問題に帰着します。

しかし、この問題では「strictlyに内部」なので、端が接している場合は含めないようにしなければいけません。左端の重なりはLISで解く際にはじくことができますが、右端のみが重なって、左端が重ならないものも省くようにしないといけません。これは最初に右端の座標で並べ替える際に、右端の座標が同じならば左端の座標が大きいほうを先に並べるように(左の座標でも降順)することでLISの時にはじくことになります。

LISについては参考書籍の蟻本などに書かれているので詳細は省きます。$O(n^2)$と$O(n\log{n})$の解法が紹介されていますが、この問題は$O(n\log{n})$の解法でなければいけません。漸化式だけ書いておきます。

考察

こうしてみると簡単な問題に見えるのですが、最初の並べ替えを思いつけるかどうかの積み重ねでしょうか。