ALGO ARTIS
📝

AHC050勉強会レポート

がんぽん
に公開
AtCoder
heuristic
idea

はじめに

こんにちは、ALGO ARTIS でアルゴリズムエンジニアとして働いている岩本(@G4NP0N)です。

ALGO ARTIS では日々の学習の一環として、AtCoder で開催された各コンテストについての勉強会を開催しています。
この記事では、先日開催されたAtCoder Heuristic Contest 050 勉強会の様子を公開します！[1]

勉強会の進め方・ルール

以下のような価値観で開催しています。

  • 参加して下位だった人（解けなかった人）が主役、質問をしまくる
  • 上位だった人（解けた人）は考え方含めて親切に答える
  • 解いてなくても参加してオッケー
  • 楽しくやりましょう！

Heuristic コンテストの勉強会の場合、あらかじめ共有 Notion ページに解法の概要を記入しておき、順位の低い人から順に発表・解説していく、というような形式を取っています。[2]

問題概要

https://atcoder.jp/contests/ahc050/tasks/ahc050_a

  • 40×40 のグリッドがあり、開始時点ではMマスに岩が置かれている。
  • 壁か岩にぶつかるまで上下左右いずれかの方向へランダムに動くロボットがある。初期位置はランダムな空きマス。
  • なるべくロボットが潰されないように気をつけながら空きマスに岩を置いていってね。

参加メンバーの解法

今回の勉強会には、アルゴリズムエンジニア 13 人が参加しました。
読みやすさのために実際の進行から順番を多少変更しつつ、ピックアップして紹介していきます。

T字を作ってロボットを閉じ込めたい！

Kiri8128

乱択貪欲を試していたのですが、ラスト45分くらいでビームサーチを思いついて試してみるとスコアが良くなりました。ビームサーチの評価値は「これまでのスコアと、存在確率が変わらないと仮定して残りのマスを存在確率の小さい順に取っていった場合のスコアの和」で、幅は9です。
最初はT字型の構造を作って流し込みたいと考えていましたが、諦めました。

#####
#...#
##.##


T字構造。下方向から侵入したロボットは、その後下方向に脱出するのが困難になる。

eijirou

自分がやりたかったことも似ています。T字の場所を決めておき、そこにロボットを誘導できるように岩を配置していくことで、ほぼ全てのロボットを集中させるようなことを考えていましたが、具体的な手段がわかりませんでした。

他の参加者からも同様に、T 字は思いついたが実現できなかったというリアクションが寄せられました。

  • T 字を作る際にロボットを潰してしまうと本末転倒なので難しい
  • アドホックなルールベースを短期コンで書くのは間に合わなそうだった

ロボットを閉じ込めていく解法は難しいのでしょうか？
いえ、きちんとこの方針で上位を取っているメンバーがいました！

MathGorilla

T字とは少し違うのですが、通路に閉じ込める解法で27位でした！
以下の順で通路を構築していきます。

  1. 通路をランダムな個数作成する。連続する未ブロックセルを見つけ、両末端マスの周囲3マスの存在確率がほぼ0ならばその行を閉じ込め候補として扱う。複数の候補がある時は長さが大きい場所を優先。
    閉じ込めたい行に隣接するマスの上下いずれかにランダムにブロックを配置し、通路へ誘導できるようにする。 
.#?? … ??#.
#... … ...#
.#?? … ??#.


通路に隣接するマス（？マス）の片方にブロックを配置することで、通路へ誘導できる。

  1. 通路に1手で到達できるマスに隣接したマスを、存在確率の小さい順に埋めていく。
....#..  
...#.?.
..?..?.
.##..#.
#(通路)#
.#.###.
.?.?...
..#....


?マスに岩を配置することで、ロボットを通路へより誘導しやすくなる。

  1. 通路以外の存在確率の低いマスを埋める。
  2. 通路をロボットを潰さないように半分埋める。
  3. 残ったマスを存在確率が低い順に貪欲で埋める。

    一部の通路にロボットが集中する様子を確認できる。
    上記を列の数や列の長さの評価、マスを調べる順番などを変化させながら200回ほど試して最もスコアが高いものを出力しました。

獲得した点数は 148,815,846 点と、満点の 99%を超える高スコア！実装に割ける時間の少ない短期コンテストでこの解法をしっかり完成させていることにメンバーからは賞賛の声が上がりますが、実はこれでも1時間ほど余ってしまったとのこと。さすがはレッドコーダーです。

実は奥深い！？十人十色な貪欲法

terry_u16

マスにロボットが存在する確率をp,隣接4マスにロボットが存在する確率をqとしたとき、Cp-qが最小となるマスに岩を置く貪欲法をしました。
重みCを変えながら何度も実行して、一番良いものを採用しています。
市松模様とかうまく使えないかなと思って色々試してみたんですが、ロボットが行き来できなくなってしまうので良くなさそうでした。

G4NP0N

市松模様わかります！というか、ロボットは岩・壁に隣接しないマスには存在できないので、存在確率だけで評価する貪欲法をとりあえず書いてみると勝手に市松模様になってしまいました。

市松模様。ロボットがバラバラに存在するので、スコアが伸び悩んでしまう。
ロボットの配置が偏った方が良さそうだと思ったので、存在確率が同じくらい小さいマス同士は、隣接4マスの存在確率の分散が大きいものを優先するようにしました。

tempura0224

同じく貪欲です。存在確率が最小のマスのうち、四方の壁への距離の和が最小のものを選びました。なるべく長い道を残してあげたい気持ちですね。

ロボットの存在確率を基本としつつ、タイブレーク時の評価をどのように設計するかという部分が肝心のようです。

  • 盤面の状態を維持しやすいように、通過確率が小さいマスを優先
  • 岩の場所がなるべくまとまるように、隣接する岩の数が多いマスを優先
  • その場所に岩を置いた数ターン後の状態を計算して、分散が大きくなるマスを優先

など、他のメンバーも様々な工夫を凝らしていました。
そんな中、見事勉強会メンバーの中で 1 位に輝いた itigo さんの解法がこちら！

itigo

乱択貪欲でした。

\ a: ロボットが存在する確率
\ b: ロボットが通過する確率
\ c: 隣接4マスにロボットが存在する確率

として、600a+3b-cが小さいマスを選びました。
評価値設計のお気持ちとしては
\ b:ロボットが閉じ込められている構造を破壊したくない
\ c:ロボットの存在確率が高い箇所を囲む窪みを作りたい
ということを意図しています。

序盤200ターンは上記の評価値の上位100個からランダムに選んでいます。最初は上位2個から選んでいたんですが、100個に変えたら大幅にスコアが良くなりました。
最終的なスコアは序盤にいかにロボットを閉じ込められるかで決まるので、序盤に多様性を持たせるのが大切なようです。


seed=0のビジュアライザ。ロボットが終盤まで生き残っている様子が確認できる。

terry_u16

評価値の重みってどうしてこのバランスなんですか？

itigo

実は自分でもよくわかってなくて(笑)
b:c = 3:1 が大事らしくて、これを崩すとスコアが悪化するんですよね。

tempura0224

3つの岩に隣接しているマスに存在する時、ロボットが次のターンに移動する確率と移動しない確率が1:3なので、そこに起因しているかも。

一同

あ〜。（納得）

匠の技が光る評価値設計により、堂々の 9 位獲得！
itigo さんはこのコンテストでヒューリスティックレートが2815となり、いちご色レッドコーダーに到達！おめでとうございます！

おわりに

ABC などと比較すると問題が複雑なため、ついつい復習が億劫になってしまう AHC ですが、他の人の考察や振り返りを聞くだけでもかなり様々な知見を吸収できると感じています。
ヒューリスティックコンテストが強くなりたいそこのあなた！ぜひ友人や職場の同僚を誘って、勉強会を開催してみませんか？

脚注

  1. この記事は競技プログラミングコミュニティへの知識の還元を主目的としており、AHC問題の利用についてはAtCoder株式会社に相談させていただいております。 ↩︎

  2. これは順位の高い人が偉いというわけではなく、少しずつ解法・考察がステップアップしていく方が理解しやすいためです。 ↩︎

ALGO ARTIS
ALGO ARTIS

Discussion