Skip to content

AtCoder Heuristic Contest 067

問題概要

  • https://atcoder.jp/contests/ahc067
  • N*N マスの魔王城がある
    • マスは、空きマスか障害物マスからなる
    • 範囲外はすべて障害物とする
  • 勇者が(0,0)マスから侵入してくるので、城内に「扉」と「スイッチ」を設置することでできるだけ(N-1,N-1)にある玉座までの移動回数が多くなるようにしたい
    • 扉
      • マスの間に1枚設置できる
      • 2K個の型がある
      • 合計で最大M枚設置できる
      • 同じ種類を何個でも設置できる
    • スイッチ
      • マスに設置できる
      • K個の種類がある
      • 同じ種類を何個でも設置できる
    • 扉2kと扉2k+1がスイッチkによって制御される
      • 初期状態で2kが空いていて、2k+1が閉じている
      • スイッチを押すと開閉状態が入れ替わる
    • 勇者は、最小回数で玉座にたどり着くルートで行動する
      • 最小回数Tは、O(2^k N^2)で計算でき、そのコードは実装例が与えられる
    • スコアは、round(10^6 * log_2 T/N)で計算される
      • もし玉座に到達できない場合は、スコアは1点になる

時間

  • 4 時間

個人的メモ

アプローチ

  • できるだけ勇者を遠回りさせたいが、単純に扉を設置して遠回りさせるだけでは大して増やすことはできない
  • そこで、スイッチを活用して、「スイッチを押さないと次に進めない」ようにすることを考える

スイッチをO(N)回押させる

  • いろいろ考えられるが、「スイッチの周りを扉で囲んで、スイッチiの周りの扉はスイッチi-1を押さないと開けない」ようにする
  • すると、スイッチを順番に全部押させて、最後に玉座が開くようにできる
  • スイッチをできるだけ離れて配置することで操作回数は稼げるが、上位には遠く及ばない

スイッチをO(N^2)回押させる

  • 「スイッチiの前に扉をi枚設置して、スイッチ0からi-1までを押し直させる」
    • スイッチiの前に扉をi枚設置して、その扉をスイッチ0からi-1までの押し直しで開くようにすることで、一応、スイッチを押す回数をO(N^2)にはできる
    • 扉の設置枚数は最低45枚なので、50枚制限以下には収まるが、盤面によっては1枚で塞げない可能性もあるので調整は必要
  • 「スイッチiの前に扉を2枚設置して、スイッチ0からi-1までを押し直させる」
    • (解説放送)
    • 上記よりもっと効率的にすることができるよう
    • スイッチiの前に、「スイッチi-1で開閉する扉」と「スイッチi-2で開閉する扉」の2枚をうまく設置することでもO(N^2)を実現できる
    • スイッチiを押したい場合、たとえば「スイッチi-1がON、かつ、スイッチi-2がOFF」で開くように扉を設置すると、スイッチi-1をONにするためにスイッチi-2もONになってしまっているのでそれをOFFにさせるために繰り返すことを強制できる
    • これだと扉の必要枚数がかなり少なくなるので、残りの扉は壁などに利用することができる
  • これらの方法だと2000〜3000ターンぐらいまでは伸ばせるが、コンテスト中だと上位は数万ターンぐらいになっていたので、全然届かない

スイッチをO(2^N)回押させる

     switch k-1    switch k
        |             |
      door g        door h
        |             |
...-----+-- door g' --+-- door h' -----...(玉座)
  • 簡単のために、上記のような、一本道に横道が出ているようなケース(本線・脇道構成)を考える
    • 横道の奥にスイッチを置き、それぞれの通路の途中に扉を設置する
    • スイッチ側と一本道側で開閉状態が入れ替わるように対応する相補扉(gとg'、hとh')を設置すると、どちらかだけしか通れないようにできる(分岐器、ポイント)
  • 扉h,h'が一つ前のスイッチk-1で開閉状態を入れ替えられるようにした場合、もし扉hが閉じていて、開けたい場合はスイッチk-1を押す必要があるが、扉hを開けた時点ではそれまでのスイッチ側の扉が閉じている状態なはずなので、スイッチkを押せても、扉h'を開けるためには(閉じている)スイッチk-1まで再度開け直す必要がある
  • 玉座も最後のスイッチと考えて、すべてのスイッチが閉じた状態を初期状態とすると、扉の枚数を抑えつつ、スイッチを押す回数をO(2^K)回にできる
  • グレイコード
    • スイッチの状態をbit列として考えると、途中の状態はグレイコードになっている
  • 盤面への埋め込み
    • この一本道をどう埋め込むか?が問題になるが、結構難しい
    • 玉座を根としたランダムDFS木などで木構造を作って、壁(下記参照)などを設置するのが扱いやすかった模様
      • とはいえ結構実装が大変
  • スイッチ0を離して置く
    • スイッチ0をできるだけスイッチ1以降から遠い位置に配置すると、操作回数を伸ばすことができる
  • スイッチを9個使うか10個使うか
    • スイッチ1個を使わないと常に開かない扉(壁)を作れるので、思い切ってスイッチ9個しか使わないようにする、でも結構戦えてたみたい
    • 実際、スイッチ10個でも最後の方で壁にしていた扉が消えてショートカットされてしまう
    • うまく壁を作ることでショートカット阻止できる場合、ざっくりターンが倍にできるので結構上位では重要なポイントだったのかも？

貪欲、局所改善系

  • 今回は、上記のO(2^N)回の解法が強く、単純に扉やスイッチの位置を状態にした貪欲や局所改善では全然ダメだった模様

壁を作る

  • スイッチがあまり押されない扉は壁として利用できる
    • O(2^N)回の解法とかでは、スイッチ9は最後にしか押されないので、扉19とかはずっと閉じたままになるので壁として利用できる
    • ただし、スイッチ9を押してしまうと壁がすべて消えてしまうため、勇者にショートカットされてしまう恐れがある
    • とはいえ、完全に壁にできなくても、スイッチ0を押したら壁が出現するようにするとかでも距離は伸びるので有効
  • 相補扉(扉2kと扉2k+1)を設置すると常に通れないマスを作れる
    • 例えば、左右が障害物の橋マスで上下に相補扉を設置すると、どっちの状態でも通れないようにできる
  • ある領域でスイッチの状態が確定する場合は、そのスイッチの扉を使うことで壁にできる
    • (解説放送)
    • 上記のO(2^N)回の解法の例とかで、扉g'が開いている場合はそれより右側の領域では常に扉gは閉じていることが確定するので、壁として利用できる

領域を分割する

  • https://x.com/montplusa/status/2069072432321986677
  • 領域ごとに領域間を移動できるようにするスイッチを用意して、「領域Aから領域Bに行くための扉を領域Aのどこかにあるスイッチで切り替えると、その扉は開くが領域Bから領域Cに行く扉は閉じる」ようにしておくと、領域B内のどこかにあるスイッチを押して扉を開き直させるよう強制できる
  • スイッチををできるだけ遠回りさせるように配置しておくと、移動回数を伸ばすことができる

その他

AIの影響

挨拶テク(リセットタイミング調整)

  • claude codeやcodexなど、5時間rate limitがあるとき、4時間コンテストの3時間前にcodexを利用しておくことで、コンテストが半分過ぎた時点でリセットされるよう調整するテク
    • コンテストの前半の試行錯誤でトークン消費すると、後半でトークンが足りなくなる恐れがある
  • 一般的にも、朝に挨拶しておくとお昼ごろにリセットタイミングを持ってこれて都合がいい的な？
  • 開始の判定が簡単な挨拶でされるか微妙かもなので、ちゃんとリセットのタイミングが期待通りになったか確認したほうがよさそう
  • https://x.com/chokudai/status/2065252573926527481

関連したパズル、ゲーム

解説

(50位まで&発言を見つけられた方のみ)