最終スコア10795247で222位でした。

基本方針

スコア計算式を見ると、見渡せていない座標があった場合明らかに損であることがわかります。

そこで、端から順に未見の座標を探して、見つかったらそこに移動する、経路はBFSで最短のものを探す、を繰り返す、をしました。

他の方針はコンテスト中に思いつかなかったので、最後まで基本的な方針は変わりません。

時系列まとめ

開始

最初だけでも暫定順位稼いでやろうと欲張って、自明な正の点数を得ることを今回はしませんでした。（が、これで焦りまくることになる・・・。）

第0.9世代

袋小路に入っても無駄なので、まず袋小路を封鎖してから基本方針に沿って探索をしました。方針を固めて実装を終えるまで、1時間20分もかかってしまいました。

が、なんとWA。

ちゃんと確認したわけではないですが、袋小路を封鎖するロジックに穴があった模様です。

第1世代

とりあえず一度ACがほしいので、袋小路を封鎖するロジックを全てコメントアウトだけしてビジュアライザで確認すると、なんとスコアが増えました。おーいｗ

提出すると、無事ACで7514401点をゲットしました。

第2世代

f:id:mdstoy:20210807222308p:plain

袋小路を除去するロジックを一旦排除したため、上図左端のように袋小路に入ってしまっています。

そこで、未見位置の探索で行き止まりが見つかったときは、そこから最も近い交差点を移動先に変更します。

これで8500805点まで伸びました。

第2.1世代

f:id:mdstoy:20210807222833p:plain

上図のように、袋小路でない部分では中途半端な位置まで侵入してしまっていたので、それについても対応します。

具体的には、元々の迷路の壁だけでなく、すでに見た部分も壁とみなして袋小路かどうかの判断をさせました。

これで8730337点になります。

第2.2世代

第2.1世代の修正が一部おかしかったらしく、元々の袋小路にも何故か突っ込んでいることがありました。修正するのですが、よかれと思ってやった修正で思った通りに動いていないとかスコアが下がるとか思ったほど上がらないとか、ヒューリスティックあるあるにひたすらハマります・・・。

散歩にいったり気分転換をはさみつつ、なんやかんやで9113276点までは伸びました。

第3世代

袋小路を探索するロジックを、上からと左から見ることに特化して書いていたので、それまで未見位置の探索を(0, 0), ..., (0, n - 1), (1, 0), ..., (1, n - 1), ... としていたのを(0, 0), ..., (0, n - 1), (1, 0), ..., (n - 1, 0), (1, 1), ..., (1, n - 1), (2, 1), ..., (n - 1, 2), ... として、左から見る方にも振ってみたらちょっとましになるんじゃないの？と思ってやってみると、これがハマったらしく、10795247点になって8桁に乗りました。

ここで残り時間が少なくなっていたのと、やりたいことがほぼなくなってしまったので実質終了でした。