CodeIQ 「『スパイラル・ウォーク』問題」の掲載期間が終わったということで、自分の提出コードを公開したいと思います。詳しい問題内容と解説は後日CodeIQMagazineあたりに掲載されると思うので、その際にリンクを張りたいと思います――覚えていたら(´・ω・`)
2016-12-29追記: CodeIQMagazineに本問の解説記事が掲載されていました。またほかの方が公開されたコードがToggetterにまとめられています。
# 問題文に従うと「進む距離m」は(格子点の数 - 1)となる。
# (格子点の数) = (w + 1) * (h + 1) だから、F(m)は次を満たす(h,w)の組み合わせの総数である:
# (w + 1) * (h + 1) - 1 = m <=> (w + 1) * (h + 1) = m + 1
# 言い換えるとF(m)は「m+1の約数のうち、1でもm+1でもないものの総数」とわかる。l
# 以上の性質を利用すると「1<=m<=nとなるすべてのmに対するF(m)の和」G(n)は次のように考えることができる
# 2<=x<=n+1となるすべてのxについて、「xを約数にもつがxではない、n+1以下の整数」の個数の和
if __name__ == '__main__':
n = int(input())
t = n + 1
answer = sum(t // x - 1 for x in range(2, t + 1))
print(answer)
コメントをのぞくと 実質的なコードは4行。それもやや冗長に書いて4行ですから、もっと短くすることもできそうですね。
個人的には興味深い問題でした。「格子路をらせん状に歩くとき、その歩く距離の組み合わせの総数を求める」という、一見するときわめて複雑な問題提起ですが、よくよく考えていくと「x以下の自然数の約数の個数の総数を求める」というところにまで収れんします。要するに本問は「複雑そうに見えても、その本質はシンプル」というタイプの問題であり、解答者は周辺的な情報を一切無視して、単純な中核部分にだけ取り組めばよいということになります。
複雑な事象に対してその複雑さを維持したまま取り組むのは愚策です。複雑さの本質を直感し、その本質にアプローチする。それこそがシステム開発あるいはプログラミングの基本であり、パズルを解く楽しみのひとつでもあるとわたしは考えています。