- 0.初めに
- 1.問題の概要
- 2.ビジュアライザで例を見る
- 3.最初の提出
- 4.適当に書いてみる
- 5.順位表を見る
- 6.最初の考察
- 7.重ならない駅の配置
- 8.バグを修正
- 9.収益を上げる
- 10.シミュレーションと山登り（失敗）
- 11.駅の評価関数の改善
- 12.線路の改善
- 13.山登り
- 14.初期ペアを複数試す
- 15.どこに駅を焼きなます
- 16.高速化のために必要なことを考える
- 17.収益が良くならなくても家や職場が増えれば採用する
- 18.入力生成方法の確認とクラスター検出方法について調べる
- 19.最初の駅を中央に置く(未採用)
- 20.再スタート
- 21.提出したい
- 22.バグの修正
- 23.まだバグが残っている
- 24.最後の週末
- 25.コンテスト最終日
- 26.今回やろうと思っていたこと
- 27.終わりに
- 28.最終結果（2025年3月3日）
- 29.復習
0.初めに
はじめまして、もしくはお久しぶりです。競技プログラミング歴が5年を超えた、かえでです。
今回は、RECRUIT 日本橋ハーフマラソン 2025冬（AtCoder Heuristic Contest 043） に参加しました。開催期間は2025年2月14日(金)19:00から2月24日(金)19:00までの、10日間の長期コンテストです。
前回のコンテストではスコアが伸び悩み、残念な結果に終わりましたが、今回は長期コンテストなので、焦らずじっくりと取り組もうと思います。
ヒューリスティック・コンテストでは参加者がそれぞれ自由な解法で取り組んでいます。だから、他の人がどのように問題を解いたのかが気になるものです。私の参加記も取り立てて役に立つものではないと思うのですが、思った以上に多くの人に読んでもらえています。そこで、もっと多くの方に解法ブログや参加記を書いてもらいたい、という思いも込めて今回も記録を公開することにしました。この参加記を読んで「自分も書いてみよう」と思っていただけたなら、それ以上望むことはありません。
この参加記は、リアルタイムで記録しています。そのため、少し冗長な部分もあるかもしれませんが、取り組みの過程や、その中で感じた苦労や喜びを一緒に楽しんでいただければうれしく思います。
1.問題の概要
問題文を最近はLLMを使って要約してもらっていることが多いです。また、C++のサンプルコードも書いてもらっています。自分が苦手な数式が出てきても、質問をすることで理解を深めています。ただ、それでも問題文の読み落としが多いので、今回は1日1回音読をしようと思います。
概要をまとめると下記の通り。
- N×N のグリッド(区画)に対して、鉄道会社として「駅」「線路」を建設し、R国の住民 M 人の通勤に利用してもらって利益を得るターン制シミュレーション。
- 各ターンの行動：以下のいずれか 1つ。
- 1. 線路の配置: 更地の区画1つを選び、6種類ある線路のいずれかに変える(コスト 100)
- 2. 駅の配置: 更地または線路の区画1つを選び、駅に変える(コスト 5000)
- 3. 待機: 何もしない
- 各ターン後の集金：
- 住民が家の近く (マンハッタン距離 ≤ 2) と職場の近く (マンハッタン距離 ≤ 2) に駅があり、それらの駅が線路または他の駅を介して繋がっている場合、会社に料金 (|is−it| + |js−jt|) を支払う。
- N×N区画、最初の所持金 K、ターン数 Tはそれぞれ下記の通り。
- N=50固定
- T=800固定
- Kは11000以上20000以下
- 目標は、T ターン終了後の資金ができるだけ大きくなるように行動を決めること。
音読もしました。音読しただけで15分かかってしまった。文章が長い。
2.ビジュアライザで例を見る
問題文中のリンク「例を見る」からビジュアライザを開きます。線路と駅と居住地と職場があるのが視覚的にわかって良い感じ
3.最初の提出
PythonのサンプルコードをC++に書き直して提出しました。同じ相対スコアが順位表に並んでいます。
まだ1位以外はサンプルコードのみの提出の様子。
pahcerで100テストケースの出力をします。こちらのツールも問題なく動いて一安心。
pahcerはTERRYさんが無料で配布しているテストケースの並列実行ツールで、使い方も簡単でとても助かっています。
詳しくはこちらから。
アップデート方法などはこちらから。
— TERRY (@terry_u16) 2025年2月13日
万が一正常に動かない場合はv0.1.1へのロールバックも可能です。https://t.co/46ZFSNHnGy
4.適当に書いてみる
サンプルコードを少し書きかえて、お金があるだけ駅2つと間に線路を引いてみました。
資金が減ってしまいました。
なるほど。
5.順位表を見る
午後7時に始まったコンテストは3時間ほど経過しました。
順位表を見ます。
自分のスコアは相対スコアなので、2,474,789,225まで下がっています。
自分のスコアの3倍程度のところに7,345,899,157と同じ値が並んでいました。何か適当な貪欲がありそうです。
トップを見ると、独走していました。
6.最初の考察
お風呂に入りながら考察をします。だいぶ考えがまとまった気がするのでメモ。
- 連結した駅の中で家と職場がマッチしている人の数が多い方が良い
- 今あるお金で線路が作れる距離で駅を作る必要がある
- １つの駅の中にたくさん家や職場が入っている方が良い
- マンハッタン距離2以内に駅が重ならないように配置する方が良い
これを満たす方法を考えます。
- 50×50÷13≒192
重ならないように駅を並べたときの個数は約192個。
- 192個の駅のペアを全探索する
- 評価関数を作って良いものからペアを作る
- 1回目は2個の駅と間に線路を作る
- 2回目以降は既存の駅とつながるように1個の駅を作り、線路を作る
- 2回目以降に駅を作る際は、駅＋線路のコストが完成後残りターンの集金でプラスにできるかを確認した後建設する
これを実装するために必要なデータ
- keyで家から職場、職場から家の場所が辞書引きできるようにする
- 駅のリスト（13パターン×192駅）
- とりあえず1パターンを先に作る
というわけで実装に取り掛かりたいと思います。
7.重ならない駅の配置
重ならない駅の配置を図にします。規則性がありそうな気がするものの、良くわかりません。
何とかコードを書いて、193個の座標を受け取ります。
・193個を駅の候補とします。
・駅からマンハッタン距離が2以内の家と職場に駅IDをつけて管理します。
・家の座標から職場の座標を参照できるようにする
・職場の座標から家の座標を参照できるようにする
やっと準備ができました。
駅の候補を全探索して評価します。
・家と職場の両方が含まれる場合、ペアができたと考え、ペアのマンハッタン距離×100する
・ペアができていない場合、家と職場間のマンハッタン距離の半分を足す
ここで実装をChatGPT o1 にお願いしてみます。
絶対スコア
一番良い組み合わせが建設できないときは全てのターンで待機を選んでいたので、サンプルコードより悪いスコアが100個のうち34個ありました。
必ず2駅と線路を作るようにします。
サンプルコードよりは全て良い値になりました。30分待って、再び提出します。
うん、予想通りな感じです。
順位表のトップを見ます。
2,952,021,677
今のスコアの1.5倍のところに同じ得点が固まっているので、何かありそう。
というわけでビジュアライザに戻って考察を進めます。
今はまだ2つの駅と間の線路しか作れていません。
評価がうまくできていないようです。
たとえば、左の駅の下に駅を作ると収益が増えそう。
最初に道を全て作ってしまおうかと思ったけど、全部の駅候補を置くことはできないので、最終的な駅同士を直接つないでしまって良さそう
注意：同じ職場に複数の人がいることがある
ん、こんな場合もある
seed1で10か所くらい
Same house position: 33 9
Same house position: 31 31
Same house position: 46 23
Same house position: 43 3
Same office position: 38 42
Same office position: 25 10
Same house position: 22 45
Same office position: 36 43
Same house position: 33 31
Same house position: 2 39
Same office position: 25 10
Same office position: 39 43
Same office position: 45 44
Same office position: 29 9
Same house position: 31 31
Same office position: 28 8
Same house position: 44 22
Same office position: 43 47
Same house position: 49 26
なるほど。
8.バグを修正
日曜の朝です。昨日の午後はカーブに置くレールでバグってしまい、バグの修正をしていたら一日終わってしまいました。今朝よく考えたらすぐに修正できました。適度に休憩しながらやらないとダメですね。
持っている資金で建設できるだけ駅を建設したところ。
おお、良い感じ。と思ったけど家も職場も含まない駅を作っているかも…。
最終金額はほぼゼロなので、これから収益を上げる評価部分を書いていきたいと思います。
100テストケースを回すと、半分くらいはすごく良くなって、半分くらいは悪くなっていました。家や職場がたくさんある場合は、とても収益を上げられているようです。
seed44のビジュアライザでは所持金が6353444になっていました！
きれい。
ところで、今回もChat GPT は使っているものの、短期とは異なり、自分でかなり手を入れながら実装をしています。長期の場合は細部まで自分の思った通りに動かしたいからです。
9.収益を上げる
さて、現在の順位を確認します。
順位表のトップです。
今より10倍はスコアを上げられそうなので、まずは2桁順位に戻したいと思います。
評価をきちんと書けばよくなるのはわかっているのですが、1回提出したくなったので単純な改善を考えます。
- 600ターン以降は駅を作らない
という条件をつけることにしました。手元の100ケースでは70ケースで改善していたので、提出をします。きっと今より相対スコアも上がるのではないかと思います。
絶対スコアは約10倍になり、相対スコアも約2.4倍になりました。順位も2桁になりました。
おお、良い感じ。
収益の考え方として、その駅ができると残りのターンでどのくらい収益が増えるかを計算し、残りのターン数で割りたいと思います。式にするとこんな感じでしょうか。
- 増収ー建設費（駅＋線路）/残りのターン数
とはいえ、まずは100テストケースのビジュアライザを見ます。より良い駅の選択方法はありそうだけど、ほぼイメージ通りでした。
さて、評価を変えました。
- 3つ目以降の駅の評価を今建設した駅に追加した際の増加分に変える
- スコア増加が0になったらやめる
- 残りターンの増収が5000未満なら建設をやめる
テストケースによって上がったり下がったりしました。３つ目が100テストケースで7割良くなったので、提出をします。
絶対スコアは下がりましたが、相対スコアは上がりました。
seed0のスコアは216715です。
あ、「600ターン以上で打ち切る」を消すのを忘れてた。
30分待って、もう一度提出します。
10.シミュレーションと山登り（失敗）
収益を増やすことが難しい。
- できるだけ駅と線路を作り、後からそのターン以降建設をやめたときの収益を予測し、最大となるところで建設を止める
- できあがった初期解の一部を追加、変更、削除し、シミュレーションして最終資金を山登り
などを試しますが、前者は思ったような値が出ず、後者はバグらせて時間だけが経過しました。最終提出のコードに戻り、もう一度出直すことにします。
11.駅の評価関数の改善
ビジュアライザを見ながら確認します。
- 線路上に駅を置くときに無駄な線路を引いていたので修正
- 駅を建設するときの指標として増益分から線路の建設コストを引く
上の2つを行ったら、seed0のスコアがぐっと上がりました。
おお！
100テストケースを試します。74%が良くなっていたので提出をします。絶対スコアはベストを更新し、順位は上がらないものの、相対スコアも上がりました。まだ貪欲なので、実行時間も151msです。
- 線路上に駅を置くことができる
線路上でも迂回した線路を作っていたので修正します。
- 駅パターンのx座標を+1したもので同様に解を出し、良い方を出力することにします。
- 駅パターンを5個に増やします。
ビジュアライザを見ます。
今一番良いのがseed44のスコア7487292。
こんなに埋まるんだ。ここまで来ると、線路の引き方を改善した方が良いように思います。資金もそうだけど、ターン数を奪ってしまうのがもったいない気がしました。
12.線路の改善
線路の改善は初期解からの改善を考えています。今考えていることです。
- 後から駅を置く場所に迂回しながら線路を引いておく
一番理想的だと思っているのはこの線路
- 右に2マス、下に2マス線路を引くもの。
13.山登り
駅のパターンを5通りそれぞれ試していたのを山登りで行ってみる。
微減
時間がものすごくかかって試行回数が少ない。3秒以内に終わらない。
Mが200以内のときだけ行う。
Mが200以内のときは全ての座標を駅候補に入れる。
それ以外は5パターンで。
Mで場合分けをしたら少し良くなったので提出。
絶対スコアはベストを更新。相対スコアも上がったけど順位は少し下がった。
相対スコアだから、Mが小さいときの方がスコアを稼げていそう。
最初に使う駅を焼きなましたい。
今一番良いスコアのseed44。スコア9532327。
こんなに重なっても駅を建設した方がスコアが良くなるのが自分の直感と違うので考察しなおしたい。
300ターンのときの１本レールがあって、両側で駅が広がっていくのは収益が上がりやすいパターンだと認識している。
今のseed0、スコア349792。やっぱりこの形なんだよねえ。
14.初期ペアを複数試す
15.どこに駅を焼きなます
平日になってしまったので、限られた時間で取り組んでいます。貪欲で選んでいた駅を焼きなますことにします。総移動距離を仮に600と決め、それを満たす範囲で駅を追加したり削除をして含まれる家とペア数が最大になるようにします。その後、連結費用が足りるようにどこを開始とするかを調べます。
バグらせたので、pairで持っていた座標を1次元に直します。Mが150以下の座標候補を全て入れるようにします。
経路の焼きなまし
駅の焼きなまし
高速化が大事そう
不要な情報をカットして、高速化したい
じっくり取り組みたい。
16.高速化のために必要なことを考える
2025年2月18日の朝です。コンテスト5日目になりました。高速化すれば良い解になることがわかってきました。高速化のためにbitsetを使い始めました。最初は駅のマスクと一人一人のマスクを重ねるといったことを考えいましたが、もっと良い方法がありそうに思いました。
頭の中にAHC020が思い浮かびました、電波塔の強度を変えて、全ての家が電波を受信できる最小の強度を求める問題です。
各駅について必要な情報を考えます。
- 駅の範囲に家に含まれる職場
- 上記の職場に対応する駅の範囲に含まれなくても良い家
- 駅の範囲に含まれる家
- 上記の家に対応する駅の範囲に含まれなくても良い職場
常にこの4つがわかればよいことに気がつきます。
駅の追加や削除も計算量O(1)で更新できます。
ん、いや違う。
・駅のマスク
・駅にある家に対応する職場
・駅にある職場に対応する家
でいいのかな。
重複しそう？
座標ではなく人にIDをつけてそれをマスクすればいいのかな。
17.収益が良くならなくても家や職場が増えれば採用する
高速化考え途中で、ふと、あ、評価がスコアだけだったと気が付きました。
・収益が良くならなくても、家や職場が増えれば採用する
ことにします。100テストケースを試すと下がるものもあったので、Mが800以上の場合、適用することにします。
提出をします。
絶対スコアは64515647に上がりました。下がり続けていた順位も少しだけ回復しました。
18.入力生成方法の確認とクラスター検出方法について調べる
コンテスト６日目の朝です。昨日はbit演算で高速化することにチャレンジしていて1日を使ってしまいました。だいたいは動くようになったのですが、あまり試行回数を増やせていないのが現状です。一旦ストップして今日は別のことをしたいと思います。
順位表のトップです。強い人が来たという感じ。常連の皆さんです。ただ、2位のymatsuxさん、5位のFplusFpusFさんはここまで順位が良いのを見たことがない気がしていて、陰ながら応援しています。
私の順位はにゃーん🐱（222位）。
どんどん順位が下がっていて悲しい。
これで朝のルーティン（順位表を眺めること）はおしまいにして、気を取り直していきましょう。
さて、今回の問題で気にかけなければいけないと思っていたのですが、まだやっていないこと、それは入力生成方法の確認です。
Mは50以上1600以下になっていますが、そのテストケースの生成は下のグラフのようになります。
- 小さいM（50～100程度）が多く、大きいM（1000以上）は少ない
- 50（50-100）、100（100-200）、200（200-400）、400（400-800）、800（800-1600）がそれぞれ20％ずつ出現します。
今後はMの出現率でグループを分けて平均を見ていきたいと思います。最後の提出だとこんな感じです。これだけスコアが違うので、提出した絶対スコアをあまり重要視しない方が良いと感じました。
つぎに家と職場についてです。
クラスターが発生している場所を予測します。この辺はChat GPT 4oに質問しながら進めます。
DBSCAN（Density-Based Spatial Clustering of Applications with Noise、密度ベースクラスタリング）という聞きなれない方法が出てきました。
- DBSCANについて
- データポイントの密度に基づいてクラスタを見つける 非階層型のクラスタリング手法
- K-Means のように事前にクラスタ数を指定する必要がなく、密度の高い領域を自動的にクラスタとして識別し、ノイズ点を排除できる
- アルゴリズムの流れ
１．すべてのデータ点を未分類（cluster_id = -1）として初期化。
２．任意の未分類のデータ点を選択し、ε 以内の点（近傍点）を取得。
３．近傍点の数が minPts 以上なら、新しいクラスターとしてラベル付け。
・選択したデータ点を「コアポイント」として登録
・近傍点を再帰的に探索し、さらに ε 以内の点をクラスターに追加
４．近傍点の数が minPts 未満なら、ノイズ点（孤立点）として記録。
５．すべてのデータ点を処理するまで繰り返す。 - 家と職場の座標は クラスター構造を持つ ため、DBSCAN に適したデータセット
- 応用例：GPSデータをクラスタリングし、人が集まりやすい場所（繁華街）を特定、ほか。
良さそうに思います。C++でコードを書いてもらって、実行してみます。
今回の条件は、EPSILON = 5 の範囲内で MIN_POINTS = 2 以上の点がある場合にクラスタ認識をします。
上位20を出力するようにしました。seed0では6か所が特定されました。
Top 20 cluster centers:
Cluster 5: (30, 33)
Cluster 6: (38, 21)
Cluster 3: (24, 11)
Cluster 1: (9, 41)
Cluster 4: (40, 6)
Cluster 2: (3, 7)
なるほど。
EPSILONとMIN_POINTSの適切な値を探ります。
seed0ではEPSILON=3、MIN_POINTS=3くらいで下記が出たのが良さそうに思います。
Top 20 cluster centers:
Cluster 3: (26, 9)
Cluster 2: (10, 43)
Cluster 1: (3, 7)
- EPSILON は「ある点が他の点とどれくらい近いと"同じクラスタ"とみなすか」を決めるパラメータ。
- MIN_POINTS は「クラスターを形成するのに必要な最小点数」を決めるパラメータ。
- 目安
クラスタごとに 5～15 の人がいる
一般的に MIN_POINTS ≈ 2 × 次元数（2D なら 4 程度） が目安
MIN_POINTS ≈ 3～10 が妥当
- 目安
Mが大きいときは、両方の値を大きくする必要がありそうです。
seed54です。やはりうまく検出できずに中央1点が出ました。
ところで、HomeとOfficeに分けるだけでもビジュアライザが見やすくなりますね。
kmeans法でクラスターの数を指定すると良い結果が出ます。とはいえ、今回はMが小さいときに良い場所を見つけられることの方が重要そうなので、ここでストップして、実際のコードに取り入れることを考えます。
19.最初の駅を中央に置く(未採用)
ここまで取り組んできて考えたのは、最初の駅の影響が大きいということです。
- 最初の駅をどこに置けたらよいか
やっぱり中央だよね。
これはまだ試していないことでした。
次に置く駅の選択肢を増やすには、どの場所からも既存の駅までの距離が近いことが一番良いことです。
ただ、今回は最初の2駅で家と職場を行き来できる人が現れないと収入ゼロで終わってしまうので、
- 最初に作る駅の一つはできるだけ中央にある方が良い
という条件を加えることにします。その後は、クラスターのある場所でレールを短く連結しながら駅を作っていく方針にします。
んー、これ、やる前から良さそうだなあ。何でまだ試していないんだろう。
家と職場の距離が遠い方が収入が良くなるので、どうしてもグリッドの両端に駅を作ってスタートしていました。それがどうも良くない気がしてきました。駅が増えていくにつれ、無駄なレールが多いなあと感じていました。
やってみた。
まだできていないのだけど、もう端から敷き詰めるほうがいいんじゃない？というお気持ち。
レールを先に書いてしまおうかな。
駅の数を200個にすればワーシャルフロイドがいけると思うので、それでいい感じに収入を計算できないかなぁ。負の数にしてベルマンフォードとか。
明日は手動で解く。ダイクストラを書く。
20.再スタート
2025年2月20日木曜日の朝です。コンテスト7日目を迎えました。私はちっともスコアを伸ばせず苦しい状況ですが、順位表を確認します。
Rafbillさんの安定感がすごい。そして私はといえば、推定パフォが水色に下がっています。1124人中262位。そろそろ何とかしたいものです。
下のメモがいつ考えていたのかわからないのですが、多分この辺りだと思うので、前後のつながりなく入れておきます。
2500個を試すことができない場合、何個駅の候補があればいいのかを考えました。そして、800ターンの答えではなく、建設する駅の座標と順番だけを保持するならばもっと少ない情報で済みます。
たとえば重ならないように駅を建設するならば、5ターンごとに駅を置くことになります。すると800ターンで160個。160ターンだと考えれば、プレイアウトもできそうに思えます。線路は最後に引くだけ。線路を引く間はコストの増減をまとめて計算できます。どこからスタートするかがわからなくて、それをたくさん試せれば、良い解ができるはず。
というわけで簡略化したコードを書くぞと決意しました。
- 駅の座標と建設する順番だけが必要な情報である（所持金を考慮しない場合で最大160個）
今に戻ります。
この頃考察のし過ぎで寝不足続きでしたが、昨日は早めに就寝したので、今は頭もすっきりしました。
- 駅候補の一覧を読み込む
- 駅候補を絞り込む
- 家と職場のどちらも１個も含まれない駅を除外する
- 全ての駅間の距離を前計算する
- 2個の駅を選ぶ
- 今の予算で連結できる、かつ家と職場のペアが1個以上含まれなければ1に戻る
- 駅建設費×2とレール建設費を引き、建設にかかるターンを進める
- 次の駅を選ぶ
- 駅建設費と今ある駅までのレール建設費がたまるまでのターンを計算して足す（コストをターン分の収益で割る）
- 収益の更新
- 建設した駅情報の更新
- 建設したレール情報の更新
- 800ターンで終了
- 4から6を制限時間いっぱい試行して、一番良かった解を出力する山登りを行う
長い時間をかけて、やっと書きあがりました。書き出してみると、プログラムがだいぶすっきりとした気がします。
seed54のビジュアライザではスコア12702130が出ました。
しかし、seed0は4327。うーん。これでは提出できません。これまでの良いものと場合分けでまとめられないかと思いますが、コードが長すぎる…。
そして、実際にシミュレーションせずに概算で行う部分が新しく、これまで作った関数と入れ替えたりと、いろいろとやらないといけなそうことがあって手が止まってしまいました。
寝ようかな。
21.提出したい
2025年2月21日金曜日の朝です。コンテストは月曜日までなので、残り時間も少なくなってきました。昨日の夜は、コードを書きなおすのに夢中で、参加記を書かないで終わってしまいました。提出の際にブログに記録を残すことが多いので（ジャッジを待っているときに書いていることが多い）、提出をしないと何をしているのかわからないかもしれません。（先ほどちょっと前日分を書き足しました。）
ブログを書かないときでも、下記の表のようにエクセルで100テストケースの結果を管理しています。問題によっては平均を見ることもあるのですが、今回は特にテストケースによって得点が大きく異なるので、テストケースごとの前回との比較を重要視しています。
ベストをかき集めることができれば、今の1.5倍程度の得点にはなりそうなのですが…。
さて、現在の順位表です。saharanさんが3位に浮上。
私は301位まで下がりました。助けて～。早く提出したい。
時間を伸ばしてみます。
・「駅順を変える山登り」→上がる
・「最初の2個の駅を決める山登り」→上がらない
あれ？なんかバグってそう。
んー！バグ見つけた！！！
最初に作れる初期ペアを全部入れてなかった！
そしてseed0が上がった！
seed0のスコアは464428になっていました。
感動…。ここまでつらかったから泣ける。
100テストケースを試します。
あれ？まだ47とかいうスコアがありました。なぜ？
ん、駅ができていない…
22.バグの修正
お昼です。
3つ目以降の駅の選び方の評価が間違っていたことが判明。修正します。
60個くらいしか良くなっていませんが、一回提出しようかなあ…。
提出前302位、11,122,984,738から264位、14,576,832,283になり、ちょっと持ち直しました。
レールの上に駅が建設できることを入れていなかったので修正します。
提出すると、15Bを超えました。
23.まだバグが残っている
まだ直せていないのがこれ。100テストケース中18個もあります。
seed6の家と職場を結んだ線分を描いてみました。
修正して駅は作るようになりましたが、スコアは432。これなら何もしないで最初の所持金を維持している方が良いです。
貪欲にやっていたときは11万くらいのスコアが出ていました。
ターン数の計算で、「お金がたまるまでにかかるターン数」しか入れてなかったので、「必要なレール数（=必要なターン数）」と大きい方を選択するように修正します。
いや、合ってた。
そうかー。マンハッタン距離で概算すると、4つ接続してしまっている駅とか、一番近い十字がつながっているとかありそう。
やっぱりBFSに戻そうかな。
24.最後の週末
2025年2月22日土曜日の朝です。順票のトップは接戦です。wleiteさんが2位にいます！そして7位にMathGorillaさんがいます。
そして私はというと、1225人中286位。また推定パフォが水色に落ちています。
がんばろー。
さて、やることです。
- 序盤の300ターンで一番所持金が増える駅の建設方法を全探索する
300という数字は適当に変えて試す予定ですが、別に800ターン試さなくてもいいなというのが結論です。
駅3つなら、今は駅候補を200くらいに絞っているので、全探索でも8×1000000なので十分高速に求められます。
その後は序盤と終盤の戦略を変えることをしたいと思います。これまでは5ターン置きに重ならないように駅を建設することがベストだと思っていたのですが、重複があっても連続しても駅を建設した方が所持金が増えることがあるなあと思い出したからです。
- 序盤・・・無駄なく収益を増やす
- 後半・・・残りターンで建設費を回収できるなら範囲が重複してでも駅をたくさん作る
というわけで実装します。
ん、ふと「斜めなだけで難しいんだよなぁ」と思っていたら、過去に同じことを思った覚えがあるので検索。「RECRUIT 日本橋ハーフマラソン 2021」の「B問題 マッサージチェア2021」のことでした。解説配信があったので、聞きながら実装を進めることにします。
解説配信を見て思いついたこと
- 駅の候補座標を焼きなます
できる？今の駅候補よりも良い状態とは何かを考えてみます。
- 全ての家と職場をカバーできる駅の個数が少ないほど良い
あ、わりとシンプルかも。
削除をバグらせそうだったので、削除はなしで、良い駅を作ることに。
スコアは悪いけど、seed0で全部の家と職場をカバーできています。
全てを含む重複した駅があれば削除します。
結局焼きなましはできなかったけど、初期のポジションよりは良い駅のリストができあがったようです。一旦提出します。
絶対スコアは下がりましたが、相対スコアはほんの少しだけ上がりました。
ん－、やっとバグっていたところわかった。
所持金が100を超えないとレールが作れないからだ。
単純に金額をレール数で割ってはいけなかった。
概算のシミュレーションのときは10万回以上試すことができていたものの、BFSのシミュレーションに変えたら試行回数が数千に下がってしまった。
線路上に置くときにお金が無くても置いてしまうバグが取れない。
それでも全体で見れば答えが良くなったので提出することにします。
WAが出てしまい得点は0。相対スコアも下がってしまいました。
えーん。
シミュレーションに戻してみる
またWA。うーん。最初の貪欲がバグってそう。
うーん、そうなのかー。
ああ、そうか。駅の十字の４方向入れないと。
下がった
元に戻す
初期解を貪欲で決める
再提出
WAが消えた。
朝からやっていたけど、ブログは書けていないです。
貪欲を書きなおして、初期の駅2個のペアで貪欲をやって上位10個を取る。そこから山登り。山登りには追加と削除を入れる。
何かスコアが上がると思うのに実装してみるとたいして上がらなかったり、下がったりしています。
何とか絶対スコアはベストを更新。
しかし順位は朝よりも下がっている…。
山登り上位10個をシミュレーション一番良い解（書き出しでバグっている）
焼きなまし
おーやっと17Bを超えた。
ビジュアライザを見ると、駅の建設をやめるターンが早い。
経路を変えたい。
ビジュアライザで、１つずつseedを再生していく。
seed1のビジュアライザ。先に2つできたあとに、オレンジの丸に駅を建設している。もしレールの建設を赤戦にしていたら、レールを建設しなくても良くなる。
過去改変貪欲できる？
経路を変える際の差異。もちろんレールの数は変わらない。使うレールと座標の位置が変わる。
- AからBに行きたいときに途中でCを経由する経路を作って差し替える
そんなことができれば理想的。そこから先はもう一度シミュレートするのか、その駅の部分だけを差し替えれるのか。ターン数も変わって収益も違うからもう一度シミュレーションした方が確実な気がする。
そういえば、昨日は未採用だったけど、経由したい駅を一番たくさん通る経路を求めるDPを書いたのだった。昨日は作るかどうかわからない候補駅全てを経由することにしたからイマイチだったけど、実際に建設することがわかっている駅を通るなら、よりよい結果が出そうです。
ボツコードの中から探すの難しい…。どこ？
探して作りました。
微妙でした…。
なんかWAも多くて…
と思ったのですが、ベストを更新しているものがある！
と思ったけど一段ずれていただけでした。
そうだ、適当な座標を入れよう。
（就寝）
25.コンテスト最終日
コンテスト最終日、2025年2月24日月曜日の朝です。月曜日だけど祝日でお休みなので、今日1日AHCに取り組むことができます。うれしい。
昨日はブログを書くよりもプログラミングがしたくて、一日、試行錯誤していました。
さて、最終日の順位表です。いつもの強い面々といった感じなのですが、いつもより海外勢が多いかも。
私は1369人中351位、相対スコアは17,177,428,086。ずるずると下がりつつあります。
さて、シミュレーションのターン数経過の計算が間違っていたので修正して一旦提出します。
絶対スコアを更新しました。相対スコアももう少しで18Bに届きそうです。
駅の4方向が埋まっているかどうかがなくなっていたので（バージョンを戻すと入れたと思ったものがなくなっている…）追加します。
ん、そういえば、これを入れたらスコアが下がった気がする。
どこで更新するのかが難しかった。実際シミュレーションするなら必要ない気がした。簡略化したときに欲しいのだけど。ちょっと保留。
下の図で線路を引いているけど、線路の上に駅を建設すれば同じ家をカバーできる。
次はこれを実装したい。
だめだ、全然うまくいかない。
お昼ご飯を食べたら、候補駅で最小全域木を作って最初にレールを置ける場所を決める。
うーん、最小全域木だと遠回りすぎ。
とりあえず近い辺から結んで経路を作り、盤面を埋めていくことにします。
あれ、うまくいかない。
右に2マス、下に3マス進んだところに駅があればこれを経路として盤面を埋めることにします。うーん、微妙。
直線も追加します。
出来上がった経路がこれ。無駄だなぁ。
今後駅を追加しやすくなるとしても、微妙すぎます。
うーん、やめよう。
時刻は14時半。残り4時間半です。
長いような短いような。でもまだできそうです。
26.今回やろうと思っていたこと
そういえば今回の目標はこれでした。
- ちゃんと論理的に詰める
やはり、今回も論理的に詰めることはできなかった。
試そうと思って事前に書き出していたリストです。やったことにOKをつけました。
- OK:時間を伸ばす
- OK:ざっくりと計算
- ビームサーチ
- OK:山登り
- OK:焼きなまし
- OK:よりよい貪欲と評価関数を探す（もっと良いものがありそうだけど）
- OK:テストケースは多めに試す
- 最初は小さい盤面で考察する（うまく作れなかった）
- OK:関数でパーツを作って柔軟に変更できるようにする
- OK:マニュアルモードを探す（なかった）
- OK:自分でビジュアライザを作る（作ったけど使っていない）
- OK:bit演算を使う
- 重複除去をする
- キック
- OK:多点スタート
重複除去は今からでもできそうなので入れます。
入れました。
あんまり変わらず。
評価関数を変えます。
序盤に家と職場が増えることの重みづけ、全体にターン数が短いことに重みづけをします。
うーん、悪くなった。どうして？
疲れたのでお昼寝。
30分寝て起床。
今あるつないだ辺を一旦削除して、もう一度つなぎなおす。
やろうとしたけど難しい！
ビジュアライザを見ます。
この場所を左上から線路をのばして駅を作っていますが、線路上に直接立てても同じことです。
これを直そう！
書いた。だいぶ見た目が変わったかも。
提出！
下がってる…。
うーん、レールの上に置くことを他にも適用してみたものの、うまくいきません。
一旦今朝出したベストを1000テストケース試行してWAが出ないかを確認します。他に提出予定もないので、もう一度提出して一番新しいものにします。
システムテストがこの後行われるので、一番よかったものを忘れずに最後に出しなおさなくてはなりません。
1000テストケースの結果が出ました。なんと1000テストケース中、14個もWAが出ています。
何とか修正したと思ったら、他のところでWAが。18時半前にこれで大丈夫だと思って提出したら1ケースでWAが出ました。焦ります。
何と見つけました！
１か所お金があるか確認せずに駅を建てていた箇所がありました。
ターンを進めてお金を得るフェーズを入れます。
今度こそWAが消えたようです。
1000テストケースを試します。
時刻は18時50分を過ぎています。残り30秒になったら前回の提出から30分経過するのでもう一度提出することができます。
はぁー、間に合った。（まだ提出できていないので気が抜けません）
大きなため息。
ベストでは519,878を出していたseed0ですが、こんな感じになりました。スコア461874。
27.終わりに
最後まで息つく暇もなくコンテストが終了しました。はらはらしたけど、ハッピーエンドは訪れなかった。悲しい。
それでも、他の人がどんな解法で解いたのかを聞くのが今からとても楽しみです。
コンテストが終わった後、今日の21時からスペースを行う予定です。
また、AHCラジオも放送予定なので楽しみに待っていてください。
今回は文章らしい文章ではなくて申し訳ない気持ちですが、ここまで読んでくださり、どうもありがとうございました！次回のAHCでまた会いましょう。
次こそは良い結果を出したい！これからもがんばりたいと思います。
28.最終結果（2025年3月3日）
2025年2月26日にシステムテストが終わりました。暫定390位から2つ順位が上がって1422人中388位になりました。2000テストケースのうち5ケースがWAでした。
Ratingは4上がったものの、時間減衰が始まっているので前回のコンテスト時より2下がり、1900になりました。
29.復習
2025年2月27日20時からはAHCラジオが放送され、tomerunさんが出演され、詳しく問題について説明をしてくれました。とてもわかりやすかったのでおすすめです。
さて、何といっても今回良くなかったのは駅の候補座標を最初から間引いてしまったことです。途中の貪欲法よりもスコアが悪くなっているものが1割から2割あるまま最終提出を行ってしまいました。それはMが小さいとき場合だったので、相対スコアが良くならない大きな原因となりました。
まず、自分のプログラムから思い込みで書いた部分を消しました。思い込みとは、「カバーする家と職場が同じ駅候補は一つにまとめても良い」と思っていたことです。
再びMが小さいときは全ての座標を入れることにしました。また、重複していると思って駅候補を削除することをやめました。
すると、seed0のスコアが575472になりました。
しかし、TLEするケースが増えました。数時間修正を試みましたが継ぎ足しながら書き続けたプログラムを修正することは難しく、気力が尽きてしまいました。
しばらく寝かせて、また復習の機会を持ちたいと思います。なかなか思った通りのプログラムを書くことはできず、もどかしく思います。
いつかこの思いが解消される日が来るのでしょうか。
というわけで、今回の復習はここで一旦終了したいと思います。
