golf001

CodeIQでOzyさんがCのGolf問題を出してるのを今日知った。
https://codeiq.jp/challenge.php?challenge_id=1049
http://codeiq.hatenablog.com/entry/2014/08/26/154814

以前、CodeIQで同じようなgolfの問題に参加した時は、辛くも5位タイでした。
https://codeiq.jp/ace/ozy4dm/q310

そんなわけで、今回もさっそくチャレンジしました。ネットワークの勉強そっちのけで。

問題的には前回にもまして単純な内容で、入出力一回ずつという簡単仕様。
コードゴルフ的なテクニックよりもアルゴリズム(と言うか計算式)勝負な感じです。

n番目の値を求める場合、アルゴリズム的にはO(n)かO(1)になるのが普通で、今回はO(1)の方が短くなります。
どうせこのブログ見てる人殆どいないので、最初に投稿したO(n)のコードと、golfの解法的なものを少し書こうかと思います。(解答のコードを載せるのはやめました)

最初に、これは投稿したコードではないですが、まずは求める答えの例を出力します。

ひとまずこれで、100までの数字の2の倍数でも3の倍数でもない数字の数列が出力されます。
次は、何も考えずにそれらを足すコードにします。これを入力値の回数分だけ足すコードにすれば一応回答として成立します。
ただし、これではあまりにもなので、すこしデータを解析して数列のパターンを掴み、計算で求めるヒントを掴みます。

スクリーンショット (3)

こんなかんじで、nと数列と答えをグラフ化してみました。
すると答えは指数的な増加をしていることがわかります。

さらに、1~10の総和を求めるアルゴリズムをプログラム初心者は一度はやると思いますが、あの解法を思い出すとこの問題に色々当てはまったりしますね。

おっと、もし参加者がここを見つけてしまったらまずいので、ヒントはこの辺りまでにしておきます。

Pocket

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)