まえがき
AHC054参加しました。
他の参加者の解説を読むと、最初に植木する人が多数。冒険者の移動にあわせて動的に植木している人が少なさそうなので、本記事書きました。
メッセージ
おっさんです。おっさんでもヒューリスティック青色なりました。
若い人はさっさと追い抜いてください（まじめです。自らのスキル向上も大事ですが、この年になると若手育成が重要なのです）
当面の目標は黄色と言いたいですが、あらゆる方面でレベルアップが必要。
問題
こちら。https://atcoder.jp/contests/ahc054/tasks/ahc054_a
方針１：概要
初期配置で花を木で囲う。通りすがりの冒険者に見つからないよう、囲いの入り口から花まではＬ字にする。
多くの方はこの方針を採用。まじめな方は、いい囲いを試している。
方針１：詳細
・植木パターンを事前に検討。紙と鉛筆が活躍。８種類程度を作成する
・冒険者は上下移動を優先するので、おそらく入口は上下ではなく左右にあけるのが良い（※未検証）
・１パターン目を植木する→到達できないマスが生じたら次のパターンへ
・１パターン目（左右反転）を植木する→到達できないマスが生じたら次のパターンへ
方針１：効果
・初期配置の木が少ない場合、有効
・初期配置の木が多い場合、意図と異なったパターンになり、誤誘導を招いてそう
方針１：所感
・正直、どのようなパターンがよいか確信を持てず。そのような場合は、多数のパターンを試して上位を採用すべきでしょう。見解は後付け。
方針２：概要
・１つのターンでは、冒険者に多くのマスを認識させたくない
・２ターン目以降は、そのターンに冒険者が認識するマスを多く遮るよう植木する
・植木は、冒険者の上下左右の各方向で、近くの未認識の場所に行う
・ただし、到達できないマスができないよう配慮する
方針２：詳細
１．冒険者と花の位置関係から、探索する方向の順序を決定する。
例：花が冒険者の左下にある場合、左→下→右→上の順。左と上の優先順位を入れ替えたり、ユークリッド距離を使って順位を入れ替えたが、変化みられず。
２．上記で決めた４方向に対して探索を繰り返す
２．１ 冒険者の隣のマスを出発点に、１つ目の方向に探索を開始
２．２．１ その地点に植木があれば探索終了
２．２．２ その地点が、枠内かつ、かつ未認識、かつ花がない、かつ到達できないマスが生じない場合、植木して探索終了
２．２．３ 探索地点を１つ進める
方針２：効果
・方針１だけの実装に加えると、スコアが５倍に伸びる。ビジュアライザをみるとおもしろいように遠回りしている
・冒険者は、花から遠い方向にジグザグに移動した
・端に到達したり、初期配置の木の影響から、適度に未認識の場所が残る。これは、冒険者を遠回りさせるのに有効
方針２：所感
・冒険者を花から遠ざけているものの、初期配置の木と動的な植木が悪影響すると、遠ざける方向への道をふさいでしまい、早いターンで冒険者がスタート地点に戻ってくることがある、つまり近い方向に誘導している。改善したかったが、妙案でてこず
・冒険者が花の近くにいるとき、花から遠ざかる方向はあえて植木しないよう調整。ただ、花の近くにすぐに戻ってこれるので効果は小さい
方針３：概要（時間不足で不採用）
・場面を植木で半分にわけて２つの部屋を作る。部屋の間を細長い通りでつなぐ。
・冒険者が２つの部屋を往復し、細長い通りでターンを稼ぐことを期待
方針３：効果
・延長戦で確認予定
雑感：
どのような方針がよいか？どこを調整すべきかを人間（私）が考えてたが、これは機械学習に任せるよう変化する。この手法が広まると人間が理由を説明できなくなる。年月が経つと内部を人間が説明できなくなるのは、その分野の発展に逆行しないか？ 人はまず空を飛び、あとから航空力学を作った。機械に空を飛ばさせ、飛ぶ理由を人が考えるのか
メモ：
DAY1 9/19
・問題を読む。おもしろそう。
DAY2 9/20
・冒険者のアルゴリズムを実装するも、目的地までの経路が複数ある場合、上下左右の優先順位を守れていない...
・並行して、冒険者の妨害方法を模索する。見通しがいいとダメ
・冒険者の行動を忠実にシミュレーションするの、結構面倒くさい..
・妨害方針を整理。花囲い：花を木でＬ時に囲う。冒険者の移動方向は優先順位が上下左右の順なので、出口は左向きが理想だろう
DAY3 9/21
・家族とおでかけ。ほとんど時間とれず
・冒険者の行動を忠実に再現しないと、ゴールしたことがわからない。結構つらい
・って、ここで-1の出力で打ち切れる改善が。なんだか苦労を否定されたような？
・目的地が非公開情報であることに納得。ふらふらする冒険者を、さらにふらふらさせればいいのね。ようやく問題の面白さを得心
下記方針がありそう
・多くの地点を確認させない。未確認の方向に木を置く。分断に注意
・木の置きすぎに注意（動ける場所が減る≒ランダムに選んだ場所に花がある確率が増える）
現在順位：520位、ゲーム得点：6,174、コンテスト得点：1,575,665,605
DAY4 9/22
・保育園つながりの飲み会
・方針１を実装する。WA２件、TLE１件
⇒WA：冒険者のシミュレーションのバグ、N^2-1をターン数の上限としていた
⇒TLE：コンテストでも冒険者のシミュレーションを無駄に行っていた
まだWAが残る
DAY5 9/23
・WA２件のバグを１件取り除く。誤認：「未確認マスの中から一様ランダムに1つ選び」⇒仕様「現在位置から空きマスのみを通って到達可能な未確認マスの中から一様ランダムに1つ選び」
・花を木で囲う。囲うパターンを増やす。
現在順位：471位、ゲーム得点：35,846、コンテスト得点：7,085,443,943
・冒険者が花の場所を選んだ時、極端にスコアが低い。回避困難？
・次は何に取り組むべきか。方針２（視界遮り）or方針３（強制遠回り）
・方針２視界遮りをやってみる。かなり効果あり。面白いように遠回りしている
・現在順位：111位、ゲーム得点：211,074、コンテスト得点： 36,246,190,447
・トップクラスはさらに２倍。どうしよう。このへんで打ち切らない？
下記課題がありそう
・花への入り口を、もっと長くする（四隅に持ってくる）のがいいかな。最初の目的地＝花以外のケース以外でしっかり悪くさせる
・方針３を試す...視界遮りがこれを実現している気はするが
・花から離れる場合、後ろ方向は積極的に木を配置しないほうが良いか
・花が開始位置近くにあると、５手で終了している。コーナーケースとして対応
・初手は、花囲い＋視界遮りを両方する？⇒悪化した。一本道になるから？
・スコア÷N^2を求めて、高いもの／低いものを分析し、ヒントを見つける
DAY6 9/24
・家族がインフルか？
DAY7 9/25
・家族がインフルだ
DAY8 9/26
・家族がインフルか？（２人目）
・視界遮りの順番を変更してみる。まちまち
・花囲いに、植木禁止場所を追加したほうがよさそう。視界遮りが、わざわざ花囲いの入口の上下に植木してる。効果なし
DAY9 9/27
・いろいろ試すも効果なし。触りすぎてコードが不安定。ロールバック
・仕切りなおし
DAY10 9/28
・冒険者が花の近くにいるとき、下手に植木すると花への一本道を作ってしまうが、対策が浮かばない
・方針２において、植木しない条件を追加。冒険者～花の距離は変わらないが、他の地点への距離が大幅に悪化する。つまり、花へ誘導している場合。改善するケース／悪化するケースあり。閾値の調整が必要か？
・現在順位：206位、ゲーム得点：220,066、コンテスト得点： 32,797,535,321
・方針１の左右反転を追加。微増
・現在順位：206位、ゲーム得点：223,482、コンテスト得点： 32,845,860,052
DAY11 9/29
・最終日。相対スコアが下がる。上位陣が伸びている模様。
・花が左上の場合、明確に妨害するよう植木する（tx+1,0)-(tx+1,ty+1)。２～３のマップで試すも、爆下がり。
・暫定順位252位
・最終順位237位
2025/10/1:誤字修正