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
において、x
とy
の間にも規則性がある。
おおよそ以下の通り。
x
は-(|x|+|y|)
から始まって、最初と最後は1回、その他は2回ずつ繰り返しながら、|x|+|y|
で終わる。y
は0
から始まって、正負を交代しながら|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
に対する等差数列の和を出すことができ、そこからx
、y
の規則性を使って答えを出す。