【PostMortem】HTTF2024 (AHC027) - MON.T+α Programming Room

※画像は公式Visualizerよりお借りしています

はじめに
問題の概要
最終提出の解法
おわりに
おまけ

はじめに

　この記事は2023/12/01 - 2023/12/10にAtCoderで行われましたAHC027の解法を紹介するものになります。いつもは冗長に書いているのですが、今回はいつもとちょっと違う切り口で、他の人の言及が少なそうなところを中心に書いてみます。（決して時間が取れなくて雑に書いているとかでは）

　気を付けてはいるのですがところどころうっかり打ち間違っているかもしれません。間違いを発見されましたら優しく教えていただけるとありがたいです。

問題の概要

こちらは問題文を見ていただいたほうが早いと思われるので割愛します。簡単に言えば「部屋の汚れの平均が小さくなるように掃除ロボットを動かす」という問題です。

問題文はこちら

atcoder.jp

この問題では与えられた各マスの汚れやすさに比例して汚れの値がたまっていくので、汚れやすい所へは多めに掃除に回るのがよさそうという印象を受けます。

最終提出の解法

以下、最終提出の概要です。

言語:go言語

　これはただの好みです。

解法:評価値をもとに1マスずつ動く貪欲

　以下はTwitterで行った解法ツイートです。

暫定14位　最終提出の方針
・「今の場所から最も評価値の高い場所をもとめ1マス進む」貪欲を可能な限り繰り返す
・最近通った場所についた場合は機械的にルートを反転させたり・・・
— MON.T+α (@montplusa) 2023年12月10日

今回用いた評価値はほとんど同じ方針のものがAHC公式放送で述べられていた(公式放送にて√dにしたら44Mになったといわれているもの)ので、AHC公式放送の該当の解法をご存じない方はぜひご覧ください。（該当の解法以外にもいろいろ述べられていて参考になりました）一応、この先のセクションではそのあたり詳しいことは知らなくても、「最も評価の高いマスに1マス近づく」という貪欲を繰り返していることだけ知っていれば楽しめる内容になっています。

AHC公式放送（該当の解法の前準備は22:30くらいから）

www.youtube.com

　公式解説では各マスの汚れを√dで計算する(本来の汚れを√dで割る)という方法が用いられていますが、実はこれは(現在のそのマスの訪問回数)で割ることで似たような結果が得られるので、こちらを採用しています。このほうが実際のマスの位置関係による行きやすさが若干反映されてよいような気がします。

貪欲の限界に挑戦

　もう他の方の解法を確認している方はご存じの通り、このコンテストにおいて貪欲解法には大きな壁があります。というのも、貪欲解法はこの問題の持つ以下の特徴に対して弱いからです。

・道中うろうろしながらコンスタントに成果をあげることが大事

(評価値として、最短経路でないパスを用いた場合にあげられる成果を考慮しようとすると途端に難しくなる)

・かたまって汚れているエリアはとりきれないとすぐに戻ってくる羽目になる

(貪欲では汚れているエリアを分断するように突っ切ってしまうor途中で別の汚れているエリアの目標に方向転換してしまうことがあり、少ししてまた無駄に戻ることになる)

　最終的に順位表の最上位あたりにいる方々のスコアは私の感覚では貪欲では達成できなさそうだな・・・という印象なのですが、貪欲でもここまではこれたよ、ということで一部をここに残しておこうと思います。誰か貪欲でさらに良い結果が出せている方がいれば教えてください。

貪欲における47.7Mの道のり

46~47Mあたりまでは改善の繰り返しで比較的順調だったのですが、そのあたりを超えてからはいろいろ苦しい中もがいていた記憶があります。もがいていた時に一番効果があった「反転テクニック」をここでは紹介します。

最近通った道についた場合に直近の経路を反転する

貪欲で移動経路を決めているときにいちばんよく起こるのが「ここさっき通ったばっかじゃん」パターンです。ということで、これを解消するために経路の反転を行います。

サンプルはseed=1での一場面です。

↑貪欲に評価の高いマスへと足を進めていたところ。botはこの後L(+そのあとにLD)とすすんで取りそびれた大きめの汚れを取りに行きます。

↑ところが、このターンの移動はついさっき汚れをとったばかりのところに行きついてしまい、無駄に一ターン消費してしまっています。

↑そこで、直近3回の移動を逆再生して、その動きを正式な動きとして改変してしまいます。移動の回数の合計を確認してみると、先ほど無駄に消費してしまった1ターンはなかったことになり、別の場所に移動することに成功しています。

↑結果、ここでは1マスの移動の追加だけで汚れの大きな場所の掃除をすることができました。

この後左上へULLと計画します。

↑ここで逆再生。（逆再生の長さは5）

↑今回は結局距離は縮まりませんでしたが、Lと進んでやり直すことができます。あるいは現在地が変わったので上のマスを取りに行くほうが評価が高くなっているかもしれません。

このテクニックは貪欲ベースで47M付近からスコアを改善するには必須のテクニックでした。

現在位置を分身させてしまう

上で述べた反転テクニックを使って大胆に現在位置を分身させてしまうのが有効です。

サンプルはまたしてもseed=1のこの場面です。

↑この場面は先ほどの反転テクニックを使って、移動回数を増やすことなく

↑この場面にできることを確認しました。また、最初の場面でU,Rを選択することで

↑このような場面にも到達できます。

さらに、最初の盤面→Lからの逆再生→Dからの逆再生を用いることで

↑こんな場面にも到達できたりします。(さらにこの場面からRからの逆再生で新しい場面に)

そんなわけで、これらの場面での現在位置の点を覚えておき、これらを距離0の点とします。これにたいして最短経路に対するDPを公式解説同様に行い、移動に都合の良い場面を持ってくることで改善が期待できます。

この分身戦法が使える場面は特定のケースでのみということはなく、取りこぼしを回収する際・別の汚れた区域へ移動する際に効果を発揮します。

例として、seed=1の別の場面を考えてみます。

↑この場面では、

↑この中から都合の良い視点を選ぶことができるということで、左・中央・右下の取りこぼしや左上の新しい区域への移動などいずれの方針に対しても大きなアドバンテージを得ることができます。

お掃除高橋君2号は現在位置を錯覚しているのでデバッグ出力をしてVisualizerを確認すると1マス進む貪欲での道の変わり方が面白いです。(以下はseed=1でのまた別の例)

　意外にもDFSでのこれらの列挙はそれほど時間がかからず（ほぼ全列挙していますが、そもそも厳密に全列挙する必要はない）、手元の実験では最短経路についてのDP のほうが時間がかかるようでした。

これら(+諸々)を実装するとかなり貪欲らしからぬ振る舞いをしてくれるようになります。貪欲を頑張ってみたら最終的に行き着くのは貪欲らしからぬ動きという、現実を突きつけられる結果になりました・・・。

seed=5 (注:実際の行動は長さが70000くらいあるので一部分のみを抜粋しています)

改善の余地

　容易に想像できることですが、この貪欲のポテンシャルはそれほど高くないです。特に区域を訪れる頻度の認識が最短路に限定したDPでは甘く、この頻度については反転では対応できません。

　また、反転によって本来訪れる予定だったターンから多少前後していることで若干コストが増えてしまいます。かといって、スコア計算の処理を導入すると出力できる行動の長さが短くなってしまいループのつなぎ目での無駄が無視できなくなってしまいます。（私の解法では各マスの評価の値に(現在の汚れ)/(訪問回数)を入れていることもあって長さが長いほうが強いです。）

　評価値を謎の(軽い定数時間程度で計算できる)見積もり項で修正するorDP部分自体を工夫するなどして上の問題が解消できるなら、まだまだ改善が可能だと思います(いろいろ突き詰めて多分~2%くらいで、それ以上を目指すならさすがにビームを打つか、さっさと経路を完成させて後からいろいろ変形させないと厳しそう)

　そんなわけで、この貪欲はある程度頭打ちになっており、wataさんの順位表を確認してみると安定して最上位陣に敗北しています。（これらの統計データを公開してくださっている方々、いつもありがとうございます）

おわりに

　ここまで読んでくださった方、ありがとうございました。今回は高速に焼くのが難しそうで貪欲ベースで頑張ってみましたが、なかなか戦えたのではないかと思っています。一方で最終的に高速な焼きなましにもっていく人たちには歯が立たず、実力不足を感じています。ビームサーチもそろそろまともに向き合っていかないと・・・。

　今回のコンテストのテーマは一度過去に作ってみたいと思っていたいたので、コンテストという形できれいなビジュアライザとともに楽しめたのが嬉しかったです。コンテストの開催に関わってくださっていた方々、他参加されていた方々、楽しい時間をありがとうございました！