追記(20140124): paizaさんから景品のロックスター30本頂きました！ありがとうございました！
最近話題のpaiza主催のコーディングコンテストにチャレンジした。
キャンペーンの設定では、野田さんはコードの書ける社長令嬢とのことで、つまり社長の名前も野田さんなのであり、色々な意味で悶々としてしまいますね。
以降、ネタバレ含む真面目なアルゴリズムの話になりますので、自力でチャレンジしたい方はご注意ください。
ソートして尺取り虫
事前に全組み合わせをキャッシュしようとしてタイムアウトになる、などのお約束をこなしつつ、最初に考えたのが、商品の値段をソートしてしまい、上と下から範囲を狭めていって組み合わせをチェックしていく方法。最初のスタート地点を探すときに二分探索するのも含めて、やり方としてはhttp://sucrose.hatenablog.com/entry/2013/12/05/000146と同じですね。こんなに綺麗に書けませんでしたが。
これに加え、チョット経ってから、和が目標値と一致したら探索終了していいことに気づいて直した時点で、0.01/0.01/0.28というタイムが出た。
ソートが相当遅いのでソート相当の別のことをする
この時点でNYTProfでボトルネックを探してみると、適当に作った100,000件の商品データで、入出力5割、ソート4割、探索1割、という塩梅。ソートを何とかしないとコレ以上タイムが伸びないと思い、色々調べて、目についたのがdankogaiさんのバケットソートの記事。ただし、コレそのままではかえって遅くなってしまう。
作成したヒストグラムの分布範囲が広すぎて、全走査すると時間がかかりすぎるのだ。そこで考えをすすめて辿り着いたのが、ヒストグラムの作成だけして、値の探索は直接ヒストグラム内を走査する、という手法。
実は元の問題設定の特徴として、商品点数に比べてキャンペーン日数が極端に少ないというのがある。また、商品の価格の上限に比べて商品点数がかなり多い。商品点数がかなり盛られていると思われるcase3では、かなり密度の濃いヒストグラムが出来ると予想されるので、走査の能率はそれほど悪くならないはず。更に、実際には走査されない部分=探索に使用されない価格がかなりあることも想像できるので、それらを無視できるというのもメリットになる。
工夫としては、低い数字側から必要になった部分だけ配列に入れ(バケットソートの出力を逐次行う感じ)再利用時の高速化を図っている。
また、ヒストグラムの走査についても、その時点で見つかっている最も優秀な値を更に上書きする可能性のある範囲だけに絞り込める。極端な話、すでに目標値-1の組み合わせが見つかっている場合、配列を一回参照すれば次に進むことができる。
などなどを行い、最終的にクリナップしたコードが以下のもの。このコードのタイムは0.02/0.01/0.18。
なお、このやり方は商品価格の分布が一様だという仮定に依存していて、商品価格に偏りがあった場合に効率が著しく落ちる可能性がある。チロルチョコ専門店でキャンペーン価格は1,000,000円とか言われると目も当てられない。が、とりあえず用意されているテストケースに対してはうまく行ったようなので良しとする。
case1のタイムが落ちてしまったのは、単に商品点数が少なく、走査範囲が広いため。コレをカバーしたいなら商品点数が少ない場合だけ分岐してソートして尺取り虫すればよい。
クリナップ前のコードのほうが速くて悔しい
上ではかっこよく説明しているが、きれいな実装に辿り着くまで、変なマジックナンバー使ってみたりと、かなり試行錯誤した。その途中で自己最速タイム0.01/0.01/0.15という記録が出ている。昨日の時点(12月6日)では、perlおよびLL(PHP,ruby,python)でのレコードにもなってる。まだコードがグチャグチャで、自分で見なおしても何をやっているのかわからない部分も多く、なぜ速いのか謎のままである。
あ、あとこういうのはハッカソンとは言わないと思います。
おしまい。