golf002

前回のCodeIQの問題はあらかじめ最後に上位5位までのコードを公開しますとあったが、今回の問題は特に記載されていないので公開されない可能性がある。ので、今回はあまりコードを書いた記事は控えることにします。

さてさてそれはそうと、今回の順位表を見ていると、3位集団のソースコードは完全に予想がつく。
それに対し、2位のコードは何故1位まであと1byte足りないのか若干気になる。
1位同等のテクニックを利用しているが、単に結合順位や数式的な順番に気を取られて、暗黙の型変換という便利なコンパイラの機能を忘れているだけなのか(自分も最初忘れてた)、あるいは別の方法で縮めたのか。後者の場合がどんなコードか気になる。

上級の壁を超えられない人たちはおそらくO(n)のコードなんだろうな~と思う。
今回のような出力が1つの問題でO(n)のコードを書いた時には「何かおかしいな」と気づく野生の勘みたいなもの身に付けて、O(1)のアルゴリズムに切り替えればすぐに10byteくらい縮まるので頑張って欲しい。多分O(n)で考えるコードの方がO(1)のコードよりよっぽど難解なものになってしまってる筈だ。
簡単なアドバイスを出すと、まずはコードとにらめっこするのをやめて数列や最終出力をエクセルなんかで求めてその法則性を知ることだ。前の記事でも書いたが例えば数列の前の値との差はどうなってるのか。

スクリーンショット (4)あるいは、ダイレクトにn番目の答えを求める計算式はないか(要するにこれがO(1)のコードになるんだけど)などだ。
数列をグラフ化してみるのはいいアイデアだ。離散的な数値でない限り何かしらのグラフ的法則があるはずだ。
真っ直ぐなのか、二次曲線なのかとか。いろいろ考えてみるといい。

さて、3位の方たちはいろいろ悩んで縮める方法を考えているだろう。
だが、これをどうにかするにはgccの実装やかなり低レベルの層の動作を知らなければならないので、自力で解決するには非常に高いスキルが必要で現実的ではない。なので手っ取り早く色んな人の書いたコードを読むのが良い。例えばアナーキーゴルフ(http://golf.shinh.org/)通称:アナゴルなど、ニコニコの戀塚さんも一時期参加してたり日本の参加者も多いジャッジサイトだ。
ここでは永久に出題中の問題と、終了日が決まっている問題があり、終了日が決まっている問題は終了後にコードが公開される。
自分に高いスキルがなくとも、上級コーダーの技を盗むことはいくらでも出来る。(今回の自分のコードも以前盗んで覚えた技が使われてる)

で、件の技というやつだが、特定の条件下でしか使えず、コードの書き方に制限も増える。その代わり冗長なコードをまるまる消すことができる裏ワザだ。 自力で解決したい方はぜひともアセンブラを解析して、変数やレジスタの値を書き出して考えてみてはどうだろうか。

Pocket

コメントを残す

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

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