- はじめに
- 1.問題
- 2.1日目）貪欲解
- 3.2日目）
- 4.再考察
- 5.3日目）dfs探索
- 6.4日目）経路dpとスコア計算
- 7.5,6日目）全探索dp
- 8.7日目）制限時間の活用
- 9.8日目）迂回路処理
- 10.9日目）PythonからNimへ
- 11.最終日
- 12.最終解法解説
- 13.提出コード
- 14.終わりに
はじめに
前回の長期コンと同様に、記事の下書きを書きながらAHCに参加します
とりあえず手を動かすより、考察を重ねていけるようにしたいと思っています
長々と書いてしまったので、最終解法だけ見たい方は飛ばしてください
1.問題
https://atcoder.jp/contests/ahc027/tasks/ahc027_a
N*Nの部屋があり、中には一部壁となっている箇所もある
お掃除ロボを動かして、床面を出来る限り綺麗にするという問題
床面には汚れやすさが決まっており、掃除した直後から時間経過で汚れていく
10^5以下のステップで無限ループ出来るような操作が出力となる
2.1日目）貪欲解
事前にHTTFの過去問は一通り見たので、お掃除高橋くん2号の文字を見てホッコリしていました
問題の理解は比較的簡単でしたが、どう解いたらよいかかなり悩みます
とりあえず、スコアの出る出力を書いてビジュアライザを見ました
下端まで行って一つ右へ、上から1マス下まで上がって一つ右へを繰り返し、最後に右上から左上まで帰るだけの操作をしました
把握できたことを箇条書きで書きます
・汚れやすい領域がある程度固まって数か所ある
・汚れやすい箇所を放置するとどんどん悪化する
・右のグラフでどのターンの盤面が悪いのかわかりやすい！
・10^5という制約はあまり関係ない？(十分足りそう
・出力長さLが決まらないと初期汚れが決まらない
最初に思いついたのは、「現在値から移動した時に、最も汚れている箇所へ行く」という貪欲解なので、まずはこれを頑張って実装してみます
前処理書いているだけで無限に時間がかかります...
まず壁を考えたくないので、無向グラフ化しました
また、毎回経路探索すると無駄な気がしたので、多始点BFSで全地点間の最短距離と経路を配列に用意しておきました
それらしい解が出ることを確認していざ提出！
seed=0~5くらいでしか確認していなかったので他でも確認したところ、出力文字数が10^5を超える時があるようでした
角に汚れにくい床があると、探索しないということに気付いたので一定の移動量(適当にN^2.5)を超えたら、未探索床のうちで一番汚れている箇所へ行くようにしました
N=40でも、11,000回程度でゴールできるはずなので再提出！
1ページ目とはなりませんでしたが、とりあえず正の得点を得ることができました
ビジュアライザを確認します
一番濃い赤を消すように動けていますが、近くにある汚れた床を先に掃除するように動いた方が効率良さそうに見えます
方針を考え直した方が良さそうですが、日を跨いでいるのでまた明日にします
3.2日目）
布団の中で「遠くを行ったり来たりするのが無駄なら、距離が遠いほど選びにくい方が良いのでは」と思ったので、そのように実装しました
具体的には、f:現在の床の汚れ評価値, v:現在値からの最短距離, p:床の汚れやすさ
とした時に、(f + v * p) / (v + 1) を各床について計算して、評価が最大の場所へ向かうようにしました
ビジュアライザを確認します（show_routeに気付きました！
前回と比べると、周辺を綺麗にしてから遠くの汚れへ向かっていることがわかります
ただ、近くを掃除する際のルートが重なっている挙動は無駄に見えます
（掃除してすぐの床を掃除する必要はないため
4.再考察
12/2 18:00頃の時点で13位の位置にいますが、まだ1週間あるので一度落ち着いて考え直してみます
汚れやすさdの生成方法を読みましたが、よく分かりません...
dの分布を改めて見てみると、汚れやすい箇所とそうでない箇所がある程度分かれているように見えます
また、壁を生成した後に汚れやすさが決定されることも説明文から分かります
汚れやすい箇所を繰り返し訪問しつつ、全体を埋めていく動きをさせたい気持ちになります
何も思いつかないまま時間が過ぎて、夜になったのでとりあえずABC331に出ました
大きな方針転換が難しそうなので、次の汚れへ向かう時の処理の判定を工夫してみようと思います
一番評価値の高い箇所へ向かうようにしていますが、上位n個について巡回するようにすれば、近場でいったり来たりしないような気がします（実装できるのか？
5.3日目）dfs探索
前日に考えた、評価値の上位n個を巡回する案はTLEレベルの遅さですが実装できましたが、得点は下がる結果になりました
恐らく評価値の高い箇所へ向かうのが遅くなるからだと思われます
次の案として、(cy, cx)→(ny, nx)へ向かう最短経路のうち最も汚れを回収できるルートを探索することを考えました
dfsを使って実装したところ、こちらは効果ありでした
また、最短経路だけでなく迂回路も許可した実装もして試しました
ただ、迂回距離数を増やすとスコアが下がる結果でした
前述と同じく、価値の高い箇所へ向かうのが遅くなるのが良くないと思われます
パラメータ変更に走り出したので、結構行き詰ってしまいました
スコア計算が出来ていないので、明日以降はその方面も考えてみようと思います
6.4日目）経路dpとスコア計算
前日に行った、(cy, cx)→(ny, nx)へ向かう最短経路のうち最も汚れを回収できるルートの探索について、よく考えたらdpで解けることに気付いたため書き直したところ、5%程度改善しました
迂回路を使う場合でも、bitDPで解けるはずですが未履修のため止めておきます
貪欲解の限界を感じつつあるため、意地でも焼きなましをしたいと思い、いよいよスコア計算を書くことにしました
各床について、その場所に訪れたターン数を記録しておき、その差分の累積和に汚れやすさを掛けて、全体を足し合わせればスコアが出るはずです
ちなみに、0~Nまでの数字を全て足した値は、0.5*N^2+0.5*N で求まります
手元計算とビジュアライザの値が合うことが確認できました！
ただ、貪欲に比べ倍以上悪いスコアしか出ないのと、計算が遅く2秒以内ではとてもループが回らないため今のままではとても焼けそうにありません
現状のビジュアライザを見て、改めて作戦を立ててみます
比較的、汚れの集合に向かって移動できていますが、近場で交差するように何度も動いてしまっています
解決案は浮かびませんが、問題点は見つかったのでまた明日考えてみます
7.5,6日目）全探索dp
全床の中で一番汚れ評価値の高い箇所へ向かう考えでしたが、経路をdpで計算できるなら現在値から全ての床へ行く経路もdpで評価できるのではと考えました
迂回路は考えず、全地点へ最短で行く経路のうちで 経路の評価値合計/通る床の数 の最も高い経路を使うようにしました
グリッド上の最短経路の数え上げdpを履修していたお陰で、そこまで詰まらずに書くことができ、スコアが10%程度改善しました！（提出時21位）
気合の浮上😃 pic.twitter.com/z8qNhLCYi5
— uta (@uta_cccc) 2023年12月5日
再度ビジュアライザで確認した所、近場の赤色を無視して遠くへ向かう場面がありました
そこで、数マス進んだら再度探索をやり直す処理を加えたところスコアが良くなるケースがありました
ただ、計算時間が増えるためNが多いケースは無理な工夫となりました
8.7日目）制限時間の活用
朝起きたら急に閃きました
これまで、全床に到達したタイミングで探索を打ち切って(0, 0)地点へ向かって終了としていましたが、更に時間の限り探索をしたらどうなるのか。ということです
時間を延ばして実行してみると、明らかにスコアが向上しました！
今の解法の延長のスコア向上程度ですが、時間をかけるほどスコアが出ることが分かったため、より多くループを回すためのコード見直しに入りました
いくつか工夫をしましたが、一番効果が出たのは2次元配列を1次元配列に変更したことでした
2次元変数と1次元変数で添え字の変換が発生しないように、扱う全ての変数を1次元配列用に書き換えたことで、探索量が倍程度(おそらく)になりました
不要なコードも減らし、いよいよ貪欲解の限界が見えてきました
9.8日目）迂回路処理
3日目に考えていた、迂回路を使った探索方法を改めて考えてみました
上手くいかなかった点として、評価値最大の地点に向かう途中で迂回するという考えが、評価の仕方と相性が悪かったように思います
今の処理は道のりの汚れ評価値も加味した探索のため、迂回路の探索が上手くいくような気がします
bitDPで解くしかないと思っていましたが、拡張ダイクストラのような感じで解くことにしました
dpの更新は「nマス通った時の汚れ評価値の最大値」とすることで、最も汚れを回収できるルートを探索することが出来そうです
ただ、処理が重いためN<=30の場合に限定しました
頑張りの割には、若干のスコア改善(1%以内)でガッカリしましたが、汚れが溜まっている箇所へより早くいく必要があることを考えると、迂回という方針はやはりイマイチなようです
10.9日目）PythonからNimへ
いよいよ改善案が尽き、処理速度アップも限界になってきました
処理速度を上げればスコアが多少良くなることは分かっているため、言語を変えることを考えてみました
C++かRustで検討して、C++で少し書いてみましたが全然進みません！（泣
そんな中、XでNimの布教をしていた人のことを思い出し、トライしてみることにしました
過去のNim提出コードを参考にしたり、ChatGPTに頼ったりしながら４，５時間格闘した結果、PythonコードをNimに移植することが出来ました！
Pythonに慣れ過ぎて型を意識するのが大変でしたが、エラー文が親切なためデバッグしやすいのは非常に良かったですね
ほぼ同じコードを提出しましたが、処理速度だけでスコアが少し改善しました
ただ、順位はあまり変化なかった(25位)ので、これより上は方針から違いそうです
11.最終日
無理だろうなと思っていた、山登り法を書いてみて予想通り上手くいかなかったため少しのパラメータ調整だけして最終提出としました
12.最終解法解説
大枠の方針は以下になります
・現在地から各床へ行動した時に、汚れ評価値平均の最大経路を探索する
・探索した先へ一気に行かず、数ステップで止めて再度全体探索を行う
・スタート地点に到達する毎に出力列へ追記していく
また、Nの大きさによって探索方法を少し変えています
(N<=25) 迂回5マスまで探索し、評価値平均が最大の経路で移動
(N<=30) 迂回2マスまで探索、評価値平均が最大の経路で移動
(N<=35) 最短経路のみ探索し、3マス進んだら再探索
(N<=40) 最短経路のみ探索し、5マス進んだら再探索
各マスの初期汚れ(floor)は、d*(N^2)/2 として到達する毎に0にしています
探索時に使用する評価値は、(floor+d*(N**0.5))/(check+1) としています
※checkは、各マスの通過回数
13.提出コード
Nim
https://atcoder.jp/contests/ahc027/submissions/48356451
pypy3(Nim提出とほぼ同等)
https://atcoder.jp/contests/ahc027/submissions/48305607
14.終わりに
今回のコンテストは、これまでの長期AHCの中でも一番時間をかけたのではないかと思います（リアルが割と暇なタイミングでもあったが、54回提出は多すぎた
個人的にはやれるところまでやった気持ちでいましたが、結果や他の方の解法が出てくると、悔しい気持ちが出てきます
年内入黄を目指して、まだまだ頑張ります
