Code Festival 上海 2014 レビュー(B : n-th Points)

正解者の回答から、問題の解き方について考えてみた。

とにかくk個書き出してみる

自分のように正攻法でプログラムを書いてもいいし、実直に手で計算して書き出してもいい。

プログラムだと、k=1000とかでも簡単に出せるので、規則性を導くのが早いかもしれない。

0 0
-1 0
0 -1
0 1
1 0
-2 0
-1 -1
-1 1
0 -2
0 2
1 -1
1 1
2 0
-3 0
-2 -1
-2 1
-1 -2
-1 2
0 -3
0 3

規則性を見つける

n=1の場合は(0,0)。

n>1の場合は|x|+|y|の値に規則性がある。

n-1=1..4 (4)    => |x|+|y|=1
n-1=5..12 (8)   => |x|+|y|=2
n-1=13..24 (12) => |x|+|y|=3
n-1=25..40 (16) => |x|+|y|=4
...

ここまでは出来ていた。問題は次以降の思考に辿りつけなかったこと。

さらに規則性を見つける

|x|+|y|が同じ値を取るnにおいて、xyの間にも規則性がある。

おおよそ以下の通り。

  • x-(|x|+|y|)から始まって、最初と最後は1回、その他は2回ずつ繰り返しながら、|x|+|y|で終わる。
  • y0から始まって、正負を交代しながら|x|+|y|で終わる。

これをプログラムで書くことはそれほど難しくない。

Binary searchを用いてn-1個目の|x|+|y|を求める

実際には、入力のn-1が含まれる各|x|+|y|の最後の数を求めれば良い。 「入力のn-1が含まれる各|x|+|y|の最後の数」とは、 等差数列の和 になっている。

\( a_1=4, d=4 \)

\( S_n=\sum_{i=1}^n a_i=\frac{n(2a_1+(n-1)d)}{2}=2n(n+1) \)

これがBinary searchの、lowをmiddleにするか、highをmiddleにするか、の条件となる。

最終的に、入力のn-1に対する等差数列の和を出すことができ、そこからxyの規則性を使って答えを出す。