日本橋ハーフマラソンに参加しました
予選
http://rco-contest-2017-qual.contest.atcoder.jp/
A問題
まずサイズ２のミノを作って，それらを繋げてサイズ４のミノを作って，それらを繋げてサイズ８のミノを作りました．
結果は640400点で109位でした．
B問題
事前にエサ間の距離を求めておいて，訪れるエサの順番をビームサーチっぽく探索しました．
結果は13658点で44位でした．
全体では66位で学生では42位でした．
本戦の学生枠は40人だったのですが，なぜか予選を通過しました．
本戦
http://rco-contest-2017-final.contest.atcoder.jp/
A問題
スコアの計算方法を見ると石油をDリットル売る度にD^2のスコアが得られるようになっているため，Dが小さいときに石油を売るのはあまり嬉しくないことが分かります．よって，できるだけ大きいDについて石油を売ることを目指すという方針にしました．具体的には以下のようなことをやりました．
- D>31のとき，石油タンクにfillすることで時間TまでにDだけ石油を用意できるならfillしてsellする．
- 上を満たさないならば，5未満の石油タンクを一つchangeする．
- 上を満たさないならば，空の石油タンクを一つfillする．
- 上を満たさないならば，passする．
結果は7169275点で3位でした．
B問題
問題名から分かる通り，愚直に実装すると大渋滞を起こしそうだったため方針を決めるのにだいぶ悩みました．悩んだ結果，選んだ方針は以下の通りになりました．
- 各車について一番近い四隅を目的地に設定する．
- 目的地が遠い車から順に目的地に近づくような移動ができるならば移動する．移動できないならば1/2の確率で離れる移動をする．
- ある程度すべての車が目的地に近づいたらマップを４分割し，分割したそれぞれのマップで車の目的地を一番近い四隅に再設定する．
- 上記を繰り返す
動き方の様子は以下の動画を見ると分かりやすいかもしれません．
youtu.be
結果は86021点で5位でした．
全体では2位で学生では1位でした．
懇親会
懇親会ではピザとケンタッキーのチキンがありました．（残念ながら🍣はありませんでした．）他には，Typing War対決とかやってて面白かったです．
来年もまだ学生なのでぜひもう一度開催してほしいです．
