Skip to content

ALGO ARTISプログラミングコンテスト2025夏(AHC054)

問題概要

  • N*N (N=20〜40)マスの森があり、範囲外は木で囲まれている
    • いくつかのマスには最初に木が存在している
  • 森の入口から冒険者がやってきて、森の中に存在する花を見つけるまで行動する
  • 冒険者の行動は、「現在位置」と「確認済みマス」を状態にして、未確認マスから1つ目的マスを選び、未確認マスは木がないものとして最短距離で移動する
    • 1ターンで1マス移動する
    • 各ターンの移動後、現在位置から上下左右に木のマスまでが確認済みマスとなる
    • 最短距離が同じ場合は、上下左右の優先順で移動先マスが選ばれる
    • 移動中に花が確認できたら目的マスを花のマスに変更して移動する
  • ここで、各ターンごとに、未確認マスの空きマスに対して、木を設置できる
    • 順番としては、冒険者の位置がわかる→未確認マスに木を配置する→冒険者がマスを確認する、の順で処理される
    • 設置後は動かすことはできない
  • 花が見つかるまでのターン数をできるだけ長くなるように、各ターンでの木の配置を考えよ

時間

  • 240 時間

個人的メモ

迷路生成

  • ターン数をできるだけ長くするためには、できるだけ冒険者が花を見つけられずに行ったり来たりするようにしたい
    • 雰囲気としては、毎ターン、離れたところに目的マスが設定されて、行ったり来たりする(右往左往させる)とターンが伸びそうと考えられる
    • また、できるだけ確認済みマスを増えないようにできると良さそうに思われる
  • 今回は、配置だけでなく、インタラクティブ要素もあり、どのようにこれを実現するかがポイントだった

インタラクティブにガード

  • (解説放送)
  • 気持ちとしては、「できるだけ冒険者の確認済みマスが増えないほうが嬉しい」ので、冒険者の動きに合わせて、できるだけ確認済みマスが増えないように木を配置する、ことが考えられる
    • この場合、木を配置してしまうことで、訪問できないようになるマスができないようにする、ように注意
  • 動き的に斜め移動のようになりやすく、かなり効率よい配置が生成される模様
    • 斜め方向への移動は手数がかかるので、冒険者のターン数を使わせるのに有効

乱択生成

  • 迷路を生成してシミュレーションで評価して良いものを選ぶ、ようにする
  • 乱択DFS木(穴掘り法) (解説放送)
    • 迷路生成アルゴリズムとして、閉路ができないようランダムにDFSをすると木構造を作ることができる
    • 今回の場合、直線的に並ぶと、確認済みマスが一気に増えてしまう問題もあるため、できるだけ同じ方向に伸ばさないなどの工夫も

局所改善

  • シミュレーションが重いので、代理評価関数を用意して、それを最適化
    • 迷路生成後にシミュレーションして良いものを選ぶ、のも有効っぽい
  • メインのパス(一本道)からサブのパス(L字っぽい感じ)がいくつも伸びていると考えると、メインのパスを行ったり来たりする問題と考えられる
  • この場合、パス上の位置がわかると、期待値がパスの長さの線形時間で求められるので、これを最適化する、など
    • ただ、パスは入口と花を終端にしてしまうと、その終端付近でサブのパスをたくさん生やしたいが、スペースが足りないので、入口を終端にはしないほうがよさそう
    • 実際、探索とかしても、サブのパスはあんまり終端側によらず、メインのパスの全体に散らばるような感じになるみたい

左右分割

  • 真ん中付近で左右に分けるように木を設置して、左右を行ったり来たりするようにする
  • このとき、外周に沿うようにパスを作ると、より長い経路を通って左右を行き来させることができる模様 (解説放送)
  • それぞれの領域内をどうするかは、基本的には木構造な感じで、ルールや探索などで生成
  • その他
    • 左右を先に用意して、その間はできるだけ長くなるようにパスを見つける
    • 斜め方向で分割して、左下と右上で領域を作る
    • など

花の防御

  • いろいろ試していると、「花が移動途中で見つかってしまって、ターン数が少なくなる」(事故る)ケースがあることがわかる
    • これが起きると、うまくいくときは数千ターンとかなのに、これが起きると数十ターンとかになってしまうなどがあり得る
  • 花をできるだけ冒険者から見えなくなるようにする必要があった
    • 花が目的マスになってしまった場合はどうしようもない

インタラクティブに防御

  • 花の周囲4マスのうち、3マスは木で塞ぐことができる
  • 各ターンで、冒険者の現在位置から花が見える場合に、それを防ぐように花の周囲を木で3回まで行うことができる
  • また、以下のような配置で、左右どちらかから近づいたら塞ぐ、ようなパターンも (解説放送)
...TT
.TT..
T.f.T
..TT.
TT...

配置パターンで防御

  • 花(f)の周りを以下のように配置すると、花が見えるマスは、花の一つ下のマスだけなので、見つかりにくくできる
.T.
TfT
T..
.T.
  • しかし、以下のように、左上付近が未確認状態のときに、冒険者が右下、目的マスが左上になると、花のところを通過して行こうとしてしまい、事故る可能性がある
.?.
?fT
T..
.T.
  • 冒険者が右下に来る時点で、左上付近が先にすでに埋まっているのがわかっている状態になるよう、以下のように配置すると、より事故りにくくできる
    • 「の」の字のように1周させる
..TTT..
.T...T.
T..T..T
T.TfT.T
T.T...T
T..TTT.
.T.....

シミュレーションで確認

  • シミュレーションを走らせてスコアを見ている場合は、事故るとスコアがかなり下がるので、事故りやすいパターンは採用されにくくなる

シミュレーション

  • テスターにコードがあるので、移植すれば、動かすことはできる

ランダム性への対処

  • 目的マスの選び方にランダム性があり、かなりブレる可能性がある
  • 上位の方では、目的マスの順を固定で複数個用意しておきそれらの平均を使うとか、多腕バンディット、などで選択してたみたい

高速化

  • テスターのコードある程度高速なので、そのままでも十分そう
  • 毎ターン、BFSで最短距離を計算し直すと遅い
    • ターン数も数千〜数万とか行きうる
  • BFSの結果が変わるのは確認済みマスが変化した場合だけなので、そのときだけ更新するようにすると高速化できる(テスターの方針)
  • さらに、最短経路を求めてその経路上に木があった場合だけ経路が変わりうるので、その時だけ更新するようにするとより高速化される(解説放送)

解法間の比較、評価

その他

打ち切り出力

  • 期間中、途中で仕様が更新されて、「-1」を出力すると、それ以降は0を出力したものとして処理される(しかもそのテスト時間が実行時間に含まれない)、打ち切り出力が追加された
  • ターン数が増えると、「0」だけの出力がかなり増えて、テスターの(というより入出力)の時間がかかってしまう恐れがあった
  • インタラクティブじゃない解法(最初に出力してあとは全部0にする解法)の場合は、これをやっておくべきだった

長い経路を作る類題

ルールベース、埋め込みを考える場合

  • ルールベースやパターンの埋め込みなどの方針で考えるときに、最初からある木の配置によってはうまくいかない可能性がある
  • 基本的には、木がない場合で考えて、うまくいくケースで割合やスコアを確認し、うまく行っていないケースへの対処(探索や調整、別処理、など)を考える

解説