RECRUIT 日本橋ハーフマラソン 2024夏（AtCoder Heuristic Contest 036）参加記

0.はじめに
1.問題文を読む
2.最初の提出
3.最初の考察
4.BFS
5.考察
6.考察2
7.信号操作をまとめる
8.100テストケースの結果
9.ダイクストラでワープ（高速道路）を実装する
10.デバッグ、そしてデバッグ
11.考察
12.ダイクストラの辺にワープ（高速道路）の戻りを追加する
13.配列Ａを改善する
14.仕切り直し（ダメ）
15.対角線ルートを作成するための頂点選択をランダムにする
16.停滞
17.ラストスパート
18.配列Bの長さのなるべく隣接した頂点のグループを作る
19.コンテスト最終日
20.終わりに
21.最終結果（2024年9月3日更新）

0.はじめに

はじめまして、もしくはお久しぶりです。競プロ歴4年8か月のかえでです。

今回は、 RECRUIT 日本橋ハーフマラソン 2024夏（AtCoder Heuristic Contest 036）に参加しました。開催期間は2024年8月23日(金)19:00から2024年9月2日(月)19:00までの11日間の長期コンテストです。

さて、今日は2024年8月22日、木曜日の夜です。久しぶりのコンテストなので前日からわくわくして待っているところです。前回のAHC033参加記を読むと全く同じ行動をとっていました。今回のリクルートハーフマラソンはAHCの中でも相性が良いと感じているコンテスト。良い結果を残せるといいなあと思います。

また、この参加記はコンテスト開催中にリアルタイムで書いているので冗長な個所があるかもしれません。それでも、この参加記を読んだ方に少しでもヒューリスティック・コンテストの楽しさを感じてもらえたらうれしく思います。

1.問題文を読む

atcoder.jp

問題文を読みます。内容をかいつまんで書き出してみます。

都市（N=600固定）と道路（N-1≤M≤3N-6）がある
指定された順番(T=600)で都市を訪問する
配列Aと配列Bで信号の色を制御する
信号の操作回数が最小となるようにルートを決めて信号操作を行う

TSP（巡回セールスマン問題）なのかなあと思いますが、配列Aと配列Bで行う信号操作が何なのかピンときません。ビジュアライザを見ることにします。

問題文の「例を見る」というリンク先を開くとビジュアライザが開きます。目的地に向かって頂点が移動する様子を見ることができました。

2.最初の提出

サンプルコードがあったのでダウンロードして実行します。「例を見る」と同じ出力が出ました。サンプルコードを提出します。

コンテスト開始から1時間近く経過していましたが、順位は14位でした（提出人数は記録するのを忘れました）。同じ得点が並びます。

3.最初の考察

少しずつ問題がわかってきました。配列Bの信号の指示を連続で出したいと思います。そのためにどうするかと考えたとき、配列Aを信号の指示順に並べたい。しかし移動の際に重複する頂点を含めると配列Aのサイズを超えてしまいます。まずは重複を排除した訪問順の頂点を配列Aとし、連続している場合は配列Bのサイズまでそれを一度に出力するようにしたいと思います。

また、経路自体も現在のサンプルコードが「ユークリッド距離が小さい頂点を優先して探索する深さ優先探索」としているので、BFSに変更したら経路が短くなるのではと思いました。

それでよいのでしょうか。一旦パソコンから離れて、お風呂に入りながら考えることにします。

何となく基幹道路を作って、高速道路と一般道みたいな形を作った方が効率が良いのではないだろうかと思います。どこを高速道路にするのかという部分を詰めると結構スコアが良くなりそうなイメージがしました。ただどうやって実装したら良いのかが思い浮かびません。

まずは現在のサンプルコードを元にした改善コードを書いてみたいと思います。

配列Bで使いたい順に配列Aを並べてみました。seed0では得点が20554になりました。提出すると50ケースで全てWAになりました。

何となく配列外参照をしている気がするので、その辺りを修正してみます。修正を終えて提出しますが、３回目も全ケースWAでした。手元で実行した結果は、seed1は37311、seed2は34951でした。

うーん、何でだろう。続きは明日行いたいと思います。

4.BFS

2024年8月24日土曜日です。今日は、昼間に第五回日本最強プログラマー学生選手権決勝オンサイトがあり、スタッフとして休日出勤をしました。

休み時間にAHCに取り組むことにします。昨日やっていたコードは全て破棄して再度書き直すことにしました。サンプルのコードをBFSにします。配列Bの信号の指示は1つずつ行います。

コードを書き上げた後、seedをいくつか試してビジュアライザで見ると問題なさそうだったので提出します。今度は無事ACしました。

BFSにして距離が短くなったのでしょう。絶対スコアは356812に下がりました。そして順位は190位になりました。順位表を眺めると同じ得点が並んでいます。みんな同じことを考えているのだなあと思います。相対スコアからトップとだいぶ差がついてきているなあと思いました。

5.考察

2024年8月24日の夜です。オンサイトが終了し、帰宅途中で21時になってしまったので、ABC368にUnratedで参加しました。電車の中でスマホコーディングをして帰宅後に机に座って続きをします。先ほどABC368が終了し、やっとAHCに取り組む時間ができました。

考察の続きをします。スコアは信号を変える回数そのままだったので、スコアを良くするには信号をまとめて変える必要があります。まとめて変えるためには、繰り返し使用する道を決める必要があります。ワープできる道があると考えたとき、どんなふうに道があると良いのだろうと考えます。

長い道であること
どの点からもその道に入るまでに短い距離であること

それを満たす形を考えます。

格子状の道。縦の道で配列Aの半分のサイズを埋め、残りを横の道で埋める
渦巻き状
放射状

相変わらず実装方法は思いつきません。考えながら眠りにつくことにします。

6.考察2

翌日になりました。2024年8月25日（日）の朝です。

ルート作りの方法を考えていましたが、座標をベースに考えた方が楽な気がしてきました。配列AがNに近ければ一方通行の環状ループ。2*Nに近ければ往復できるルートを作るのがよさそうだと思います。

コードで出力する順序も整理します。

指定された都市を巡回するルートを考える
配列Aを考える
配列Bを考える

（時間が空いてしまったのでその間に考えた事）

エリアを9個に分割してその中で次数の多い頂点を選んで中継地点とする。中継地点同士を結んで高速道路として使用する。
連続移動の２点を１回で出力すればスコアは減少する。

7.信号操作をまとめる

信号操作を２つまとめて出力するコードを実装して提出します。一度も出ていない頂点をsetで管理し、訪問順に新しい頂点だけを追加するようにしました。訪問都市が配列Aで連続している場合に２つまとめた信号操作を出力します。

配列Aで使用していない部分があったので、空いている箇所に訪問済みの頂点であっても埋めます。

信号操作のまとめる長さを長さ２から配列Bのサイズに伸ばします。まとめられるだけまとめて出力することにします。

訪問する都市の信号がすでに青の場合（配列Bに含まれている場合）は信号操作をとばすようにします。

絶対スコアが20万を切りました。これまでコードを書きながらサンプルコードを2,3個試して良さそうなら提出していましたが、そろそろ100ケースを試したいと思います。

8.100テストケースの結果

100テストケースを試して気が付きました。スコアとターン数を間違えていました。スコア計算を修正します。提出した50ケースの平均は3736なので、偏りがあるのかもしれません。また、上位との差を考えると、相対スコアの寄与分に偏りがあるのかもしれません。トップの1/4くらいのスコアしか取れていないので、この状態が続くようであれば相対的に良いところを伸ばすのもありなのかもしれません。

スコアが一番悪かったseed50のビジュアライザを見ます。戻ることもあるかもしれないので、今は連続数が1のとき、最初の配列の信号を入れ替えていたのを前の配列の次の場所に入れることにします。

さて、信号をまとめて出力できる場所はワープできる箇所として積極的に使いたいと思います。BFSだったのをダイクストラに変更します。

9.ダイクストラでワープ（高速道路）を実装する

元の隣接した辺の重みを例えば100とし、配列Aの並びを重みを連続した長さで割ったコストを入れて辺としてつなぐことにします。出力の際は信号操作は長さをワープの長さにします。また、移動する頂点はワープの間の頂点も出力するようにしたいと思います。この実装がどうもうまく書けずに悩んでいるのですが、うまく実装できればスコアが良くなるはずです。やっと基幹道路（高速道路）案の実装まで戻ってくることができました。それができたら、配列Aの焼きなましまでいってみたいのですが、どこまでがんばれるでしょうか。

配列Bに含まれる部分の判定を間違っていました。順番は関係ないので、含まれる部分が多い箇所を切り出したいと思います。

うーん、全体的に煩雑なのでリファクタリングをしたいと思います。

10.デバッグ、そしてデバッグ

昨日は一日デバッグをしていました。平日なので朝と夜だけですが。ワープの復元がなかなかうまくいきません。一方通行限定にしたり、かなり限定したワープのみを作ることにしてデバッグを進めます。

やっとわかりやすいバグは修正できた気がします。100テストケースを試している間に待ちきれずに提出します。結果は29AC、21WA。ショック…。

その後終わった100テストケースの結果は平均スコア2818、2割くらいスコアを下げていたので残念。しかし、全部ACすれば14Gくらいにはなりそうです。

デバッグを続けます。本当に長い戦いでした。ついにバグが消えた気がします。ドキドキしながら提出をします。やっと…

ACしました！

絶対スコアも前回の172103から110859になり36%ほど減りました。

相対スコアも18Gを超え、推定が青パフォになりました。

よかった。

デバッグが苦しかった。順番に配列A、配列B、ダイクストラ、出力、ワープをそれぞれ出力デバッグをして、エラーを洗い出しました。

はぁ、本当に大変でした。

ただ、デバッグをしているときに、かなり頭の中も整理された気がします。

信号は一度に配列Bの長さ全部分を変えた方が良い
ワープ部分の辺の重みは１と考えて良い

まだ辺の向きが有向だったり、ワープが途中下車できないものしか作っていないので、この辺を増やしていけば、まだスコアは上げることができそうに思います。

そして、今やりたいのが、配列Aのワープをあらかじめ作ること。

９個くらいにエリアを分けて、その中から１点を選びます。
９個の点を行き来できるようにワープを作る

そうすれば、高速道路の完成です。高速道路の作り方を試して焼きなませれば高得点が狙えそうだと思います。

11.考察

さて、100テストケースの配列Aと配列Bのサイズ別のスコアを見ます。

元のスコアに比べて全体的にスコアが減少したのがわかります。もしかするとサイズ別の相対スコアを調べた方が良い気がします。おそらく配列のサイズが大きいものは、もっとスコアが下がるような気がします。トップとの相対スコアの差はとても大きいので得点源とそうでないものが分かれているかもしれません。

まだ時間はあるのでちょっと工夫をすると、ぐんとスコアが下がるということはこれからもありそうなので、最後まであきらめずにがんばりたいと思います。

サンプルコードのseed0が6863、現在のスコアは2882です。

12.ダイクストラの辺にワープ（高速道路）の戻りを追加する

ワープ部分が有向辺だったので戻り辺を追加して無向辺にします。ワープを戻す部分の実装は今回はすんなりとできました。3%ほどスコアが減りました。こんなものかな？もっと減ってもいいような気がしますが一旦提出します。1ケースWAが出て絶対スコアは0でした。相対スコアは少し上がって18,916,850,805になりました。

またデバッグしないと…。何か変な気が自分でもしているので直したいと思います。

WAの原因を調べるため、100テストケースのビジュアライザを見て確認します。seed69でエラーが出ていました。配列Aに0が並んでいる箇所がありました。これはおかしい。

配列外参照をしていました。修正できたので再提出をします。今度は無事50ケースACしました。

13.配列Ａを改善する

今は配列Ａを訪問順でまだ出てきていない都市順に追加し、全部追加したのちはルート順に埋めていました。

そろそろきちんとした道を作りたいと思います。できあがりのイメージは中心から8方向放射状に行き来できる高速道路です。

3×3の9つのエリアに分割して、各都市を頂点として追加する
各エリアからランダムに1点を選ぶ
中心とその周囲の各都市をつなぐルートで配列Ａを埋める
配列Ｂの長さに分割した辺を追加する

これで１回の信号操作で高速に行き来する道ができるはずです。

前の行から少し時間が空きました。各エリアから選ぶ都市を真ん中は中心、それ以外は端から貪欲に選んでやってみたいと思います。また、まずは4点にして対角線ルートを作りたいと思います。

対角線ルートを使った配列Aのコードは短時間で書くことができました。(0,0),(0,10000),(10000,0),(10000,10000)※に一番近い都市を見つけて、対角線上にダイクストラでルートを求めます。あとは使っていない必要な都市を配列Aに追加していきます。まだ配列Aが余っていれば、ルート順に埋めていきます。（※後から気づいたのですが座標の盤面サイズを10000×10000だと思っていました。正解は1000×1000）

100テストケースの平均は2158。提出すると、絶対スコアは100624になりました。順調に改善できています。

楽しい。

もっと高速道路を増やしたいと思います。十字になるようにルートを追加します。実装して試しますが、スコアが悪くなりました。十字ではなく外枠のようなルートを追加したいと思います。これもまたスコアが良くなりません。

真ん中を一周する環状にしてみたいと思います。これもいまいちでした。

そうか…。こちらが良いと思う道よりも、まわる都市順に合わせた道を作る方が大事なのかもしれません。通る都市をカウントすればいいのかな。良い考えが思い浮かびません。

連続したルートの信号を一度に変えてしまうのが良いのですが、配列Ａのサイズは限られています。

そういえば、と思い出したので、分割したワープを作りたいと思います。

その前に対角線を一筆書きに変えます（ほぼ変わらなかったけど採用）

対角線を中心を通るようにしてみようかな。うーん、やってみたけど微妙でした。

半分のルートを追加してみましたがバグるので本日は終了。27日火曜日の夜でした。

お風呂に入ったらもっとスコアが良くなって良いはずだと思ったのでコードを見直すことにします。

14.仕切り直し（ダメ）

バグはなくなった気がするものの、スコアはよくなりません。一旦ここは保留にして別のアイデアを試します。

ダイクストラで求めたルートの頂点数をカウントし、累積和をとって、配列Bの長さの和が大きい順に配列Aを埋めたいと思います。

カウントしてみると、思ったよりもばらつきがありました。

実装してみますが、難しい。回数が少なくても必要な頂点は配列Aに入れなくてはなりません。寝不足続きで頭が動かないので、今日は寝ることにします。

15.対角線ルートを作成するための頂点選択をランダムにする

スコアが良くならない原因がわからないので、別のアプローチを行うことにしました。四隅の頂点を複数候補としてその中からランダムに選ぶことにしました。すると、スコアが良くなる場合があることがわかりました。候補として選ぶ点を訪問予定の都市に限定することにします。また、その過程で、頂点をうまく選べていないバグに気が付きました。そう、全体の盤面サイズが1000×1000なのに、これまで10000×10000と考えていたのでした。

バグを修正し、対角線ルートをランダムに選び、時間内に山登りをすることにします。ついに、少しスコアが良くなりました！100テストケースを試すと2%ほどスコアが減っていました。

提出をします。無事ACしました。提出前は相対スコアが19,473,635,121でしたが再び20Gを超えました。順位も提出前の213位から200位に上がりました。絶対スコアが10万を切りました。

参加者のスコアが上がってきているので、現在の順位を維持するだけでも精一杯です。

ところで、いまいちすっきりとしないコードを書いているため、制限時間が3秒あるのに、乱択山登りが10回も試せていません。時間を伸ばしてみます。

…変わりませんでした。スコアは良くなりません。

もっと確実にスコアを伸ばせる方法を考えないといけないようです。余分な辺と頂点を削除してみたらどうかなあと思います。毎回配列Bのサイズ分動けるのがベストなので、例えばseed0が1ずつ動いて6863（サンプルコードのスコア）なら、配列Bのサイズ5で割った1373くらいまで減るのかもしれません。現在のスコアは2441なので、まだ半分近く減らさなければいけません。

余分な辺と頂点を削除すると配列Aに余計なものを入れなくてもよくなります。最終的には必要な道を決めてしまうことができると最も効率が良くなる気がします。