AtCoder ABC 151 - こんちゅう

うぎゃあ。解けなかった問題の簡単な説明を覚書程度に残します。

ABC151F

けっこう正答率が高い。

解き方1

最適な円は必ず2点or3点を通る。どうしてかというと, まず0点or1点しか通らない円は2点通る円のほうが最適であることが分かる。N個から2点取ってきて，こいつらを通る円を考える。でも2点だと円が確定しない。2点を直径とする円内に他の点が全てあればそれが最適。なければ外にある点を結んだ3点を通る円のうちいずれかが最適（もちろん全部ハズレの場合もある）。
この解法は $O(n^4)$ でできる。根拠は, 3点取ってくるのに $O(n^3)$ で，それごとにN個の頂点に対して円内に入ってるか確かめる必要があるから。

最適な円は必ず3点通るやろ！っつって頑張って実装してたが，方針が違う上そもそも実装力が無くて間に合わず。つらるん。

解き方2

editorialのやりかた。二分探索を使う。Rを固定し，各頂点を中心とするN個の円の交点を全て求める。このとき交点のできない円のペアがあったらやり直し。各交点からN頂点までの距離がR以下かどうか調べる。R以下なら半径Rの円で全ての頂点を覆うことが出来る。そのような交点が一つでもあったらRを小さくして再チャレンジ，一つも無かったらRを大きくして再チャレンジ。
結局これは，２つの円を選ぶことで全体の円の中心となりうる点を2つに絞っているところがミソである。１ステップあたりの計算量は,２つの円を選ぶのに $O(n^2)$ で，それに対してN頂点が円内に入っているか調べないといけないので， $O(n^3)$ となる。あとはこれを十分な精度とするために,はじめの区間をTとすると， $T2^{-n}<10^{-6}$ くらいになるよう $n$ を設定すればいいのかな。

解き方3

最小包含円でググると良い感じのライブラリが出てくるらしい。へええ。

解き方4

三分探索とやらでできるらしい。 $f(x,y)$ を $x,y$ を中心としたときのN頂点までの最長距離の二乗の最大値とすると, $f(x,y)$ は凸関数になるらしい。ほんまか。まあでもそれはそうで, 例えば $x$ を固定したとき，
$f(x,y)=max((y_1-y)^2+const,\cdots ,(y_N-y)^2+const)$
であり，図を書いてみると確かに凸関数っぽい。でもこれって解が自明にならない？よく分かってない。こんど実装してみよっと。

【追記】上で見たように， $x$ で止めても $y$ で止めても凸関数だから, いわゆる鞍点が存在しない．つまり, 例えば $x$ を一つ固定したときの $f(x,y)$ の最大値を $g(x)$ とする．このとき $g(x)$ は凸関数になる．
$x,x'$ に対して $x1=px+(1-p)x'$ としたとき $g(x1)\le pg(x)+(1-p)g(x')$ を示せばいい． $g(x1)=f(x1,y1)$ とすると, $g(x)\ge f(x,y1), g(x')\ge f(x',y1)$ であり, yを止めたとき $f$ は凸関数なので,
$pg(x)+(1-p)g(x')\le pf(x,y1)+(1-p)f(x',y1)\le f(x1,y1)=g(x1)$
が成立する．
もしかしたら合成関数が云々とかでもっと簡単に言うこともできるかもしれない．蟻本に載ってた気がするので帰ったら確認してみる．
ともかく $const*O(N^2)$ で出来るのは魅力的。実装も簡単。