AHC052参加記

AtCoder Heuristic Contest 052 に参加したので記録しておく。

結果

379,380点で5位だった!! もちろん過去最高順位。ratingが309上がって黄色になった。

問題の概要

マス目状の30x30の盤面があり、10台のロボットと、5つの直線状の壁がランダムに配置されている。
10個のボタンを持つコントローラーがあり、1つのボタンには、それぞれのロボットに対してコマンド(UDLRまたは待機)を割り当てることができる。この割り当ては最初に決める必要がある。
1ターンにコントローラーのどれかのボタンを押すことにより全てのロボットを同時に操作する。ロボットが通ったマスは色が塗られる。(問題文では掃除)
できるだけ短いターン数で全てのマスを塗るプランを作成する。

• 盤面の大きさ(NxN): 30x30
• ロボットの数(M): 10
• ボタンの個数(K): 10
• 全部塗れなかったときのスコア: 塗れたマス目の総数
• 全部塗れたときのスコア: 3xNxN - ターン数

考えたこと

上下左右に完全にランダムに動いて塗りつぶすのは、同じ場所を何回も通る可能性があるため、非効率だと思った。また、止まる必要性も低そう。
まずは初期解として、↓ のような単純な塗りつぶしを基本として考えた。

→→→→→→↓
↓←←←←←←
→→→→→→↓
↓←←←←←←

いくつかテストケースを見てみたところ、少し遠めに移動したり、壁を迂回する必要もありそうだった。
そこで以下のような候補を考えてみた。

• ある方向に塗りつぶし -> 別の方向に塗りつぶし、のように塗る
  • 全体は塗れそうだが、重複が発生しそう
• 大部分のロボットは単純に塗り、一部のロボットは隙間を塗る
  • 効率的になりそうだが、実装が複雑
• 初期移動として、全体的に散らばるような位置まで直線的に動き、そのあと単純に塗りつぶし
  • 最初だけ無駄が生じるが、シンプル

このうち一番実装が簡単な3番目のアプローチから実装していくことにした。(結局それしか実装しなかった)

実装内容

全体の構築

• ボタンの押し方を生成
  • 初期移動の操作を生成 (最大7回)
    • ボタン0をA回使う
    • ボタン1でB回使う
    • ボタン2でC回使う
    • ...
  • 塗りつぶしの操作を生成
    • 以下をX回繰り返す
      • ボタン8をY回使う
      • ボタン7を1回使う
      • ボタン9をY回使う
      • ボタン7を1回使う
• 改善ループ
  • ロボットを1台選び、コマンドをランダムに生成し、全体が塗れているか判定

以上の全体の構築を単純に繰り返し、スコアが一番良いものを答えとした。

初期移動

初期移動では、ランダムの歩数A, B, C, ...で直線的に移動していく。初期移動と塗りつぶしだけで構築するならば、最後の塗りつぶしは3種類の操作でできるので、初期移動には7種類まで使うことができ、複雑な盤面でも迂回しつつ遠くに行くことができる。(途中で気づいた)
それぞれの操作回数A, B, Cや、その方向、初期移動の回数は乱数で生成した。

塗りつぶし

塗りつぶしの方向や回数X, Yは乱数で決めた。ボタン7, 8, 9は90°ずつ異なるので、ボタン9の操作からセットで決めるようにした。

改善ループ

ロボットを1台選び、コマンドをランダムに生成し、シミュレーションする。ロボット毎に30x30のbitsetを用意しておき、それを塗っていく。
全ロボット分のbitsetの論理和をカウントして全部塗れているかどうかを判定する。なお自前のbitsetで少しだけ速くなった。

壁の判定

壁の入力形式はAHC027とほぼ同じ (ただし垂直と水平の順序が違う) なので、入力部と、壁の持ち方を再利用した。
(壁の持ち方はtomerunさんの記事 壁の持ち方 - TopCoderの学習のお時間 と同じ。以前どなたかが共有してくれて実装済だった)

提出と改善

乱数の範囲を大きくするとスコアがあまり良くなかった。最初の100msでは小さい範囲で試し、そこで塗れたら、乱数の範囲を維持したまま改善。塗れなければ乱数の範囲を拡大するようにした。
1000ケースほど実行したところ全部塗れることがわかったので提出してみたら5位だった。とはいえ3時間経過していたので、新しいことはせず、パラメータが2段階だったのを、少しずつ段階的に増やすなどの調整だけした。
最終的にも少しだけ改善して5位で終わった。最終提出は これ (311行)

↓ case=0000 score: 2554
0000は割とシンプル。きれいに塗れている。

↓ case=0118 score: 2493
パラメータを大きくしないと塗れなかったケース。いい感じで壁を飛び越えたりするとうまく塗れる。

終了後

できていなかったところ

• パラメータの最適化
  • 焼きなましもできそう
• 途中の段階で全部塗れている場合に、末尾を削る
  • 終了後、かえでさんのスペースで指摘された。やってみたところ380kには到達したが、順位は変わらず。
• ジグザグ移動
  • 初期移動は自分は完全ランダムにしたが、ジグザグに移動するつもりであれば、共通の操作として効率化できそう。
• 最後に塗り残したところだけ塗る
  • wataさんが実装している内容。さすがだ。(https://x.com/wata_orz/status/1959195382375919643)

たぶん良かった点

• 複雑なことをしなかった
  • バグらずに実装できた
• 最初にいい感じの場所(遠く&バラバラ)に行けている
  • 壁を迂回できた
• 構築と部分更新が速かった
  • パラメータが小さいので全体の再構築しなおしでもそこそこいけた
• 判定方法
  • 塗りきれるかどうかの判定にしたことで、全体をカバーするぎりぎりの操作回数になっていた

短期コンテストは、方針が当たれば上位にいけることがあるので、これからもやっていきたい。