はじめに
こんにちは、ALGO ARTIS でアルゴリズムエンジニアとして働いているscat_nekoです。
ALGO ARTIS では日々の学習の一環として、AtCoder で開催された各コンテストについての勉強会を開催しています。
この記事では、先日開催されたAtCoder Heuristic Contest 052 勉強会の様子を公開します！[1]
勉強会の進め方・ルール
以下のような価値観で開催しています。
- 参加して下位だった人（解けなかった人）が主役、質問をしまくる
- 上位だった人（解けた人）は考え方含めて親切に答える
- 解いてなくても参加してオッケー
- 楽しくやりましょう！
Heuristic コンテストの勉強会の場合、あらかじめ共有 Notion ページに解法の概要を記入しておき、順位の低い人から順に発表・解説していく、というような形式を取っています。[2]
問題概要
-
30×30 - ロボットを操作するためのコントローラは 1 台しかなく、そのコントローラには 10 個のボタンがついている。
- 各ボタンに対して「1 番目のロボットは右に動く」「2 番目のロボットは上に動く」...「10 番目のロボットは待機(動かない)」のように、ボタンを押した時の 10 台のロボットの動きを事前に設定する。
- ボタンの設定と押す順番を工夫して、できるだけ少ない操作回数で全マスをワックスがけしよう。
参加メンバーの解法
今回の勉強会には、エンジニア 14 人が参加しました。
読みやすさのために実際の進行から順番を多少変更しつつ、ピックアップして紹介していきます。
評価値を使った貪欲法！
ロボットが塗ったマスの数などを評価値として、最も評価値が高くなる操作を繰り返す貪欲法を採用したメンバーが多くいました。
まずはそのような方針を採ったメンバーの解法を紹介します。
momohara
- コントローラーは、初めは4つのボタンに上下左右を10台のロボット全てに割り当てました。
- 複数台のロボットの位置が被らないよう一部のロボットの上下左右を反転させました。
- まだ塗られていないマスと、いずれかのロボットの距離が最小となるようなボタンを押す貪欲法を試しました。
- 同じ距離になる操作が複数ある場合は、ランダムに選択し、2秒間繰り返して最もスコアの良かった操作を提出しました。
scat_neko
- 評価値貪欲を乱択しました。
- ボタンの配置: 各ロボットに対して U U U D D D R R L L をランダムにシャッフルして各ボタンに設定しました。
- 現在の状態から、 10 種類のボタンそれぞれ押して移動した後の状態における評価関数を計算して、最も評価関数の高いボタンを押すようにしました。
- 評価関数は、塗られていないマスから最寄りのロボットまでの距離の逆数の合計 + 塗られたマスの数
を用いました。 ×2 - この処理を 2 秒間繰り返し、最もスコアの良かった操作を提出しました。
itigo
- ほとんど同じような方法でした。
- ボタンの配置も同じで、 U U U D D D R R L L をランダムにシャッフルして各ボタンに設定しました。
- 評価関数は、新しくワックスがけできるマスの数だけ特大加点、全てワックスがけしてないマスについて、一番近いロボットの距離だけ小減点、を用いました。
- コマンドを生成するとき、 5 個分のコマンドを作ってから残り 5 つは逆操作のコマンドにしました。
- また、最後の 1 マスだけ残ってる際に、そのマスを過去改変で行っていたことにしましたが、あまり効果はありませんでした。
貪欲法はシンプルでも強力な手法であり、勉強会メンバーの多くが採用し、青上位〜黄色のパフォーマンスを獲得していました。
評価関数の工夫や逆操作の導入、過去改変を使った改善などによってスコアを伸ばす方法が議論され、興味深かったです。
しかしながら、この方法では「塗りもらし」が発生しがちで、後で塗りにいかないといけないマスが出てきてしまう、という課題がありトップレベルのスコアは出せませんでした。
貪欲法からの改善！ビームサーチ
評価値貪欲を構築した後に自然に思い浮かぶ改善方法はビームサーチです。
勉強会に参加したメンバーの中にも、ビームサーチを使ってスコアを伸ばした人がいました。
g4np0n
- 評価値貪欲をビームサーチに拡張しました。
- ボタンの配置は、 UDLR を 2 個もしくは 3 個ずつ、ランダムに割り振りました。
- どのボタンを押すかを選ぶかをビームサーチで決定しました。
- 評価値は塗ったマスの数と各マスから各ロボットへの距離の総和です。
- ビームサーチの幅は 50 でした。
aaaaaaaaaa2230
- 評価値ベースのビームサーチを使いました。
- ボタンの配置は、始点を座標でソートして、 [UDLR,DLRU,LRUD … ] とコマンドをローテーションしたものを割り振った 4 つのボタンと、全てのロボットが同じ方向に進む 4 つのボタンを設定しました。
- 評価値は、塗ることのできるマスの数を基本としつつ、隅に近いマスは重みをつけて評価しました。
- 新規の未訪問が出来ない場合は、無限ループの回避に多始点bfs での最短経路方向への移動を行いました。
ビームサーチを使うことで、貪欲法と比べてスコアが伸びています！
しかしながら、貪欲法と同じくビジュアライザを見るとやはり塗りもらしが発生し終盤で回収しにいかなければならず、もう少し改善の余地がありそうです。
効率的に塗ろう！ジグザグ作戦・渦巻き作戦
評価値貪欲やビームサーチでは縦横無尽に動き回るため、塗りもらしが発生して後で塗りに行く必要がありました。
長方形の部屋を雑巾掛けする際には、ヘビのようにジグザグに動くと効率的に掃除ができることを思い出し、ジグザグや渦巻きで塗る戦略を採用したメンバーもいました。
yochan
- ジグザグに塗りました。
- 操作は連打する → 一回だけ押す → 連打する、を繰り返す形にして、生スコア(操作回数)が少なくなる操作列を焼きなましで探索しました。
- 一番最初にはロボットを隅に寄せるための操作を入れました。
MathGorilla
- 渦巻き状に塗りました。
- 渦巻きは U R DD LL UUU RRR DDDD LLLL のように動かすことで実現しました。
- 縦方向の操作だけを同じ数だけ増やすと、渦巻きの形が縦長になるので、バラエティを出せました。
- 渦巻きの種類(向きや回転方向)、形状などを焼きなましで最適化しました。
terry_u16
- ジグザグに塗りました。
- 1 サイクルの中で1往復する長いヘビと、 2 往復する短いヘビを用意して、より効率的に塗る工夫を入れました。
- ジグザグだけだと初期位置がいまいちで、すぐ壁に当たったり重複して塗ったりする場合があったので、適当に初期移動を入れました。
- 塗り残しがあった場合は、適当なロボットに巡回させました。
- ジグザグの向きやロボットの初期位置は焼きなましで最適化しました。
ジグザグに塗るのは強い戦略でしたが、 4 時間というコンテストの時間内で実装し切ることは難しく、塗り残しができてしまうなど詰めきれなかったメンバーも少なくなかったようです。
一方、実装し切ったメンバーは高スコアを出しており、ここで紹介した 3 名は 20 位以内に入賞しています！おめでとうございます！
おわりに
ABC などと比較すると問題が複雑なため、ついつい復習が億劫になってしまう AHC ですが、他の人の考察や振り返りを聞くだけでもかなり様々な知見を吸収できると感じています。
ヒューリスティックコンテストが強くなりたいそこのあなた！ぜひ友人や職場の同僚を誘って、勉強会を開催してみませんか？
Discussion