ひたすらがんばるAHC008

ゆーと

AHCお疲れさまでした。35位だったみたいです。HTTF予選でも35位だったらしい。ブルゾンちえみ。

画像1

109回の提出。メモ代わりに提出するからこうなる。やめようね！

問題概要

自分がいる区画に動物がいないように柵をたてて区切りましょう！

区画が広ければ広いほど高得点！動物がいれば点数半減！

動物は5種類いていろんな動きをするよ。

やったこと　～1日目～

問題を読んで理解した瞬間に思いついたのがこの案でした。盤面を4分割して一番多いところを刈るだけの簡単なお仕事です。犬が邪魔だった。コードを書いている途中で、人が重なっていれば犬のロックオン対象をコントロールできることに気づき、犬を引き連れる係を作りました。

画像2

左下で犬に襲われる（？）人。

やったこと　～2-3日目～

犬の動きをコントロールすることを考えて、いわゆる「犬小屋」を作りました。動物が少ないところに人を入れることにも成功。

4分割した部屋どの方向でも、動物がいなければいつでも閉じられる最強の人の配置。すごい。（下図、右上に行くべきですがバグです）

画像3

この時点でなんと1位。マジで？　一時的でも1位になったの初めてです。

画像は11億点のものですが、いろいろバグを取って20億点まで伸びました。しかし、この解法、理論上25億点までしか取れず、方針転換を決意。

やったこと　～4-5日目～

他の人のビジュアライザ見ながら、固定配置が良さそうだという結論に。

一手で閉鎖空間を生み出すことができ、置く柵の数が少ないこの形を採用。

画像4

初期段階。途中で閉じ込められるなら閉じるという動作も行ってます。

これでも30億点超えるみたいです。左下閉じれてないなぁ（バグ）

画像5

固定配置設計のコードの一部です。全部手書き。しかもmの値によって設計順が違うため、6通りの盤面を全部手書きしました。パワー。

画像6

よい子は真似をしないようにしよう

（どうすればよかったんですかね？）

やったこと　～6-14日目～

上記のアイデアをビジュアライザ等で分析しつつ、改良を重ねました。

画像7

Excelすごい。パワー。

具体的には、以下の内容を改良しました。

・犬小屋の横幅の調節
・構築中、閉じ込められる動物が出現次第、一番近い人が閉じ込めに行く
・固定配置の構築順と動き方（点数ロスが大きい部分をなるべく遅く構築）
・最後1体だけは捕まえやすさを優先して柵を立てる
・最終ターンが来た場合、点数が上がるように貪欲に動く
・配置構築後、ゾーンディフェンスをがんばる（曖昧）
・各種不具合の修正

画像8

大層なアルゴリズム使ってない（多分幅優先探索だけ）ですが、

結果52億点まで行きました。

手元1000ケースでは捕まえられなかったケースが26ケース程。

ビジュアライザの賛否

ビジュアライザから得られる情報が多く、上位勢が共有してしまったらすべてが破壊されるのでは？と思っていましたが、賞金付きコンテストで上位勢がそんなことをするはずありませんでした。

個人的に、競技としてはナシだとは思います。が、コンテストを活性化させるという面では大いに役に立つので難しいですね。

ただ、強い人は共有ありでもなしでも強い。

総評

猛者だらけの場所で思ったより戦えて、　ぼく、満足！

どの人数/動物数でも同じ形を組んでいた点は今考えると改良できましたね。

めっちゃ疲れた。生活崩壊もしたけど、ヒューリスティックコンテスト超楽しい！！！

コンテストにこんなに時間をかけられるのは学生のうちだけなので、これからはコンパクトなコードを書くのを意識しないといけないですね...　やってるうちに身につくかな？

ここまでのヒューリスティックコンテスト、ほぼ貪欲系しか書いていない気がするので、焼きなましとかいろいろやってみたいですね...

いいなと思ったら応援しよう！