もふふろぐ

10月10日から10月27日まで開催されていたハル研究所 プログラミングコンテスト2017の結果が発表されました。 ハル研プロコンへの参加は3回目です。 最終結果では総ターン数22,213で95位になりました。

今年の問題は、平面上で10体のUFOを動かしすべての家にできるだけ早く配達をするというものでした。 昨年よりもサンプルコードが控えめで、総ターン数は112,793でした。 ここからチャレンジスコア22,222を目指すことになります。

コンテスト中に実装した方針とその結果を表にまとめました。

方針	総ターン数	時間（秒）
k-meansで家をクラスタリングしてから小型UFOに分担させる。	36,750	0.0312
家を偏角でソートしてから小型UFOに同数ずつ分担させる。	31,681	0.0390
大型UFOを移動可能な農場として利用する。	22,410	0.3906
小型UFO間で担当を調整する。	22,213	0.7578

荷物の受け渡しをどのようにして経路に組み込むか悩まされました。 終わり際の提出コードでは、クラスタリングを改善するループを回しています。 しかし、実装に時間を掛けたわりに、思っていたほどターン数を減らせませんでした。

知人の方針を聞くと、どうやらクラスタリングより経路探索を重視したほうが良い結果を得られたようです。 面倒がらずに色々な方法を試すべきだったと反省しています。