ハル研究所 プログラミングコンテスト2019

10月1日から10月15日まで開催されたハル研究所 プログラミングコンテスト2019に参加しました。 今回でハル研プロコンへの参加は5回目です。

コンテスト終了時点での総ターン数は70,479で、記念品贈呈の対象である30位以内には今年も入れませんでした。 学生とハル研究所社員限定であるハル研プロコンに参加できるのは今年が最後なので、全力を尽くしましたが、上位との実力差を痛感する結果に終わりました。

過去の記事

• 2015 宅配便
• 2016 小惑星群から地球を守れ！
• 2017 UFOのお手伝い
• 2018 がんばれ！街のお菓子屋さん

問題概要 カメの早食い競走！

• 30×60のグリッドで表現される広場がある
• 広場のランダムな座標にカメ (6～25匹) とエサ (40, 60, 80, 100個) が配置されている
• エサには高さ (1～カメの数) が設定されている
  • 一様な乱数を初期値として「高さを (1～現在の高さ) に変更する」処理を0～2回繰り返す
• 各カメは独立に1ターンごとに上下左右に移動できる (待機もできる)
• エサがあるマスにその高さ以上のカメが集まっているときカメはエサを食べる
• すべてのエサを食べるか1000ターン経過するとステージ終了
• 制限時間60秒で240ステージ分繰り返し総ターン数を競う
  • カメの数 20通り × エサの数 4通り × エサの高さの分布 3通り

考察

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

サンプルコードでは、すべてのカメがエサ0から順に食べに行く実装がされており、多くのステージで1000ターンを超過していました。 （総ターン数 232,221）

初めに、そのエサの順序の最適化を巡回セールスマン問題として（とくに高速ではない実装で）解いたところ、総ターン数は約96,000になりました。

このままではエサの高さに対して必要以上の数のカメを使ってしまいもったいないので、余るカメを次のエサに先に向かわせることにしました。 また、その様子をシミュレートし、エサの順序の一部を反転・シフトしながら山登り法で最適化することを試みました。 すると、低いエサをある程度分業して回収できるようになり、総ターン数は一気に70,000台まで縮まりました。

チャレンジスコア（達成者のうち5名に記念品が贈与される）である77,777に早い段階で到達できたことは心の平穏をもたらしました。

しかし、これ以降は難航し、各ステージに使う時間を一定でなくしたり、エサの高さの分布によって場合分けしたりしましたが、70,000を切れずに終わってしまいました。 最終的な30位の総ターン数は約61,000だったようです。 途中、巡回セールスマンから離れて、上手な貪欲法を考えることにも努めましたが、72,000に止まりました。

山登り (ステージ239: 458ターン)

貪欲 (ステージ239: 538ターン)

ビューア

例年のようにハル研プロコンには便利なビューアが用意されていますが、総ターン数の改善が進むと、ヒートマップがだいたい緑色になって傾向がわからなくなるので、配色に手を加えました。 このとき、単にスコアや色相の範囲を広げるだけだと緑～黄あたりの見分けがつかなくなってしまったので、ease-in-outのような関数で補正しました。

変更前

stageColor: function (no) {
  var d = 1 - (this.stages[no][5] - this.minColorTurn)/(this.maxColorTurn - this.minColorTurn);
  d = Math.min(Math.max(d, 0), 1);
  return 'hsl(' + (d*120|0) + ', 100%, 50%)';
},

変更後

stageColor: function (no) {
  var d = 1 - (this.stages[no][5] - this.minColorTurn)/(this.maxColorTurn - this.minColorTurn);
  d = Math.min(Math.max(d, 0), 1);
  d = d < 1/2 ? 2*d*d : -2*(d-1)*(d-1)+1;
  return 'hsl(' + (d*240|0) + ', 100%, 50%)';
},

また、今回はステージ生成のパラメータが周期的に変わっていたので、60ステージごとに改行することでステージによる結果の違いを比較しやすくしました。

感想

5年間の集大成となるような結果を目指して臨みましたが、またしても記念品圏内に入ることが叶いませんでした。 考察の仕方や採用するアルゴリズム・実装には成長を感じていましたが、結果が伴いません。 来年以降にはハル研プロコンに参加できないと思うと寂しい気分になります。 魅力的なコンテストを開催してくださったハル研究所の方々に感謝です。