AHC039 に参加しました(154位)

概要

AHC039 に参加しました。324873 点で 154 位でした。周りでなかなか見なかった解法だったので、自分の解法を軽く残しておきます。

seed=66, score=3241

基本方針

フィールドをグリッド上に分けて、(サバの数) > (イワシの数) となっている領域を選択する。選択した領域は、 "F" みたいな形のパーツを使ってつなげる（以下、この部分のことを F と呼びます）。

F みたいな形のパーツを使ってつなげた

F を作るためにの領域分無駄にしてしまうのですが、あまり影響はないと判断しました。

当初は全体の領域でやろうとしたのですが、辺の長さの総和の制約を大幅にオーバーしてしまったので、小さい領域で F を構築することにしました。

一番最初のテスト

改善したこと

以下のような改善を行いました。それぞれの寄与分はあまりわかりませんが、全く効果が無かったものはありませんでした。

• グリッドの幅を変える
• グリッドの縦横のマス数を変える
• グリッド全体をずらす

解法のデメリット

非連結なグリッドの選択ができるのがこの解法の強みなのですが、それゆえに辺の長さの総和の制約が相当ネックでした。

考えたけどやらなかったこと

F の不必要な部分について取り除く

実装が大変なことになりそうだったのでやりませんでした。そもそもこの解法に至ったのも、実装を簡素なものにするためだったので。

多点スタート

実は、生成した結果をビジュアライズしてみるとグリッドの縦横のマス数は高々 2x3 程度になっているケースが大半でした。そうであれば、あらかじめ形を決め打って焼きなましをしようと考えたのですが、これが思いついたのはコンテスト終了 30 分前だったのでやりませんでした。

こんな形が多かった