Lake(湖) - joi2010-day4 解説

筆者: qnighy

池の岸と岸を結ぶ直線状の航路の集合のなかで、交差しない最大の部分集合を見つける問題である。

問題の変形

実は、この問題における「岸」は、任意の位置(座標0が自然)で切り開くことができる。

そうすると、直線上の2点を結ぶ区間のうち、互いに包含または非交差であるような区間の部分集合で最大のものを見つける問題になる。

また、この問題では座標の絶対的な大きさは無視できるので、座標圧縮を行うと、処理しやすくなる。

O(N^3)解法

…

O(N^2)解法

この問題は明らかに動的計画法であるので、漸化式を立てる。

漸化式は、特定区間内においてどれだけの区間を同時に保持できるかである。

基本的には以下のようにおけばよい。

dp[f:t] = max(dp[f:t-1], dp[f:X]dp[X1:t-1]+1)

dp[f:t]は、座標fからtの範囲内に収まる航路のなかでの交差しない最大である。

右側は、tの直前に到着する航路を使わない場合である。

左側は、Xを出発して、tの直前に到着する航路を使う場合である。

これを実装することによって、O(N^2)で解けるので、満点を獲得できる。