AtcoderのHeuristicコンテストAHCへの参戦記録。暫定333位だった。
https://atcoder.jp/contests/ahc054
護衛トレント
最初の週末の時点で、AAを渦巻き配置のトレントで護衛する方針を立てた。９０°回転４通りと、裏返しの計８通りの中から、最も始点からの距離が遠くなるものを選ぶ。８通りとも既存の木が通路を邪魔してしまう場合は、外側の護衛トレントから順に無くしていき、それぞれ８通り試し、置ける配置の中で最も渦巻きが長いものを選ぶ。
一重の壁では、反対側のトレントが認知されていない時に、知らずに中まで突き進んで偶然見つけられてしまう事がある。下の図はサンプルの0031番で、冒険者は目的地（赤枠のマス）に向かって進もうとする。たまたまその方向に護衛トレントの入口が向いている場合、本当は行き止まりにも関わらず、壁となっているトレントを確認できていないので進めると思い込み、護衛トレントの中に侵入してしまう。行き止まりであることに途中で気づくが、そのときには伝説の花を見つけてしまう。
全方位に2重の壁になるようにしたら一時100位以内までグンと上がった。これだけでも、ほとんどのケースはほぼ全マスを確認済みの緑にできる。下図は最もスコアが良かった0092番で、5216点。護衛トレントの中まで到達しつつも、AAの発見まで至らず引き返している。
確認済みになると、次の目標地点の選択肢から外れるので、目標に偶然AAが選ばれてしまう確率が上がってしまいまう。偶然選ばれてしまったら最早どうしようもないので。一方で、護衛トレントにはむしろ早く確認して貰わないと、行き止まりなのを知らずに入ってきてしまう、という葛藤。上記のような壁を進行方向に沿って並べていくと、確認されたマスは増えにくいが、護衛トレントにも気づいてくれない。
謎のWA
左上の(-2,-3)の位置にトレントを置くと、何故か1ケースだけWAになる不具合があり、最後まで解決できず。このマスだけ抜いた渦巻きで提出。ただ、終了後の3000ケースのシステムテストでも引っかかる恐れあり。その後、その位置が森の入口だったケースではないかとの指摘があり、検証したところ、そのとおりだった。護衛トレントを置くロジックには、初手だから不要と思って入れていなかった確認済み判定を追加したところ、全てACした。