HTTF2024(AHC027)メモ

Seed＝０

HTTF2024(AHC027)に参加したメモみたいな日記みたいな記事です。コンテストは12/1からだったんですが12/2までは仕事の合間に問題見たりダウンロードしたりしたくらいで取り組んだのは12/3からということでそこから。

12/3

貴重な1日休みなので、朝遅めに起きてスプラやって玄関に飾るクリスマスリースを初めて手作りして裏庭の枝が伸びすぎたクルミや松の枝刈りをして午前が終わった。昼食べてよーしAHCやるぞー、その前に買い出しってことでコンビニ行ってあれこれ買って今度こそAHCやるぞーってパソコンに向かうも、なんか眠くて頭働かないのでちょっと昼寝して、で、起きて甘いものとか食べながらポチポチやってたらようやくエンジンかかってきた(午後4時)。まず入力もらう。グリッドのセルとセルの間の壁が与えられるやつ。前回ようやく気付いたんだけど、これは移動できるマス同士を繋ぐグラフで持てば良いよね。出力はUDLRの羅列なので特に問題なく。で、とりあえず正のスコア取れる解を作るには全部のマスを回ってスタート地点に戻って来なきゃいけなくて、どうすればいいの？とサンプルコードを見る。DFSか。普段ヒューリスティックでは最短ルートを知りたいことが殆どだからBFSばかり書いてるけど、まぁキューをスタックにすれば良いのだし。とPythonのコードを見ながらDFS書き始めたんだけど数行で「行って帰って来るって面倒くさそうだし、その後そこから改善していける気がしないな」と思ってやめて自分なりにAC取る方法を考える。近い未踏のセルに移動していって最後(0,0)に戻ればいいのでは？じゃあやっぱりBFSだな。BFSは全てを解決する。とばかりにBFS解を書いて見る。実行するとツラツラと塗りつぶして行って無事AC。でもサンプル解よりいいのか悪いのか分からないなということでサンプルコードをchatGPTにC++に翻訳してもらって実行。何の問題もなく一発で動くのね、すげーな。で比較するとBFS解の方が良さそう。よし投げるか。第一投にしてはまぁまぁ。ビジュアライザ見ていて、雑にマンハッタン距離の近い未踏のセルに移動してたのが壁越しに行ったり来たりして無駄に見えたので、ちゃんとBFSで最寄りの未踏セルに移動するようにしたら若干改善したので第二投。

12/4

ビジュアライザを見てるとやっぱり汚れやすいところは何回か行かないとダメそうなので(ビジュアライザ見なくてもそう)汚れ度の高いところをある程度回ってから未踏セルを巡回してみる。逆に一度全部回ってから汚れてるところを回ってみる。汚れてるところ回って全面清掃してまた汚れてるところを回る。などなど試してみて2番目のが良さげだったので提出。31G乗って180位。おお。思ったより良かった。

12/5

スコア計算がきちんと出来てなかったけど、この後焼きなましやビームサーチは出来なくても山登り、いやせめて乱択はしたいので、スコア計算をデバッグ。printfで内部の計算途中の値をドバっと出して見て修正していったら公式のテスター(vis)と一の位までピタリと合うようになって気持ち良い。

12/6

汚れるとこから汚れるとこへの移動の合間に未踏セルを経由するとどう？と実験してみたけど改悪に終わる。

12/7

小手先の変更ではやはりダメそう。未踏セルをある程度回ったら汚れるとこを掃除、を繰り返すようにしてみるか。ある程度ってどの程度？与えられたデータから計算できる？まずはn分割を一通り試してみるか。で、1から20分割まで試して1番良いのを出力するのを提出。4TLE。時間管理しないとだめかー。でもふと順位表見ると33Gに伸びてる。TLEあってもそれ以外の点数は有効なんだっけ。高速化もちょっと想うところあるけれどとりあえずは1800msで打ち切りに直して、でも4TLE直してもさほど変わらないかーと思いつつ提出。おお35G乗った。提出結果を見たらまだ1TLE。1700msにして再度提出。ぬ？36Gで167位？！1TLE馬鹿にならないな。

12/8

セル間の距離を知りたいときいちいちBFSしてたんだけど、今回はマップは固定なので初めに全セル間の距離を求めておいて使い回す高速化。デバグ用のグリッド表示。ルートを探すとき、未踏セルを優先。などをした。

12/9

この日も1日休み！でも12月の貴重な休みなので、午前は床屋、午後は花壇整理したり庭の勝手に生えた木切ったり玄関脇のなんちゃって枯山水整たりしてたら午後4時。休日まるまるAHCに注ぎ込んで進捗なかったりしたらかなり後悔しそうなので、やることやって残りの時間でやるくらいがいいかなーみたいな弱腰な姿勢。で、ビジュアライザ見るとルートがくるくるしたり行ったり来たりしてるので、汚れるセルで囲まれたセルも汚れるセルの仲間にしてある程度塊にしてやったりとか、汚れないセル回ってるときにもう少し残ってるってとこで汚れるセルの掃除に行っちゃうので汚れないセル掃除の個数をランダムに増減して一番良いのを出力する乱択にするとかしてジワジワと改善。39Gで150位でこの日は終了。

12/10

最終日だけど仕事あるのでちょこっと思いつきを実験して改悪に終わってほぼおしまい。牛舎で順位表やX見て「上位争いアツいな～」と思ってたら初提出でいきなり1位の人が現れてビックリ。すげー！自分はというと1700msで打ち切ってた乱択を1900msまで伸ばして再提出したんだけど、終了13分前に「攻めすぎかな」と思って牛舎からスマホで1850msに直したやつを再々提出して終了。結局山登りもせず貪欲と乱択で終わり。暫定で180位38G。

結果＆感想

システスでTLEが10個以上あったようで180位から201位まで落ちてしまいました。間に合ってるのはほぼ1800ms台でTLEは2200ms超えなので、最後に50ms加減したのはあまり関係なかったのかも。でも青パフォが取れて良かったです。

今回とにかくビジュアライザが高機能で楽しかったし助かりました。ありがとうございます。あとwataさんの解説もいつもだけど簡単な自明解から初めてステップアップしていって「そんなスコアが？！」みたいな驚きもあってすごいなぁと思います。途中の上位の抜きつ抜かれつや最終日に初提出の方が優勝をかっさらっていった展開も下から眺めていてアツかったです。ほんと楽しいコンテストでした。12日からのMMも貪欲頑張ります（たまには焼けよ）（いや無理）。