【No.022】「AOJ 2181 Neko's Treasure 」
AOJ-ICPC 難易度550の問題です。
Neko's Treasure | Aizu Online Judge
問題概要
二次元平面のなかに、2つの点と、nつの円の候補がある。
nつの円の候補の中から任意の数だけ実際に設置する円をえらび、
2点の間を移動するとき(回り道をしてもかまわない)に横切らなければならない円の数の最小値
を最大化しなさい。
ただし、実際に設置する円のなかで、互いに触れ合っているか交差している円があってはいけない。
完全に内包しているか内包されている円はあっても問題ない。
考察
2つの点両方を内包している円は設置する必要はない。
同様に、2つの点両方が外側にある円も設置する必要はない。
よって、設置するのは、どちらか片方の点のみを内包している円だけで十分である。
設置する意味の無い円の例
2つの点を内包している
どちらの点も内包していない
解法
選ぶ円の組み合わせは全部で3つのパターンがある。
・「点Sのみを内包している円」しか選んでいないパターン
・「点Tのみを内包している円」しか選んでいないパターン
・「点Sのみを内包している円」と「点Tのみを内包している円」の両方が選ばれているパターン
最初の2つのパターンについては、動的計画法で簡単に求めることができる。
ノードの数が円の数と等しく、円iが円jを内包している場合にノードiからノードjにエッジが伸びている有向グラフを考えると、答えはそのグラフでに最も長いパスの長さになるからである。
(ちなみに半径の長さでソートすることがトポロジカルソートになる)
最後のパターンについては、「点Sのみを内包している円」の中で最も外側にある円と「点Tのみを内包している円」の中で最も外側にある円を二重ループで決めうちすれば最初の2つのパターンと同じになり、動的計画法に使用した配列を参照すればそれぞれの決め打ちした円のペアについて、O(1)で最大値を求めることができる。
ACしたソースコード
AIZU ONLINE JUDGE: Code Review