HTTF2022本戦お疲れ様でした！予選落ちしてしまっていたのでオープンコンテストでの参加です。最終的に55,693,436点を獲得してオープン1位、本戦参加者と合わせても4位を取ることができました。出来過ぎな結果で驚いています。

というわけで今回も解説を書いていきます。例によって無数の解法のうちの一つでしかないため、誤解なきよう。

f:id:terry_u16:20211219103200p:plain — ビジュアライザ (seed=0)

問題概要
前提知識
忙しい人向け解法
解説
参加記
感想
おまけ

問題概要

お掃除高橋くん*1 に掃除をさせるプログラム*2 を書いてね。プログラム長はできるだけ短くしてね。

atcoder.jp

前提知識

巡回セールスマン問題の解法（bit DP、焼きなまし法、貪欲法（例：Nearest Neighbor法）等なんでもOK）
01-BFS（ダイクストラでも代用可）
最短経路の復元
ランレングス圧縮

忙しい人向け解法

HTTF本戦お疲れ様でした！55,693,436点でオープン側1位決定かな……？
200(2(LrrF)3(RllF))みたいなのが雑に強いので、係数部分をグリッドサーチして掃除しきれなかった部分についてTSPをやりました。TSPは基本Nearest Neighborで、上位10個だけ2-optで仕上げました。 https://t.co/UiQyvnjCNj #HTTF pic.twitter.com/RB6peOvzw6
— TERRY (@terry_u16) 2021年12月18日

解説

大まかには次のような流れで、3段階に分けて解きます。

右手法・左手法を組み合わせたループを作成し、雑に掃除する。
掃除しきれなかったマスに対して、巡回セールスマン問題を解く。
得られたプログラムに対し、ランレングス圧縮をかけることで解とする。

以下、思考過程を交えてもう少し詳しく説明していきます。

制約に着目する

全部のマスを掃除すると点数が跳ね上がる*3ので、高得点を狙うなら全マスの掃除は必須です。となると全てのマスを訪れる必要があるため、この問題は巡回セールスマン問題の亜種と言えそうです。

したがって巡回セールスマン問題を解いてからプログラムの圧縮を頑張ればOK……という気もしてきますが、この圧縮はかなり難しそうです。*4 もっと良い方法はないでしょうか？いきなり実装に手を付ける前に制約をじっくり眺めてみることにします。以下の制約が重要です。

基礎命令を1つ実行するのに1単位時間かかり、 $5000$ 単位時間以内で掃除を完了しなければならない。出力されたプログラムが $5000$ 単位時間で終了しない場合は $5000$ 個目の基礎命令を実行後に打ち切られて停止する。

$5000$ 単位時間という制約がどの程度厳しいものなのか、ざっくり見積もってみましょう。フロアの1辺の長さは $N=20$ であるため、マス目の数は $N\times N=400$ です。1つのマスに前進命令（F）1回、方向転換命令（L or R）1回の合計2命令くらいが必要と雑に仮定すると、だいたい $400\times 2 = 800$ 単位時間くらいで掃除ができそうです。 $5000$ 単位時間までにはかなり余裕があります。 $5000$ 単位時間以下であれば $800$ 単位時間で掃除を終えても $5000$ 単位時間で掃除を終えても得点は同じなので、 $800$ 単位時間しか使わないのは少々もったいない気がします。*5

もう少し時間を贅沢に使ってしまいましょう。何か適当な命令グループを何度もループさせると、時間はかかりますがプログラム長はかなり短くて済みます。これを終盤までループさせて、残ったマスだけで巡回セールスマン問題を解くと、プログラム長を相当短縮できそうです。

右手法・左手法

上記の「何か適当な命令グループ」には何を使えばよいのでしょうか？様々な候補が考えられそうですが、ここでは迷路の解法の一つである右手法・左手法を使うことにします。これは迷路の右側の壁に手をついて、壁沿いに進んでいくという方法です。

結論から言うと、右手法はRllF、左手法はLrrFをループすることで実現することができます。本当にこれで実現できるのか試してみましょう。下図のように進路の左・正面・右に壁がないケースを考え、右手法の命令グループであるRllFを適用してみます。

f:id:terry_u16:20211219120907p:plain — 初期状態

できるだけ右側の壁に沿って歩かせたいので、まず右を向かせましょう。R命令を実行します。

f:id:terry_u16:20211219121136p:plain — R命令まで

正面に壁があると前に進めません。その場合は左を向かせることにします。l命令を実行すると、正面に壁がある場合だけロボットが左を向きます。その場合、右手は必ず壁に付いた状態になります。

f:id:terry_u16:20211219121258p:plain — Rl命令まで

再度l命令を実行します。全てのロボットが壁に右手を付いた状態で、なおかつ壁のない方向を向きました。

f:id:terry_u16:20211219121418p:plain — Rll命令まで

この状態でF命令を実行することで1マス前進します。あとはこれをループさせれば右手法の完成です。同様に左右を入れ替えることで、左手法もLrrFで表現できます。*6

右手法・左手法の組合せ

あとは右手法をループさせればいい感じに掃除してくれそうな気もしますが、これだけではダメです。下図のように、壁が外周と繋がっていないケースでは上手くいきません。

f:id:terry_u16:20211219123328j:plain — 右手法だけではダメな例

このループを脱出するには適当なタイミングで違う動きをすれば良さそうですが、かといってプログラム長が長くなることは避けたいです。ここでは、右手法と左手法を交互に繰り返すことでループの脱出を試みます。具体的には、x, y, zを正の整数として、z(x(RllF)y(LrrF))という命令グループを実行することにします。

これだけで上手く行くのか？という気がしますが、結構上手く行きます。たとえばseed=0にてx=1, y=2, z=417として417(RllF2(LrrF))という命令を実行すると、400マス中395マスを掃除することができます。

ループ回数の全探索

上の例ではx=1, y=2, z=417としましたが、上手く行かないケースもあります。例えばseed=6だと、400マス中82マスしか掃除できませんでした。あらゆるマップに対応できる(x, y, z)を決定できれば良いのですが、なかなか難しそうです。そこで、(x, y, z)のペアを全探索することにします。*7 各ペアについてシミュレーションを行い、最も良かったものを採用すれば良いでしょう。

何をもって「良い」と判断するかについては、例えば以下のような判断基準が考えられます。

z(x(RllF)y(LrrF))だけで掃除できたマスの数
z(x(RllF)y(LrrF))終了時のマップの状態を初期値として巡回セールスマン問題を解き、プログラム長が最も短かったもの

今回は後者を採用することにします。

巡回セールスマン問題

掃除しきれなかったマスに対して巡回セールスマン問題を解きます。マスからマスまで移動するときのコストは命令実行にかかる単位時間としても良いですが、Fを連続して3回以上実行するときは3Fのように圧縮できるため、ランレングス圧縮後のプログラム長をコストとするとより正確に見積もれるでしょう。*8

巡回セールスマン問題の解法はbit DP、焼きなまし（2-opt等）、Nearest Neighbor法などがありますが、好みのものを使用してください。マスからマスまで移動するときのコストは、全マスを始点として01-BFS（ダイクストラでも可）を実行することで $O(N^4)$ で前計算しておきます。 $dist[i][j][dir][k] :=$ マス $(i, j)$ にいて、 $dir$ 方向を向き、 $k$ 連続でFを実行中のときの距離*9 と定義しておくと良いでしょう。

ランレングス圧縮

最後に、得られたプログラムに対してランレングス圧縮をかけて完成です。複雑なアルゴリズムは適用しませんでしたが、もしかしたら賢いアルゴリズムを使うことでもっと縮められるかもしれません。

まとめ

以上で必要な部品は全て揃いました。いくつか工夫を加え、最終的な解法は以下のような流れとしました。

全てのマスのペアについて01-BFSを実行し、圧縮後のプログラム長を基準としたコストと単位時間を基準としたコストを前計算しておく。
パターンをz(x(RllF)y(LrrF))またはz(y(LrrF)x(RllF))と決め打ちした上で、(x, y, z)のペアを全探索し、最終的な解の候補を作る。
1. z(x(RllF)y(LrrF))による動きをシミュレートする。
2. 残ったマスに対し、1.で求めたコストを使ってNearest Neighbor法により雑に巡回セールスマン問題を解き、最終的なプログラム長を見積もる。Nearest Neighbor法は基本的にプログラム長を基準としたコストにより次の頂点を求めるが、コストが等しい場合はタイブレークに単位時間を基準としたコストを用いる。*10
3. a.とb.を合わせて $5000$ 単位時間以内で終了しなかった場合は棄却する。そうでない場合は最終的な解の候補とする。
2.で得られた候補のうち、プログラム長の短いものから個を取り出して詳細に検討し、最も良いものを採用する。
1. 各候補の巡回セールスマン問題パートに焼きなまし法を適用し、プログラム長の短縮を試みる。*11
2. $10$ 個の解のうち、最もプログラム長が短いものを採用する。
得られたプログラムに対し、ランレングス圧縮をかけることで解とし、出力する。

これを提出すると、55,693,436点が得られました。seed=0のビジュアライザはこんな感じです。

atcoder.jp

解説は以上です。

参加記

参加記というか、コンテスト中の思考の垂れ流しです。ここだけ常体です。

～0h05m 初提出

問題を読む。圧縮とかどうやるんだ……。TSP*12中にそんな同じ移動パターンが続くことある？天才的なコードゴルフ能力が求められるんだろうか。

とりあえず左手法とか使ったらいい感じに回れるんじゃないか？最序盤で記念に1位を取ってみたいので、雑に9999(LrrrF)とかいう文字列を出力してみる。3,597点。弱い。1ケースあたり36マスくらいしか回れていない。ビジュアライザを見て納得。

～0h10m 右手法を追加

左手法だけだとダメだけど、右手法も交えて交互に壁を伝っていったらそれなりにまんべんなく回れるんじゃないか？ついでにrも3個から2個に減らして9999(7(LrrF)7(RllF))とかいう文字列を投げる。ループ数を7にしているのは素数の方がループにはまりにくいような気がしたため。29,104点。1ケースあたり291マスだし悪くないのでは？ビジュアライザを見ても大きく改善されている。

暫定1位なので記念にツイートしておく。こんな序盤の1位に何の価値もないんだけど、振り返ってみれば開始10分で右手法・左手法の組合せを思いつけたのはかなり良かった。

～0h30m ローカルテスト環境整備

8時間の長丁場なので、じっくり環境整備を進めていく。まずはローカルテスト環境整備。以前のコンテストで作っていたものを流用して、256ケースを並列で流すプログラムを作った。適当に(x, y)のペアをいじって何度か流してみる。パラメータ次第でそこそこ性能が変わりそう。

このテスト環境は終盤までめちゃくちゃ役に立った。こういうの短期コンだとサボりがちだけど、毎回やった方が良さそう。

～2h00m 考察・コード整備

この時点でトップが1000万点くらい。桁の違いにビビるけど、冷静に計算してみるとプログラム長は1ケース1600文字とかそのくらいっぽい。このあたりちゃんと考察した方がいいな。

問題を丁寧に読み直す。 $5000$ 単位時間制限に目が留まる。どのくらい余裕があるんだろうか。1マス2命令と仮定すると $800$ 単位時間だからかなり余裕がありそう。右手法＋左手法のループをたくさん回して、残ったマスだけ巡回セールスマン問題すると効率が良いように思える。マップは既知なのでシミュレートも可能。

考察は引き続き進めていくとして、コードを書いていく。今回は長丁場なので結構丁寧に構造体等を整備した。具体的には、

命令を入れ子構造の列挙型として整備
グラフを隣接リスト形式に変換
命令を処理するシミュレータを整備

あたりをやった。シミュレーション結果のスコアとビジュアライザのスコアが一致するところまで確認。この時点でコード長は300行弱。実装重いけどこういうライブラリ系の整備は楽しいね。これのおかげもあってか今回はほとんどバグに悩まされなかった。

～3h30m 初期解の実装

整備ができても解が作れないと意味がないので、初期解の実装に移る。方針は先ほど考えたものを採用。最初のループ命令は140(5(LrrF)2(RllF))で固定。その後01-BFSを全点間でやって、それを使ってTSP。TSPはめんどくさいのとバグらせる気しかしなかったのとでとりあえずNearest Neighbor法でお茶を濁す。さらに経路復元とランレングス圧縮。

実装が重い。500行を超えた。助けてくれ。

どうにか書き上げて手元でテストケースを回す。かなり良い。投げると25,218,707点でオープン暫定1位になった。嬉しいのでツイートしておく。

～4h15m (x, y) の全探索

昼ご飯（カレー）を食べて後半戦へ。

テストケースを手元で回してみると、良いケースと悪いケースがはっきりしていることに気付く。悪いケースをビジュアライザで見てみると、140(5(LrrF)2(RllF))で掃除できたマスの数が100マスにも達していなかったりする。どうも最適なループ回数はマップによって違いそうなので、z(y(LrrF)x(RllF))の(x, y)を全探索してあげればよさそう。zはこの時点では $\left\lfloor\frac{4000}{4(x+y)}\right\rfloor$ で固定。最も多くのマスを掃除した(x, y)のペアを採用することとする。

どう考えてもスコアが伸びるので投げる。39,346,364点で本戦・オープン合わせて暫定1位。やったね。

～4h40m 評価関数の改良

掃除したマスの数を評価関数としていたが、その後のTSPパートも考慮して最終的なプログラム長の推定値を評価関数にした方が良さそう。マス同士の間のコストを前計算しておけば、Nearest Neighborは軽いので十分回る。投げると40,909,571点。微増だけど良くはなったので採用。

～5h10m (x, y, z) の全探索

zは $\left\lfloor\frac{4000}{4(x+y)}\right\rfloor$ で固定してたけど、もうちょっと攻めて $\left\lfloor\frac{4750}{4(x+y)}\right\rfloor$ あたりにしてみる。48,408,569点。上がりすぎだろ。4000も4750もそこまで変わらないと思ったのに。掃除してないマスが少し減っただけでもスコア的にはかなり効くのか。

この値も全探索に入れた方が良さそう。4700から4900まで10刻みで探索することにする。42,927,030点。 $5000$ 単位時間を超えるケースを忘れていた。修正して51,526,404点。5000万点超え！

～7h00m TSPパートの改善

ビジュアライザを見るとTSPパートで謎に無駄な往復をしている。コストをプログラム長で見ているから直線上にあるマスは全部同じコストになって、遠くのマスを先に選んでしまうことがあるのか。タイブレークとして実距離長を考えることにする。52,211,524点。

あと改善できるところといったらTSPパートくらい？もう実装750行に達してるからかなりキツいんだけど……。Nearest Neighborで上位10個残した後、仕上げに2-optの焼きなましを入れることにする。53,407,900点。ここでbit DPを思い付けなかったのは反省。

～8h00m 初期パターンのバリエーション追加

今まで左手法→右手法の順番しか試してなかったけど、右手法→左手法の順番も試してみた方が良さそう。z(x(RllF)y(LrrF)), z(y(LrrF)x(RllF))の両方を全探索することにする。55,682,429点。終盤で伸びたのは大きい。パラメータを微調整して、55,693,436点でフィニッシュ。最終的な実装量は1000行弱。

感想

私がヒューリスティックコンテストにはまるきっかけになったのは、ちょうど1年前のHTTF2021本戦オープンでした。ビギナーズラックで総合11位を取ってしまい、それをきっかけにここまで熱中してしまいました。それからちょうど1年の節目に総合4位を取ることができ、とても嬉しく思います。ツカモさんをはじめとしたHTTF関係者の皆様、本当にありがとうございます。来年は予選通過できるように頑張ります。

www.terry-u16.net

今回の問題は良い方針が閃くかどうかがカギになった気がしますが、私は閃くことができたのでめちゃくちゃ気持ちよかったです（最悪）。とはいえ手がかりはちりばめられていたので、閃き一発勝負ではなく一つ一つ辿っていけばある程度再現可能なように感じました。制約の大きさも8時間というコンテスト時間も絶妙だったように思います。本当に面白かったです。

今回のコンテスト中の立ち回りはもう二度と再現できないんじゃないかというくらいの出来でした。いつも序盤に飛ばして終盤に息切れすることが多かったのですが、今回は終盤までちゃんと改善を続けられたのが良かったです。今回だけで終わらせず、今後もこの調子で続けていきたいなと思います。

f:id:terry_u16:20211219145625p:plain — 順位推移（AtCoder Marathon Replayより）

f:id:terry_u16:20211219145646p:plain — スコア推移（AtCoder Marathon Replayより）

おまけ

なお、本選は unrated です。
— ツカモ (@tsukammo) 2021年12月7日

そ、そんな……。

*1:かわいい。

*2:以下、お掃除高橋くんを操作するための命令L, R, l, r, Fと繰り返し処理により構成される文字列のことをプログラム、その文字列長をプログラム長と呼ぶことにします。C++やPythonなど汎用言語によるプログラムと混同しないように注意してください。

*3:399マス掃除するだけだとテストケースあたり399点しかもらえませんが、お掃除高橋くんのプログラム長Lは高々5000文字にしかならないため、400マス掃除した場合はその時点で20008点以上得られることが確定します。

*4:規則性のあるマップではないため、圧縮しやすい同じ命令グループが連続で出現するという確率はかなり低そうです。

*5:こういうシチュエーションは現実にも結構ありそうです。5時間の外出中にロボット掃除機を稼働させる場合、清掃時間は1時間でも5時間でもユーザーには影響がなかったりとか。

*6:行き止まりになっている場合はどうなるのか気になりますが、実は今回の問題では行き止まりが存在しない（各マスの次数が2以上）ことが保証されています。また仮にそうでなかったとしても、RllFを2回繰り返すことで行き止まりを脱出することができます。

*7:zは5000ターン制限に引っかからないギリギリまで大きくした方がいい気もしますが、zを大きくすることで掃除していないマスから離れていってしまうケースも考えられるため、こちらも全探索することにしました。

*8:3連続でRを実行する場合はLを1回で代用でき、その逆も同様のため、圧縮についてはFだけを考えれば十分です。

*9:kは0, 1, 2以上の3つの状態を考えれば実用上十分かと思います。

*10:タイブレークを入れないと近くのマスを無視して遠くのマスに行ってしまうことがあるため、タイブレークを入れて近いマスを優先的に選ぶようにしています。

*11:ここは@c7c7さんの解法のようにbit DPも適用した方が良いです。残されたマスが十分少なければ実行時間内に厳密解が求められます。

*12:Traveling Salesman Problemの略です。

TERRYのブログ

最近は競技プログラミングにお熱。

HACK TO THE FUTURE 2022 本選オープン解説＋参加記