こんちゅう

エッセイ・小説・ブログ・楽譜置き場。 不定期更新。

AtCoder ABC 151

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

ABC151F

atcoder.jp

けっこう正答率が高い。

解き方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つの円を選ぶことで全体の円の中心となりうる点を2つに絞っているところがミソである。1ステップあたりの計算量は,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)で出来るのは魅力的。実装も簡単。