🦔

AHC054参加記(33位)

に公開
競技プログラミング
AtCoder
競プロ
ahc
tech

概要

AHC054に参加した記録です。

良い成績が取れたので考察をまとめた記事を投稿することにしました。
どんな工夫をしてどれだけスコアが上がったかを時系列で書きました。
何かの参考になれば幸いです。

  • レート以上の成績が出せた
  • 暫定35位, 最終33位
  • パフォーマンスは橙色の2454、入青
  • ルールベースで大事だったのは2つ
    • カタツムリ（渦巻き、袋小路）を作る
    • 左右に分割する
  • 高度なことはせず、泥くさいBFSで一つ一つコーナーケースをつぶしていった
  • 夏休みを利用して時間で殴った (提出回数: 90回)

https://x.com/i/status/1972608398228361545

試したこと

  • カタツムリ方式の囲い
  • 左右の分割
  • ミルフィーユ方式での囲い
  • 囲いの焼きなまし -> ボツ
  • 特定のパターンを敷き詰める -> ボツ
  • 分割した後にあばら骨みたいな構造を作る -> ボツ

スケジュール

大学の夏休みが長く、コンテスト期間はフリーだったのでフルで時間を使えました。社会人の方や、アルバイトなどで多忙な方と比べると何倍も時間を割くことができました。

1日目

まずは、0を出力するだけのサンプルコードをC++に書き直しました

提出して動作の確認後、方針を立てて提出しようとしましたが、インタラクティブなAHCは初めてで、入出力形式の違いに手間取りました。
今まではWebのビジュアライザだけを頼りにやっていましたが、ローカルテスターを使うしかないと理解して環境を整えました。

この時点で100位前後だったと思います。スタートダッシュ賞には当然届かず、あきらめて寝ました。

2日目

到達不可能になってしまうマスが発生し、無駄が生じていたのでたどり着けるマスが減らないことを設置する条件に追加しました。また、インタラクティブを利用して移動先の視界をふさぐようにしました。

ここで、最後まで使うことになるbfs_score関数を定義しています。プレイヤーの位置からたどり着けるマスの数を数える関数で、花(AA)にたどり着けない場合は0を返します。トレントを配置したとき、この関数の結果に変化がない場合は問題のない変更とみなします。

ここらへんで、どんな構造が良いのか真面目に考えることにしました。AAがむき出しになっているのが好ましくないのは明らかなので、その延長で考えました。カタツムリ状だと途中で帰ってくれることに気付いたので、カタツムリ状に配置してみることにしました。

マジでルールベースです。向きも定まっています。キュー（ここではvector）にpushして、後に先のbfs_score関数で問題がないなら置くことを繰り返すだけです。

        // ゴールをカタツムリ状に囲む
        if(first_flag){
            first_flag = false;
            vector<int> di = {-1, 0, 0, 1, 2, 2, 2, 1, 0,-1,-2,-3,-3,-3,-2};
            vector<int> dj = { 0, 1,-1, 1, 0,-1,-2,-3,-3,-3,-2,-1, 0, 1, 2};
            rep(i,di.size()){
                cand.push_back({ti + di[i], tj + dj[i]});
            }
        }

なぜこの形が良いかの解説はいくつか上がっていたので省略します。

plasmaeffectさんの記事がとても分かりやすいと思います。
https://zenn.dev/plasma_e/articles/1705ad6dda1b2e

かなり良いスコアです。

この日は32位で終了しました。
このあたりで、今回のAHCは良い成績が取れそうだなと思いました。

3日目

カタツムリをどんな場合でも作れるようにしました。たくさんバグらせました。
基本方針は、AAから迷路を右壁に張り付いて回るときに左側に壁を生成していくようなイメージです。
とてもルールベースです。
(右壁と左壁の2パターン) × (初めに出ていく方向4パターン) = 8パターン をすべて試して、できるものを採用します。

あまりスコアが上がっていないです。それもそのはず、ゴール周りに木があって凹構造がある場合にとても弱いルールベースになってしまっていました。
2日目の方法で囲いを作れない場合、周囲に邪魔な木があることが多く、この手法でも囲いを作れないことが多いため、変化が小さかったのだと思います。

同じようなパターン例を複数作って全部試したほうが良かったかもしれません。

  • カタツムリが置けない場合は前までの4近傍をふさぐ囲いに (236262)

例外をケアしてスコアを上げました。

上がりました。この後は囲いの細かいバグを修正したり、囲いを選ぶ評価基準を定めたりしました。

さらに、囲いの評価基準にスタート地点を含めないことを追加するとスコアが一気に上がりました。

  • 囲いでスタート地点を含めない (323258)

この辺りで13位になり、AHC最高の瞬間でした。

この日は最後に凹構造への耐性と壁が近い場合の耐性を囲いに付与して終わりでした。

  • 囲いで凹構造と壁に対応 (360670)

この日は最終13位でした。

4日目~6日目

4日目から6日目はスランプでした。
様々な方法をためしましたがなかなか劇的に改善するものは得られず、絶対スコア36~37万付近をうろうろしていました。

ルールベースだと例外やバグに弱そうだったので、焼きなましで囲いを作れないかチャレンジしました。しかし、解空間がうまいことなめらかになるような近傍と評価関数を設定できず、安定して強い構造を作ることはできませんでした。
ここで作ったUnion Findを使って良い構造かを判定する評価関数は最後に使うことになりました。

あとは、カタツムリの構造を他の場所に置くとどうなるのかと試してみましたが、うまくスコアが上がりませんでした。ビジュアライザを見た感じ、ゴールよりも優先度が高くなるのは好ましくないのかなと思いました。ジグザグに視界をふさぎながらトレントを配置する方法は案外よかったのかもしれません。

他の構造もためしてみましたが、改善する結果があっても理由はよくわからず、程度もそこまで大きくなかったので保留しました。

ゴールまでの経路をふさぐような工夫もしました。これはカタツムリ構造が作れなかった場合でも、ゴールに近づく方向をふさげば同じような構造ができると考えたからです。ここでは実装が良くなくて、のちに修正することになります。

6日目終了時点で44位まで落ちてしまいました。

7日目

スランプ気味になってしまったので、問題について整理して一から考察をやり直しました。

左右に分断する方法を前日の夜思いついたので、実装してみました。

montplusaさんのツイートと同じ気持ちで、一度通った道を何度も通ってほしいことと、目的地に向かう際、他の未確認地点を見てほしくないことを考えました。

https://x.com/montplusa/status/1972613413206716640

左右に分断すると、少し改善しました。

スタートを含むと良いと考えたというより、これしか思いつきませんでした。ほかの方の解法でナナメにやっているのをみて、なるほどと思いました。
が、改めて考えると通路内に初めから入っていてもらったほうが、左に行くためにはここを通らなきゃいけない！とわかってもらえるのでよさそうです。

左右に分断する際、マスのロスを許していなかったのですが、数マスのロスを許すとスコアが若干改善しました。

改善は誤差レベルではあるので、この差に踊らされたのは良くなかったです。
ローカルテスターでは特定のケース(seed=0,19,70など)のみ試し、全体の平均はとって確認していませんでした。
やったほうが良いと思いつつ、面倒でやりませんでした。反省です。

実装はほぼBFSです。強い形が崩れないように、ゴールには近づかないようにしました。

この日は最高25位、最終27位で終わりました

8日目

分断時BFSにいくつか不具合があったので修正しました。進路妨害でゴールが近い場合の不具合も修正しました。後者はスコアに影響ありません。

3万ポイントほど上がったので、致命的な不具合だったみたいです。

開始27位、最高22位、最終27位

9日目

カタツムリにバグがあったので修正しました。

分断の考察を進め、3車線に変更しました。左右を行き来するためのルートが一つであることを確実に知ってもらえるために、少なくとも2車線で壁から壁までつながってると良いです。実装したところスコアが伸びました。

AAの囲いにミルフィーユ方式を採用しました。これはカタツムリが発動しなかった場合の保険で、バグりにくいですが、スペースを広くとってしまい、そこまでの堅さもありません。

AAからの4近傍を壁にして、この壁と元あった木の8近傍を通路にして、さらにその周りを壁に..と繰り返しました。基本的に袋小路であるわかればいいので、壁は3層程度で十分です。壁と通路ができたら、通路から壁を通って次の層の通路へ、通路のゴールから最も遠いマスから壁を通ってまた次の通路へ..と繰り返します。壁際に強いです。

文字列はこの方式で壁と通路を層のように重ねたものです(seed=2)。偶数が通路、奇数が壁で、0がスタート地点です。

.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.......66666666......
......6655555566.....
.....66544444456.....
..66665443443456.....
.665554433333456.....
.654444332223456.....
.6543432221234566....
.6544322121234456....
.6554321012233456....

下の画像はこの時に生成される初期盤面です。

ここでの評価には焼きなましの時に作った評価関数を採用しました。これに通った場合はゴールやその付近がターゲットでない限り、途中で帰ってくれます。問題は良い構造でもNOが出ることですが、妥協しました。

少し下がりましたが、システムテストに含まれる例外を見越して採用しました。

開始30位、最高25位、最終33位

10日目

分割した後、あばら骨のようにしようとしましたが、うまくいかずスコアが5割~6割くらいまで下がってしまいました。方針としては間違ってなかった気がするので、実装方法に問題があったのかもしれません。

最後のチャレンジで、ゴールの位置に応じて入口の位置を変えるようにしましたがスコアが下がってしまいました。ゴールから遠いほうに通路の入口が配置されるようにしたつもりでした。

結局、ミルフィーユ方式をちょっと改善したり、他の部分を手直ししたりしたものを提出しました。

開始35位、最高33位、最終35位

システムテスト

システムテスト後、35位から33位に上がりました！

システムテストの内容を確認してみるとTLEが...

3000テストケース中2つのTLEで済んで助かりました。
確認してみると、近い順位の人はMLEやWA, TLEを出している人が多かったです。

ルールベースでいろんな仕組みを追加したことと、BFSを使いすぎたことがどこかのシードで影響してそうです。
手元で試したテストケースが100個だったのも悪手でした。
自動で複数回のテストを実行してくれるツールがあるみたいなので、次回は利用するべきです。

また、後から気付いたのですが、ミルフィーユ方式が動いていませんでした。原因は提出前に囲いの中にスタート地点が含まれていた場合に無効とする判定のバグです。修正後に確認するべきでした。

まとめ

カタツムリ状の囲いが強いことに早々に気付けたことと、これによって左右に分断するアイデアがわいてくるまでの時間を稼げた点が良かったのかなと思います。
また、詰まったときに考察を一からやり直せたこともアイデアがわいた要因だと思います。

インタラクティブは使ってるようでほとんど意味はないです。運です。無根拠です。ほかの方の方針にあるように、DFSで直径の大きな木を作るというような工夫がもう少し出来たらよかったかもしれません。

上位と比べると、下のような要素が足りていなかったようです。

  • 実行時間の有意義な利用
  • 罠の設置
  • インタラクティブを利用した囲い
  • 普通の通路の生成方法の考察
  • ルールベースからの脱却
  • TLEの出ないコード
  • 十分な数のテストケースでのテスト

Discussion