Google code jam 2013 round 1 Aの問題A. bullseyeに挑戦する.
白と黒が同心円状に描かれた「矢の的のようなもの」をbullseyeという.
ここでは
とする.
この問題を入力と出力で定義すると,
である.
入力と,それに対する正しい出力の例は以下の通りである.
よって$m$本の黒い輪から成るbullseyeを完成するには $$ \sum_{k=1}^m (2 r + 4 k - 3) = 2 m^2 + (2 r - 1) m $$ のペンキが必要であるとわかる.
よって$2 m^2 + (2 r - 1) m \le t$を満たす最大の$m$を出力すればよい. 二次方程式の解の公式から $$ \left\lfloor \frac{1 - 2 r + \sqrt{(2 r - 1)^2 + 8 t}}{4}\right\rfloor $$ を出力すればよい.
というのが素直な方針であるが,実際に試すと……