お久しぶりです。西村です。久々にAHCでいい結果がでたので記事にまとめます。ほんとはコンテストの翌日ぐらいに公開したかったのですが、現実世界のお仕事が忙しく今日になってしまいました。

問題文はこちら（https://atcoder.jp/contests/ahc039/tasks/ahc039_a)

問題を要約すると、良い魚と悪い魚が分布していて良い魚だけを囲いたい。領域の広さは縦横10万、使える網の長さは40万。網は垂直もしくは水平にしか設置できない。

ビジュアライザーでは良い魚は赤く表示されているので、赤い魚だけをできるだけ多く囲えばよいです。

提出1: スコア 150 / パフォーマンス 639　

※パフォーマンスはコンテスト終了時点でのランキング表を基準にしています。

https://atcoder.jp/contests/ahc039/submissions/59648760

一部を囲ってあげればプラスの場合、マイナスの場合があり、マイナスはカウントされないので点数があがるだろうという回答です。結果的に端っこの100×100を囲っても何も囲えずだめだったようですが、ACしました。よく考えると全体の100万分の1の面積しか囲っていないので、5000匹しかいないプラスの魚を囲える確率は低かったです。

提出4: スコア 142992 / パフォーマンス 1123

https://atcoder.jp/contests/ahc039/submissions/59649566

全体を縦横N等分に区切って一番よいセルを囲いました。Nは2が最良だったので2で提出しました。囲い方を4通り試して一番よかったのを出力する。それだけなのですが、緑上位です。

提出5: スコア 370266 / パフォーマンス 1939

https://atcoder.jp/contests/ahc039/submissions/59654405

縦横を均等に1分割～20分割し、一番良いセルを優先度付きキューに入れる。優先度付きキューからは良い順に取り出し、取り出したあとに隣接セルで優先度付きキューに未追加なものを追加する。網の長さ※1が400000を超えたら打ち切るという手順で囲う範囲を決めました。この手順で囲う範囲を決めると、網が二重になるような不正な構造が発生するため、不正な形になった場合には解として採用しないものとしました※2。ちょっと手直しすれば解として使える場合もありもったいなさそうにも思いましたが、面倒なので処理が複雑になり過ぎそうだったので素直に棄てました。採用する水域を確定できたらあとは時計回りに出力した。※3

提出6: スコア383256 / パフォーマンス 1993

https://atcoder.jp/contests/ahc039/submissions/59654864

網の長さ400000じゃなくて、330000で打ち切ったらなんか上がったので、提出したら実際に上がってた。よく考えてみたら、途中でベストな状態になってることが分かったので提出7に続く。

提出7: スコア430403 / パフォーマンス 2154

https://atcoder.jp/contests/ahc039/submissions/59655411

網の長さが400000とか330000に達した時点で評価するのではなく、網を伸ばすごとに得点を評価して最善の値を出すようにした。結構のびた。

提出8: スコア437342 / パフォーマンス 2180

https://atcoder.jp/contests/ahc039/submissions/59655696

網の長さは単調に伸びるわけではないので、400000を超えても処理を継続し、長さが400000以下の場合だけ提出解として採用するようにした。

提出10: スコア444692 / パフォーマンス 2214

https://atcoder.jp/contests/ahc039/submissions/59655696

上限を20分割を45分割に変更した。

提出17 スコア461750 / パフォーマンス 2284

https://atcoder.jp/contests/ahc039/submissions/59659805

乱択した。最初は、優先度付きキューに入れるときにノイズを乗せたが殆ど効果がなかった。雑にビジュアライザを観察すると、区切りの位置を変更しないことには点数が伸びないように思われたため、グリッドの縦横の長さを乱択した。

最終提出のイメージ

ところで

以下の提出でスコア68950 / パフォーマンス 1006 でます。なので、AHC難しいって思わず、参加者増えてくれると嬉しいな。

4
0 0
0 50000
100000 50000
100000 0

今後の課題

乱択ばっかりやってないで焼きなませるようになりたい（もしくはビーム）とか、グリッドを段階的に分割していく方法は思いつかなかったので使えるようになりたいとかありますが、AHCは失敗してもレーティング下がることないので気軽に参加していきたいです。そして、アルゴリズムもAHCと同じようなレーティングの仕組み＋レーティング減衰が実装されるとよいのにな。

注釈

※1 グリッドのある領域を塗る場合に網の長さがどう変化するかは、接している領域の塗り数だけに依存する。グリッドのサイズをLとするとき、接している領域が0だと4L、1だと2L、2だと0、3だと-2L、4だと-4Lだけ伸びる。

※2 外から幅優先や深さ優先で塗りつぶして全マスを塗ることができれば合法。角が接しているような場合は調整できるはずだけど、面倒なので棄てました。

※3 あるマスが選択されているとき、上が選択されていなければ上には網が必要。左、右、下も同様。必要な網をそれぞれのマスを中心に時計回りに作っておけば、どこから辿っても一周ぐるっと回ってこれてうれしい。（のだが、座標系を適当にやっていたため混乱してばぐりちらかした。最終的にはちゃんと実装できた）