正しい嘘解法入門 - Monoxer Tech Blog

ソフトウェアエンジニアの大橋（AtCoder: amylase）です。

今回は競技プログラミングの話をします。それも、企業の技術ブログにありがちな “競技プログラミングが業務に役立った話” ではなく、純粋にコンテストに出た問題の話です。一見怪しく見える幾何の近似を正当化します。最後までお付き合いください。

問題

atcoder.jp

辺の長さが $A, B$ である長方形の中にできるだけ大きな正三角形を描くとき、その辺の長さを出力してください。

$1 \le A, B \le 1000$
答えと出力の絶対誤差または相対誤差が $10^{-9}$ 以下ならば正解

近似解

本問を解く上で重要な性質は「最大の正三角形は長方形と頂点を共有する」というものでした。今回これの解説はしませんが、公式解説が非常にきれいなので見てない人は今見てください。

この性質が成り立っているとき、共有する頂点で長さ $A$ の辺と三角形の近い辺がなす角を $\theta$ とすると、この問題の答えは共有する頂点から伸びる2辺のうち短いほうの長さ、すなわち

$\displaystyle{ \max_{0 \le \theta \le \frac{\pi}{6}} \min\left( \frac{A}{\cos\theta}, \frac{B}{\cos \left( \frac{\pi}{6} - \theta \right)} \right) }$

です。

ここで試したくなる嘘解法が「 $\theta$ を細かく刻んでたくさん試す」であり、実際に弊社の競プロ部員もこの解法で正解しています。部内で話題になったのが彼の「6000万分割ではWAになるが8000万分割ではACになる」という報告でした。これはたまたまなのでしょうか？　誤差を見積もってみましょう。

誤差評価

$A \lt B \cos{\frac{\pi}{6}}$ のときは簡単にわかるので、以下 $B \cos\frac{\pi}{6} \lt A \lt B$ とします。

$\displaystyle{ f(\theta) = \frac{A}{\cos{\theta}}, g(\theta) = \frac{B}{\cos{(\frac{\pi}{6} - \theta})} }$

とおくと、 $f$ が単調増加、 $g$ が単調減少なので、求める最大値は $f(\theta) = g(\theta)$ なるただ一つの $\theta = \theta_{\max}$ により与えられることがわかり、 $f(0) \gt g(0)$ かつ $f(\frac{\pi}{12}) \lt g(\frac{\pi}{12})$ なので、 $0 \lt \theta_{\max} \lt \frac{\pi}{12}$ であることがわかります。

$f, g$ のグラフを $\theta_{\max}$ の周辺で拡大すると次の図のようになります（ $f, g$ は直線で近似します）。角度を分割する戦略では、角度の分割幅を $\varepsilon$ とするとある角度 $\theta$ があって $\theta \le \theta_{\max} \le \theta + \varepsilon$ となるので、そこに着目すると図のような点の位置関係になります。

$f, g$ の微小変化を見積もります。 $\theta_{\max}$ の周辺での傾きは、 $f, g$ を微分してそれぞれ

$\displaystyle{ f'(\theta_{\max}) = \frac{A\sin(\theta_{\max})}{\cos^2(\theta_{\max})}, g'(\theta_{\max}) = -\frac{B\sin(\frac{\pi}{6} - \theta_{\max})}{\cos^2(\frac{\pi}{6} - \theta_{\max})} }$

とわかるので、 $f, g$ の微小変化はそれらの $\varepsilon$ 倍です。

解の絶対誤差が最大になるのは2つの近似解候補が等しいとき（図の点 $P, Q$ が同じ高さにある）で、この時の絶対誤差は2つの微小変化の調和平均の半分になります。調和平均を幾何平均で上から押さえて三角関数の計算をゴリゴリすると解の絶対誤差は

$\displaystyle{ \frac{ \varepsilon \sqrt{AB} \sin{\frac{\pi}{12}} }{ 2 \cos{\frac{\pi}{6}} } }$

で抑えられます。次の準備として、 $B \cos{\frac{\pi}{6}} \lt A$ を用いて $B$ を消去し、

$\displaystyle{ \frac{ \varepsilon A \sin{\frac{\pi}{12}} }{ 2 \cos^{\frac{3}{2}}{\frac{\pi}{6}} } }$

で抑えておきましょう。

解は少なくとも $(\sqrt{6} - \sqrt{2}) A$ （正方形の場合）より大きいので、絶対誤差の評価とあわせて相対誤差は

$\displaystyle{ \frac{\varepsilon \sin{\frac{\pi}{12}}}{2 (\sqrt{6} - \sqrt{2}) \cos^{\frac{3}{2}}{\frac{\pi}{6}}} }$

より小さくなります。

分割数を $d$ とおくと $\varepsilon = \frac{\pi}{6d}$ なので、分割数を具体的に決めることで以下のように相対誤差を評価できます。

6000万分割: $\lt 1.356 \times 10^{-9}$

8000万分割: $\lt 1.016 \times 10^{-9}$

残念ながら微妙に足りないですが*1、おそらく $\theta_{\max}$ が $\frac{\pi}{24}$ より大きいか小さいかで場合分けするなどして精密に評価すると $10^{-9}$ より小さいことがきちんといえるのではないかと思います。それかもう8200万分割で提出しましょう（相対誤差 $\lt 9.904 \times 10^{-10}$ ）。

いかがでしたか？

$f, g$ の交点が解であり $f - g$ が単調であるとわかったときに二分法を適用するのが競技プログラミングとしては最適ですが、コンテストに参加する者なら痛感しているように常に最適な解法を選択できるとは限りません。怪しい近似をするとき、嘘仮定を置くときに本稿を思い出して「もしかしたら証明できるかもしれないしな！」と自信を持って提出していただけると幸いです。