「スパイラル・ウォーク」問題 （その2）

「スパイラル・ウォーク」問題

締め切りが 2016/12/22 10:00 AM なのでその 2 分後に投稿されるように予約

設問
自然数 w, h に対し、横と縦の長さがそれぞれ w, h となる格子状の道を考えます。
この左上の点からスタートして、同じ交差点を二度以上通らないように、らせんを描いて進みます。
最初は下方向にまっすぐ進み、これ以上前に進めなくなったところで左折し、再びまっすぐ進みます。
これを繰り返し、全ての交差点に到達したところで終了します。
(w, h)＝(4, 3) の場合の進み方を下に示します。このとき進んだ距離は 19 であることが分かります。



自然数 m に対し、上のように進んだ時の距離がちょうど m となるような組 (w, h) の個数を F(m) と定義します。
例えば F(11)＝4 です。進んだ距離が 11 となる組 (w, h) は、(1, 5), (2, 3), (3, 2), (5, 1) の 4 通りです。

同様に、F(3)＝1, F(23)＝6, F(28)＝0 となることが確かめられます。
さらに、自然数 n に対し、1≦m≦n となる全ての m に対する F(m) の和を G(n) と定義します。
例えば、G(11)＝12, G(100)＝283, G(1000)＝5076 となることが確かめられます。
標準入力から、自然数 n（1 ≦ n ≦ 106）が与えられます。
標準出力に G(n) を出力するプログラムを書いてください。
※ テストケースは全部で 6 つあります。全てをPASSすれば正解です。

=======================================================

いやはや，説明にミスリードされて，馬鹿正直なブルートフォースによるプログラムを書いてしまった。

考えて見れば，G(23) を求めるのに F(1) 〜 F(23)  の和を求める必要は全くない。

以下の図をみればわかるが，F(x) があろうがなかろうが行ごとに見てセルの値が x+1 より小さいセルの個数の和が求める答え G(x) である。

G(11) = 5+3+2+1+1 = 12
G(23) = 11+7+5+3+3+2+2+1+1+1+1 = 37



R プログラム

g = function(m) {
    m = m+1
    sum = 0
    for (h in seq.int(m%/%2-1)) {
        sum = sum+m%/%(h+1)-1
    }
    cat(sum, "\n")
}

> system.time(g(991245)) # 11856448
11856448
   ユーザ   システム       経過  
     0.354      0.002      0.348