- 0.はじめに
- 1.問題文の概要
- 2.最初の提出
- 4.2日目 埋め込み
- 5.3日目から5日目
- 6.6日目
- 7.7日目 ついにスコアが上がった
- 8.8日目
- 9.9日目
- 10.10日目
- 11.コンテスト最終日
- 12.終わりに
- 13.最終結果（2025年10月2日更新）
0.はじめに
はじめまして、もしくはお久しぶりです。競技プログラミング歴5年半のかえでです。
これは、2025年9月19日金曜日19時から9月29日月曜日19時までの11日間開催された「ALGO ARTIS プログラミングコンテスト2025 夏（AtCoder Heuristic Contest 054）」の参加記になります。
この参加記は、コンテスト期間中に自分のメモ代わりに記録しているところもあるので、わかりづらい箇所や、冗長な箇所があるのではないかと思っています。
今回は特に方針が行ったり来たりしていて、「また同じことが書いてある」ということがあるのではないかと思います。
そういったことも含めて、コンテストに参加している雰囲気をリアルに感じてもらえればうれしく思います。そして、これだったら自分でもできるかもしれないと感じてもらえたら、公開してよかったなあと思います。少しでもAHCに興味を持ってもらうことができ、参加者が増えることを心より願っています。
また、AHCの解説欄には誰でもアップできるので、自分はこんな風に解いたとぜひ載せていただけるとうれしいです。同じくらいの力の人がどんなふうに解いているかを知ることができるのは、とても価値があることです。私自身も解法と呼ぶことのできない参加記を載せているのは、少しでも輪が広がることを願っているからです。
1.問題文の概要
- 冒険者は地図を持たずに森にやってくる
- 伝説の花の位置を冒険者にできるだけ見つかりにくく、そして最終的には必ず見つけられるように、入口からのルートに木の魔物「トレント」を置く
- インタラクティブの最終的に伝説の花にたどり着くまでのターン数をスコアとする
2.最初の提出
予定があったため20時前くらいから問題文を読み始めました。シンプルでわかりやすくてうれしい。
順位表ではRinSakamichiさんが首位にいました！すごい！
考えたこと
- 見通しが悪い方が良い。
- 斜め配置が良い。
- たどり着く前に塞ぐ（別から迂回してもらう）
メモ
- トップ（20:00）の相対スコア：71,324,772,857
- サンプルの相対スコア：6,557,945,468
メモ
- トップ（20:50）の相対スコア：63,164,166,651
- サンプルの相対スコア：2,659,990,991
最初の提出をします。サンプルコードをC++にしたものです。トレントは何も置きません。無事ACしました。
- AAを囲うのは良さそう
こんな感じ。
2回目の提出をします。
seed44ではスコア2534が出ていました。未到達マスが点在し、渦巻き状のルートを行ったり来たりしていました。
苦労せずに良いスコアが出ているように感じます。
順位表のトップを見ます。terry_u16さんが1位になっていました。
メモ
- 最初に迷路を作っておくのはどうかな。
- 全部のトレントを埋め込みたい。
4.2日目 埋め込み
2次元配列でトレントを置きたい箇所を作っておき、それを埋め込んでみました。
1手目に全て置きます。
その後AAの周りだけ、上下左右のうち3か所に、ルートをふさがないように、あらたにトレントを配置します。
seed0は526になりました。
提出をします。
- 初期配置時に残った空きマスへのルートがふさがれていないことを確認します。
seed48では4326が出ました。
提出結果です。
埋め込みを変えてみました。
別の埋め込みも試します。
100テストケースを見た感じ、そこまで良くなさそう。もう少し複雑に置こうかな。
絶対スコア64966になりました。
（上との違いを書くのを忘れました。多分別の埋め込みを試しています）
5.3日目から5日目
スタートダッシュからterryさんがトップを独走中でしたが、2位との差が詰まってきたかもしれません。自分の約5倍の相対スコアです。
埋め方を変えてみますが、一長一短です。
AAの周りを渦巻きにしました。
この模様通りに置けるときだけ置くという判定にしたので、大きすぎて全然置けません。もう少し小さなものにします。
ランダムに何回か目標を決めて移動したとき、AAが見つからないかどうかを確認します。近くを目標にされた場合はしょうがないですが、主要道路から見えるのは良くないです。
ん？主要道路？
あえてこの道を常に最短で通れば良いという道を作っておけば、脇道に逸れないのでは。
- あらゆる場所への道が入り口から遠いけど、それが主要道路で最短である。
という条件でいろいろとパターンを考えます。
左の幹線道路より、真ん中の幹線道路の方が距離が長くなりそう。
真ん中の幹線道路から脇道が出る。
さて、木が無いところでは、割とよさそうでした。とはいえ、木があるところではボロボロ。
- 入り口からAAまでの最長経路を作りたい。
失敗しました。バグっています。
今は初期マップだけ手で作っていますが、そろそろ自分で実装をがんばろうかなと思います。
今考えているのは左の２又に分かれているタイプ
- 盤面を4×4に分けます。
- スタートが3（下図参照）で、AAが半分のうち、一番遠くなるような順序にします。
- 残りの半分も一筆書きで遠くなるようにまわる順番を決めます。
下の図だと、
- 3→2→1→5→6→10→9→13→14(AA)
- 3→4→8→7→11→12→16→15（ダミー）
になります。
こうすることで、右と左を行ったり来たりするルートができるのではないかと考えました。
最短でAAを見つけたとしても60手くらいになる感じ。
目標は
- 全てのテストケースでN*N以上のスコアを出すこと
です。
まずはseed0を手で作ります。
あれ？
すぐに見つかっちゃった。
とはいうものの、自分のseed0のベストスコアは798。うまくいったり、うまくいかなかったりするので、良いスコアを出すのが難しいと感じます。
terryさんのテストケース実行ツール、pahcerを見たら、bestスコアが保存されていたのですが、それを見ると、N*Nで割った長さが平均1.92になっていました。絶対値のスコア予想も今の2倍くらいです。そうか。各テストケースでベストが出せれば、それだけでかなりスコアが良くなりそう。
右回り、左回り両方から遠くしておいて、近くに来た時に北側を封鎖すると少しスコアが良くなりそうです。
- 最初に人１人通れる分だけ残して、トレントを埋められるだけ埋める
目的は見通しを悪くすること。
- 人がAAとの距離を短くしているときに塞ぐ（AAへの別ルートがある場合）
- AAの周りはL字に、できればコの字に取り囲んでおく。
遠回りの道を作るのが難しいので発想を変えます。
- 最短路の道を作る
- 最短路の道をふさいで、トレントを取り除いて別の道を作る（その際、今ある道と合流しないようにする。
- 1、2を繰り返す
最短路をふさいだら、2桁のスコアのテストケースがなくなりました。
あ、違う。これ、DFSで長い道を作ってる。
- 盤面の "." だけでランダムDFS生成の全域木を作り、その木における入口→AAの一意の経路を採用する
- 初手にその経路以外の "." をすべてトレント化する
- 2手目以降は出力 0 とする
という内容で、LLMがこちらの指示以上に良い感じにしてくれました。さらに分岐する横穴を掘ります。貫通しない程度にジグザグの道を追加します。
おー、よくなりました。
悪いものがなくなり、他のテストケースのスコアもだいぶ伸びました。
提出をします。
絶対スコアはベストを更新して87068になりました。相対スコアは、人数が増えているので順位は下がっていますが、相対スコアもパフォーマンスもだいぶ上がりました。
（提出前は223位、15256053943でした）
今は遠回りの１本道なので、ダミールートを追加します。
- Step1: 入口からAAまでの長い経路をDFSで確保する（必ず到達できる）。
- Step2: 「ダミー目的地」はAAとは異なる位置にし、長い経路をDFSで確保する。
- Step3: 本経路とダミー経路は「合流しないように」作る。
- Step4: 本経路とダミー経路の各マスから「横穴」をジグザグに掘る。ただし
- AAの近くは掘らない
- 袋小路になるように、どこかで止める
- Step5: 初期配置では「これら残した通路」以外をトレントで塞ぐ。
少しよくなりました。提出をします。
絶対スコアは97504、相対スコアは20Gを超えました。
順位表のトップです。
相変わらずテリーさんがトップです。RinSakamichiさんが3位にいるのを見ると、貪欲で良い方法がありそうな気持になります。自分との差は3.5倍。
少しでも縮めたいです。
絶対スコアは88884に下がったものの、相対順位は208位から192位に上がりました。
Nが大きいときがイマイチで、Nが小さいときが相対的に良さそうです。
テストケースごとにN*Nで割った値を指標にすると、前回が1.06、今回が1.12なので、テストケースごとに補正して良くなったかを見た方が良さそうです。
-1を入れるとそれ以降を自動的に計算してくれるようになったので、初期位置を作った後、-1を入れることにしました。これにより、ビジュアライザで考察しやすくなりました。
（時間経過）
さて、17000歩、12km歩いて帰ってきました。
考えつきました。最強のルートを。
まずはseed0を自分で書きます。
あれ？スコアが良くない。
- AAだけ遠回りルートで、後はDFSで長いパスを作る
と良いと思ったのだけど。
- 行き止まりを作ってみました。
ちょっと良くなったけど、そうじゃないんだなあ。
やっぱり幹線道路かな。
- 幹線道路から行き止まりをいっぱい作る。
ん－！これだー！
seed0のスコアが604になりました。
上のseed0のビジュアライザを見やすいように補助線を書くとこんな感じ。
赤が幹線道路で、青がAAから幹線道路へつなぐルートです。
というわけで実装開始です。
デバッグをしながら、幹線道路をつくります。
まず、幹線道路を作る際にAAを避けるように修正します。
ちょっとずつ理想の幹線道路ができあがってきました。
できあがったら、AAを幹線道路につなぎます。
最後は、幹線道路から行き止まりのジグザグの道を作れるだけ貪欲に作ります。
ジグザグの道とは、右下右下右下…、右上右上右上…、左下左下左下…、左上左上左上…のどれかです。曲がり角が多い方が見通しが悪くなるので、確認済みマスが増えづらいという利点があります。
とは思ったものの、作ってみると、道の本数があまり取れず、イマイチでした。
右右上右右下右右上といったジグザグを考えます。
いろいろとバグります。
- 道幅が広くなって広場ができあがる。
- もっと道を作れるのに作らないため、トレントが密集した森ができる。
それっぽい盤面になってきたものの、まだ行き止まりを作れるし、スコアも低いままです。
- AAが上にあると特に見つかりやすいようなので、AAへつながる道は下方向に作ることにします。
うまくいかない。
- どこにもつながっていないトレントがあったら、どこかにつなげる貪欲を追加します。
- 今は環状なので、AAから幹線道路のT字路につながったところで、入口から近い方をふさぎます。
かなりよくなりましたが、まだ極端にスコアが悪いものがあります。これまで初期盤面を生成した後は、-1を出していましたが、インタラクティブで、トレントを追加することにします。
うまくいかないので、その前のコードを一回提出しておきます。
貪欲なので138msで終わっています。
提出前はすでに290位ぐらいまで下がっていたので、提出による順位のダウンはほんの少しです。N*Nで割った値は平均0.91で、前回の1.13よりだいぶ悪くなっているのですが。
いっぱいループを作っておいて、ふさぐ？
道の中に抜け道を作っておいて、ふさぐ？
うまくいなくて焦る気持ちが出ます。
コンテスト5日目の夜でした。
解法を合体したけど、どんなときにどちらがよくなるかがわかりません。ハイスコアを更新することはできませんでした。
DFSに戻ろうかなと思います。
今考えていること
- 現在トレントで埋めてしまっている到達できないマスに経路を広げること
実装して提出をすると、久しぶりにベストを更新しました。
考察を続けるものの、スコアがよくなりません。
最初の埋め込みを再び行いたい気持ちに戻ってきました。
ん、こんな形はどうかな。
- 各部屋を連結するように穴をあける
6.6日目
よく考えたけど、これ、無駄かも。
上の埋め込み配列を見ながら思います。
DFSのときもそうでしたが、道を作るのに3列を必要とするのが無駄だなあと思うようになりました。
貪欲に道を作った方が、２列で作ることができます。ちょっとseed0を自分で作ります。
結果はスコア552になりました。
かなり自分の中で良さそうな形が見えてきました。
まず右に行って、幅5列くらいでジグザグに下がります。次は5列くらいでジグザグに上がります。AAのある場所が最後に来るように調整します。
7.7日目 ついにスコアが上がった
2025年9月25日木曜日の朝です。
順位表のトップはyunixさんです。terry_u16さんが今9位なので、少し顔ぶれが変わった感じ。
私はといえば、321位。昨夜が300位くらいだったので、どんどん下がっています。巻き返したいもののスコアに結びつく良いアイデアが浮かびません。
昨日は貪欲に道を作る実装を書いていましたが、書き終わりませんでした。
ん、何か良さそうな配置を思いついたかも。
上下の移動を先に行うので上下に長い壁を作っておくと、行ったり来たりする長さを伸ばせそう。
ランダムに埋め込むのが思ったよりも良いように思います。
- 20%ほどトレントをランダムに埋め込んで入り口とAAの最短距離をふさいでいく
を入れたらスコアがぐっと伸びました。とはいえ、2秒でおさまらないテストケースがあったので、時間で打ち切りを入れます。
100テストケースの結果はぐっと良くなりました。
ドキドキしながら提出します。
絶対スコアは152390になり、前回の約1.5倍になりました。
相対スコアは提出前の333位から240位に上がりました。久しぶりの青パフォ！
一番スコアが良いのはseed93でスコア5323です。
一方、seed99のように中央が何もないようなものもあるのですが、左端と下の細い道を行ったり来たりして、思った以上に距離をかせいでいます。
まだスコアは伸ばせそう。
何となくわかってきたのは、未到達マスが点在するのが良さそうということ。DFSだと、長い経路になるものの、未到達マスを意図的に作ることができずにいました。
さて、ランダムにトレントを配置する充填率を15%から25%くらいに増やしてみますが、スコアのブレ幅が大きくて参考になりません。また、スコアの振れ幅が大きい理由がわかりません。
よし！週末は渦巻きや稲妻型のジグザグ、角に配置するパーツなど、いろいろ作ってためしてみよう。
8.8日目
順位表のトップです。
金曜の夜です。
ついに、最後の週末です。
まずはNによるの相対スコアの得点寄与を出します。厳密には0を出しているので、絶対スコアは正しくないのですが、ざっくりこんな感じ。
Nが30以内のとき
- 97356
- テストケース数61
- 相対スコア：16,278,981,769
- 1ケースあたりの相対スコア：266,868,554249,798,391
Nが31以上のとき
- 全体153170-97356=55814
- テストケース数39
- 相対スコア：9,738,627,247
- 1ケースあたりの相対スコア：249,798,391
というわけで、あまり変わらなそうだなあと思いました。
Nを28で分けたらちょうど50個ずつになりました。
- Nが28以下の相対スコア：13,054,879,382
- Nが29以上の相対スコア：11,821,918,970（およその値）
Nが小さいときの方が少し良いようです。
さて、seed62では、スコア7475が出ていました。
高スコアの理由をビジュアライザからつかめればと思います。
seed0の答えを手で作ります（いわゆるマニュアルモード風）
左図はV字風に右上と左上を蛇行します。
右図は真ん中より左を左上につなぎ、右を右上につないで、外周をコの字で回ります。
これまでAAは3方向を囲ってしまっていたけど、複数のルートにつないでおいて、近づいてきたらそのルートをふさぐということをすれば、3本行き止まりルートにできるかもしれない。ただし見通しが良いと見つかってしまうのでダメ。
9.9日目
コンテスト9日目、2025年9月27日土曜日の朝です。
やったー！ついに週末です。
朝晩ウォーキングをしながら考察をし続けていました。
- 右に行くには左からじゃないと行けないルート
- 下に行くには上から出ないといけないルート
- 隣のマスに移動するには反対の端まで行って戻ってこれないルート
- 入口を根として、AAを葉として、一番深くなるようにグラフを作る
- 4隅に見えづらい形のトレント配置を埋め込む
位置から別の方法を試したくなる気持ちをおさえて、今のプログラムを良くする方法を考えます。
今は何も置いていないスペースがあるので、そこに、「UST（ランダム全域木）を作る」、もしくは「視線カット用のトレントを植える」を追加します。4隅には見えづらい形の楔型経路のトレントを埋め込みました。
平均スコアは良くなり、seed0のスコアは1592になりました。
提出をします。提出前の277位、23,963,240,560から、255位、25,829,365,822になりました。
そうそう、順位表のトップはasi1024さんです。
ビジュアライザを見ます。
seed4では、目的地ではない場所を選択しているにもかかわらず、ルートがAAに向かっていて、早期発見されていました。
もったいない。
入口とAAの最短路をAA側から塞いでいくことをしていましたが、経路は長くなるものの、１本道になってしまい、良くない場合もあるのだなあと思います。
seed62でスコア8887が出ました
ビームサーチを追加してみたのですが、スコアは良くならず。
デバッグ出力をさせながらビジュアライザを見ること数時間。
全然別のことでまだやっていなかったAA周りに楔型のパターンを初期配置することを思い出したので追加します。少し良くなったので、提出をします。
絶対スコアは13000くらい上がったものの、皆に追い抜かれているので、相対順位は下がった分を戻した程度でした。
AA周りのパターンを修正（回転も可）します。
提出結果です。
10.10日目
コンテスト10日目、2025年9月28日日曜日の朝です。
順位表のトップにRafbillさんがいます！
自分はといえば262位でした。日中はさらに下がりそう。がんばるぞ！
ところで、寝ている間（?）に考察していたのですが、まずは、AAを外周沿いに右下まで1本道を作り、右下の隅からしか行けないようにします。
あとはある程度の区画を作ったら、L字型の長い道をつけ、そこからしか入れないようにします。
seed0を手で作ってみたけどイマイチ。
右下に入り口を全部集めてみようかな。
あ、これダメなパターン
うーん、その後もいくつか試しますが、どれもイマイチでした。
もう午後です。
これまでよかったDFS解と最短距離をふさぐ＋UST＋目隠し解をシミュレートして、良かった方を出力するプログラムにしたいと思います。NやAA座標の位置、Tの割合などの条件で場合分けできればと思っていましたが、よくわかりませんでした。
100テストケースのベストは今の1.5倍くらい。特にNが小さいケースでよくなりそうです。
solve1、solve2で解法を分けてシミュレーション結果のよかった方で本番を行うプログラムを書いてみますが、なかなか思うようなものができあがりません。
うーん、またも時間が経ってしまいました。
時間もなくなってきたので、2000テストケースを試します。
Nと木の設置割合とスコアの関係を見ます。
4隅のパターンを複数試したら少し良くなったので提出します。絶対スコアはベストを更新して、188112になりました。
相対スコアも提出前の26,097,194,002から少し上がって、順位も280位から256位に上がりました。
バグを見つけた（埋め込みパターンの4隅に配置する際の回転の向きが異なっていた）ので、修正して再提出します。
2000テストケースの結果を見ると、だいぶ良くなっていたので、システスで少し順位が上がるかもしれません。
さて、もう残り時間もあまりありませんが、新しいアイデアです。
- 入口とAAの間を斜めに分断します。
- 分断した場所をDFSで端から端まで何往復かするルートを作ります。
- AAがあるエリア、入り口があるエリアをその長いDFSルートを通らないと行き来できないようにします。
- AAがあるエリア、入り口があるエリアは今と同じ形でルートを作ります。
どうでしょうか。
うーん、うまく実装できない。
次のアイデアです。
- パターンがあるとき外周に細い通路を作って逆サイドに持ってくる
左に目的地があるときは、まず左に行くので、「左に行くには右に行かないと到達しない」といったルートにすると良いのではないかと思っています。
11.コンテスト最終日
2025年9月29日月曜日、コンテスト最終日の朝です。
なかなか改善できないまま、日にちだけが経っています。今日こそは！と思いましたが、仕事でした。朝晩少しだけできるかな。
さて、順位表のトップです。見るたびに違う気がしますが、入れ替わっているだけのような。システスでどのように変動するのか気になります。
そして、自分はといえば、少しずつ下がっていっています。
うーん、難しい。
昼休みです。まだちょっとだけできるかな。
seed4のビジュアライザ、左下の方に7×4のトレントで埋め尽くされた場所があります。
1手目
仕事が終わったので、コンテスト終了まで後1時間。
バグっていた箇所を修正して、2000テストケースを試します。
ベストを更新していたので、提出します。
ぎりぎり30分より前に提出できたので、ラスト1回の提出を残しています。
絶対スコアはベストより下がって、179538になりました。
相対スコアも提出前の288位から307位に下がってしまいました。こういうときは本当に悩ましいのですが、ローカルでの2000テストケースの結果を信頼して、もう一回提出することはせずに、このまま終了したいと思います。
時刻は18時45分。順位表のトップを眺めて終わりにしたいと思います。
んー、やっぱり、システスが終わるまで不安です。
12.終わりに
簡単そうに見えて、難しい問題でした。ちょっとしたことが点数を上げたり、下げたり、一喜一憂する感じ。とはいえ、下がることの方が多かったのですが。
ビジュアライザを見ながら試行錯誤をしていると、あっという間に時間が経ってしまいました。とてもおもしろかったです。
後は、システムテストで結果が良くなることを祈りたいと思います。
コンテスト後の午後9時からはXで感想会スペースを開く予定です。今から楽しみです。話に来てくれるといいなあ。聞きたい方もお気軽にご参加ください。
また、10月2日には解説放送も予定されています。
インタラクティブは経験値が足りないなあと思います。シミュレーションをもっと良い感じに取り入れたかったのですが、実装が大変でバグらせ続けました。次こそはもっと上の順位に行きたいものです。これからもあきらめずにがんばります。
13.最終結果（2025年10月2日更新）
システムテストが終了しました。3000テストケース全てでACしていました。
解説タブにあった詳細順位表を見ると、Nが小さい方が私の得点源でした。
暫定順位は309位でしたが、257位に上がりました。よかった。
全体ランキングが364位なの、このグラフを見ると実はすごい気がします。
さて、今回の問題の考察の最大ポイントはAAの花の隠し方でした。探索中の冒険者は、行き止まりであると判定すると、そこで向きを変えます。「AAが目的地として選ばれる場合以外にAAを訪れない（見られない）ようにする」トレントの配置がとても重要でした。
何となく良いと考えていた「渦巻き型」がどうして良いのかを、コンテスト後のXでの解法ポストや感想会スペースで説明して聞くことができ、とても納得しました。
今日の夜には解説放送があるので、きっとそのような内容も丁寧に説明してくれることでしょう。
