ハル研究所プログラミングコンテスト2015 参加記

はじめに

去年に引き続きハル研究所プログラミングコンテストに参加しました。
前回参加した時は60位くらいでツライ記憶しかなかったのですが、今年は4位に入ることが出来ました。

f:id:t-pro-6q:20160202000218p:plain

自分がこれだけ高い順位に入れるコンテストというのを今まで経験したことがなかったので純粋に嬉しい。

1位の人の解法は公式のホームページに載っているので、この記事の存在意義がほとんどないのですが、~~よくある手法でこの順位までいけましたという自慢がしたかったので~~ネットで検索してもコンテスト参加記自体があまりなかったので自分がやったこと等を書き起こすことにしました。

問題

問題パッケージは2年前までのものについてはダウンロードすることができるので、取り組もうと思っている人は早めにダウンロードをしておいたほうがいいかもしれません。
www.hallab.co.jp

問題概要

営業所には複数個の荷物が保管されていて、各荷物には届け先が決まっています。
届ける時間が指定されている荷物に関しては、指定された時間帯に運ばなければいけませんが、そうでない荷物に関してはステージ終了時に配達が完了しているのであれば、どの時間帯に運んでも構いません。
荷物を運ぶ際に、1マス移動する毎にトラックの重さと積んでいる荷物の重さの分だけ燃料を消費してしまうので、
この消費燃料ができるだけ少なくなるように荷物を運んでください。
荷物の数は各ステージ最大で16個となっています。

黄色の動き回っているのがトラックです。かわいい。
０以上の数字が書いてあるマスが、その時間帯に運ばなければならない荷物の届け先で、負の数字が書いてあるマスが、時間帯が指定されていない荷物の届け先となっています。
f:id:t-pro-6q:20160201235134g:plain

おおまかにやったこと

なにはともあれ、最短ルートは計算しないとなにも出来なさそう→実装

ステージ内の荷物がすべて運ぶ時間帯が指定されているとした場合、巡回セールスマン問題を頑張って解けば最適解が得られそう→実装後、時間帯が指定されていないものについてはとりあえずトラックに詰めれるだけ詰めて出発させる。→30000000点獲得

後は時間帯が決められてない荷物(以下、長いので自由荷物と呼びます)をどの時間帯に運ぶのがいいか探索しよう→とりあえずビームサーチ→理論値到達

あとはひたすらに高速化を行いました。

最短ルートについて

最短ルートは各荷物から幅優先探索を行うことで最短ルートを求めることが出来ます。C++の場合標準テンプレートのqueueを使えば簡単に実装することが出来ます。

巡回セールスマン問題について

巡回セールスマン問題とは、ざっくりいうと「出発点と複数の目的点が与えられた時、各目的点を少なくとも1回ずつ通ってから出発点に戻ってくるときのコストの最小値を求める」問題です。
NP困難として知られ、多項式時間では解けないのですが、今回の問題は荷物のサイズが16個と少ないので厳密解を求めることが可能です。詳しい求め方はここでは省略します。「巡回セールスマン問題 bitDP」等で調べれてもらえればいろんな記事が出てくると思います。

ビームサーチについて

マラソン系コンテストに参加するにあたって必須といってもいいテクニックであるビームサーチを今回は使用しました。

今回の問題について、自由荷物を配達する時間帯を全探索することができれば最適解が得られるのですが、制限時間内に処理が終わらないので、自由荷物を配達する時間帯を幅優先探索で調べる際に、自由荷物の配達の仕方を毎回評価関数というもので評価をし、評価値のよいもの上位K個を次の探索候補として探索を行っていきました。

※K=3としたときのビームサーチのイメージ
f:id:t-pro-6q:20160202002936p:plain

評価関数はそのまま、「(自由荷物を含めた)配達時間を決めた荷物を最適に配った時の消費燃料」で評価しました。

また、ビームサーチをするときに気をつける点として、同じ状態集合を含めないということが挙げられます。

例えば、今配るべき荷物が全部で10個あり、そのすべてが自由荷物であるとしたとき、以下の２つは一見違う状態の様に見えますが、実際に消費する燃料は同じであるので、そのような状態が複数次の状態集合に含まれないようにしないと、上位K個のうち大半のものが同じ状態集合となってしまって、最適解を得ることが出来ません。
f:id:t-pro-6q:20160202003814p:plain

ビームサーチをする際、「営業所からの距離×荷物の重さ」の大きいものから探索を行っていくと、コストの大きい荷物で距離が近いもの同士は同じ時間帯に、そうでない荷物は違う時間帯に振り分けられることが多くなり、ビーム幅を狭めても最適解が出やすくなります。

コンテスト期間中は大学のサーバーを使って1000個ほどのテストケースでテストし、以下のような結果を得ることができました。
f:id:t-pro-6q:20160202004804p:plain
最終的には全応募作品が再評価されることを利用して、ビーム幅を5ずつ変化させた作品を大量に提出しました。

高速化について

今まで参加してきたマラソンマッチ系のコンテストでは高速化フェーズにまで入れないことがほとんどだったので、本格的に取り組んだのは今回が初めてです。
なので、ありきたりなことしか出来ていませんが自分が取り組んだことについて箇条書きの形式で書き起こします。

・プロファイラツールを使用してどこがボトルネックになっているかを調べる。
・再帰関数は一般的に重い処理なので、ループ文で書き直せる部分は書き直す。
・評価関数は新しい状態ができるたびに適用されるので、重点的に高速化する。
・値の使い回しができるところは再計算しない。
・連想配列のキーにはできるだけシンプルなものを(int等)使用するようにする。
・標準ライブラリは基本遅いので、自作できるものは自分で作る。
・無駄な計算をしない(自分の場合、連想配列に突っ込まなくてもいいものまで突っ込んでいて遅くなっていたりしました。)
・配列は次元が小さいほどアドレス計算を省略できるので、次元を落として書き直す。

配列の次元を落とすのはコードの可読性が落ちるのでもうやることがなくなったと確信を持ってからやらないとダメです。今回のコンテストで学びました。あとプロファイラがすごい便利だなーと感じたりもしました。

感想

冒頭にも書きましたが、今回の大会では自分の想像以上の順位に入ることが出来たので、その点では良かったのですが、荷物を配達する時間を決めるアルゴリズムについてはもっと考察をするべきだったなと反省しています。

ランキング上位者は荷物の決め方も動的計画法でやっていたり、分枝限定法でやっていたりしていて、なるほどなーと感じました。ただ、どういうアルゴリズムを使えば効率的に解けるか、といった部分に関してはこれから色んなコンテストを経験するにつれて身についていってくれると自分を信じています。

プログラムを上手く書くコツはプログラムを書かずにじっくり考察すること、というのを身をもって体験しました。自分はせっかちなので問題が出されたら結構見切り発車をしてしまい、結果として良いスコアが出なかったり、あるいは無駄なコーディングをしてしまったりするので、今後はそういった点について特に気をつけていきたいです。

たこし++の備忘録

競技プログラミングの備忘録