Google Code Jam 2016 World Finals

2016-08-10 | [Competitive programming]

C 問題の答えがあるので注意してください．

コンテスト

A, B を解いて 10 位でした． B は見たら解けるものに見えたので他の問題を読まずに突撃したら FA がとれました (https://twitter.com/semiexp/status/761733685418819584)．

A はなんでここで出したんだろうという感が強い問題でした（何も考えずにひたすら実装をすると通って，それ以外の解法があるともあまり思えない）

C は解法聞いたり後で考えたりしてすごい問題だなあとなりました．せめて実験するべきだったかなあ…

D はいろいろ試してことごとく破綻してつらかったですが，解説を聞いたら解けたかったなあという気になりました（そもそものアプローチがだいぶ間違っていたけど…）

E は解ける気がしません．

C 問題の答えと証明

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

(x, y) で中心が (x, y) の円を指すことにします． (x, y) が見える必要十分条件は「x, y が互いに素，かつ sqrt(x^2 + y^2) < 1/d」になるらしいです．これを証明します．

まず，互いに素が必要であることは明らかなので，以後 x, y は互いに素であるとします．

円のうちどの部分が見えてもよいとすると考えづらいので，とりあえず「その円だけ周囲を透明にし，中心に赤い点を置いたとしたとき，中心の赤い点が見えないといけない」という条件で問題を解くことを考えます． このとき，(x0, y0) が見えるためには，「直線 y0 * x - x0 * y = 0 と，(x0, y0) より原点に近い円が交点を持たない」ことが必要十分です．

これは，「0 < x^2 + y^2 < x0^2 + y0^2 なる (x, y) であって，直線 y0 * x - x0 * y = 0 との距離が d 以下のものが存在しない」と言い換えられます． 点と直線の距離の公式から，これは「0 < x^2 + y^2 < x0^2 + y0^2 なる (x, y) であって，|y0 * x - x0 * y| / sqrt(x0^2 + y0^2) <= d を満たすものが存在しない」と言い換えられます．

ここで，x0, y0, x, y は全部整数なので，|y0 * x - x0 * y| も整数です．しかも，x0, y0 は互いに素なので，これを 0 にする (x, y) は (x0, y0) の整数倍しか存在せず，そのようなものは (x0, y0) より近くはないことから， |y0 * x - x0 * y| >= 1 としてよいです．一方，x0, y0 が互いに素なので，絶対値の中を 1 あるいは -1 にするような x, y (0 <= x < x0, 0 <= y < y0) がそれぞれ存在します．

なので，結局条件は「1 / sqrt(x0^2 + y0^2) <= d が成り立たない」すなわち「sqrt(x0^2 + y0^2) < 1/d」となります．

ところで，上の議論から，「原点および円 (x0, y0) の中心を結ぶ直線」から等距離のところに最寄りの 2 円がある」ことがわかるので，この直線を少し回転させるとこれらのうちのどちらかの円により近づいてしまいます． これらの円は (x0, y0) よりも原点に近く，原点から見た視野角が大きいことから，直線を回転させまくってこれらの円が再び見えなくなったときには，(x0, y0) はもう見えなくなっています． よって，円 (x0, y0) が少しでも見えるならば，円の中心も「見える」としてよいため，上の議論で得られた条件が結局必要十分条件であったことがわかります．