AHC043 参加記 & 1位解法解説

ここしばらく RECRUIT 日本橋ハーフマラソン 2025冬（AtCoder Heuristic Contest 043）に参加していました。最終的に優勝することができたので、参加記兼 1 位解法の解説を書いていきます。

今回も日本橋ハーフマラソンの例に漏れずユニークな問題でとても面白かったです！

Heuristic Contest とは？

想定された「正解」がない問題に対して、できるだけ “良い” 解を制限時間内に出力するプログラムを書くコンテストです。

答えのある問題に対して「できるだけ早く、正確に」解答するアルゴリズムタイプのコンテストとはまた一味違った楽しみがあります。

明確な正解・不正解による線引きではなく連続的なスコアによる順位付けがあり、全参加者がレベルによらず同じ問題に取り組むので、どのレベル帯の参加者も「今の自分より少し上を目指して取り組む」ことができます。

コンテスト終了後には各々の参加者が SNS やブログで自身の解法を解説するフェイズがあり、ここで他の参加者とどのように問題に取り組んだのかを語り合うという醍醐味もあります。

ともかくここでは魅力は語り切れないので、興味が湧いた方はぜひ AtCoder Heuristic Contest でググって色々な記事を読んでみるか、過去の類似形式のコンテストを漁ってみて雰囲気を掴んでください。

問題

町に鉄道を引いて儲けを最大化するシミュレーションゲームの解法を考える問題です。

詳細はコンテストの問題ページを確認してください。

$N\times N$ のグリッドがあり、ここに線路と駅を作っていきます ( $N=50$ )。
グリッド上に家と職場のペアが $M$ 組存在します ( $M\in[50,1600]$ )。家と職場は、一定のルールのもとランダムに設置されます。同じ場所に複数の家や職場が設置されることもあります。
住人はマンハッタン距離で 2 以内にある駅にアクセスでき、地面を歩いて乗り換えをすることなく家と職場を往復できるとき、そのペアの住人は鉄道を利用します。
1 ターンに一度線路または駅を建設でき、 $T$ ターン後に持っている資金がスコアになります ( $T=800$ )。
各ターンの終了時に、鉄道を利用した住人からの収入が得られます。ここで、収入は鉄道の長さや駅の数ではなく、条件を満たした各ペアについて、その家と職場のマンハッタン距離の総和で求められます。
線路を 1 マス設置するには 100、駅を 1 つ設置するには 5000 の資金を消費します
マス内で 90 度曲がる線路を設置することができますが、線路を分岐させることはできません。
設置した線路は後から駅に上書きできます。駅を線路にしたり、線路を別の向きの線路で上書きしたりすることはできません。
線路は 2 方向にしか接続しませんが、駅は 4 方向に接続できます。つまり駅を介して路線を分岐させることができます。
初期資金は 11000 から 20000 の間で与えられます。ただし、どんなに資金が少なくても、少なくとも一つのペアを鉄道で接続させられることは保証されています。

結構複雑なルールですが、基本的には直感的に正しいと思えることが起こります。住人は路線の乗り換えをしない点には注意が必要です。

考察

駅だけでなく線路も自由に設置できるため自由度が高く、最適な戦略を考えるのが難しい問題です。

こういう問題では、「本質を損なわないようにしつつも、できるだけ問題を単純化して考える」ことが重要になります。

特に長期コンテストでは時間に余裕があるので、難しいなと思ったらひとまず解の自由度を制限した状態で取り組むことを考えるとよいです。

要素を削って単純にする

まず、全ての駅は互いに線路で繋がっているものとします。住人は乗り換えができないので、分断された複数の路線を作ることはあまりメリットがありません。

すごく離れた場所に繋ぎやすい家と職場のペアがある場合などでは最適にならない可能性がありますが、今回ペアの個数 $M$ が最低でも 50 はあるため、そこまで問題にならないと予想できます。

もう一つ、線路の接続は最短距離に限ることにします。今回は距離空間がマンハッタン距離なので、ユークリッド距離とは違い最短距離での接続でも接続方法にはそれなりの自由度があります。この制約によって、駅間の線路を引く方法が大きく制限され、とても扱いやすくなります。

序盤が重要

このゲームでは「収入をもとに次の駅を設置し、新たな収入を得て次の駅を設置し、さらに収入を得る……」というループを繰り返すので、序盤の改善は終盤になって加速度的に効いてきます。

大方針 1: ビームサーチ

序盤の選択が重要で、ターン制で展開していくゲームとなると、最初に候補に挙がるのがビームサーチになります。

ここでは、駅を設置して線路を最短距離で繋げるまでを 1 手とします。

線路は実際に引かずに接続方向だけ決めておく

このとき、線路をグリッド上に実際に引く必要はなく、駅に対する接続方向だけを決めておけばほとんどの場合で十分（＝後から矛盾しないように線路を引くことができる）になります。

さらに、接続方向すら一通りに決めておく必要はなく、最短距離で接続できる方向の候補全てを 4 ビットの変数で重ね合わせ的に持っておき、必要に応じて状態を確定させることで自由度を上げることができます。

例えば上の画像では、13 番と 4 番の接続は横一直線のため左右の出口を使う以外に最短距離で接続する方法がありませんが、9 番と 4 番のように斜めに接続する場合、9 番は右と下の出口を、4 番は左と上の出口を使うことができます。

ただし、4 番の左側の出口はより優先度の高い（＝一通りしかない）13 番への接続に使用されてしまっているので、9 番への接続に使う出口は上側で確定します。

実際の実装では、それぞれの駅について他の駅との接続を構造体で接続方向付きで持っておき、ある接続の方向の可能性が更新されたとき、関係のある別の接続へ状況を伝播させ、収束するまで繰り返し更新を行います。

自分の試した限りでは、新たな「少なくとも局所的に可能な」接続を追加させて伝播させたことによる接続の矛盾^[1]は発生しませんでした。

そのため、このように接続方向の可能性を順次制限しながらビームサーチを進めていくことができます。

実装は厳しい

ちなみにここの処理は大変にややこしく、終始バグが絶えませんでした。

例えば上のような接続のペアでは、15 番の出口の選択によっては 41 番の出口の候補も絞り込まれます。

15 番の上側の出口を採用したとしましょう。この場合は特に問題は起こりません。しかし、右側の出口を採用すると……

このように接続が一直線になってしまうため、41 番の左側の出口は使えなくなります。

とまあこんな感じで考えるべきコーナーケースが大量に発生し、とにかく正しく動かすだけでも一苦労でした。

未確定の線路に後から設置した駅をねじ込む

線路の引き方を確定させないメリットがここにあります。グリッド上では「最短経路」は多数存在するので、後から都合の良い経路を使ったことにすることができます。

実は、先程から表示していた青い四角形は、「最短距離を保ったまま通ることができるマスの範囲」を表しています。この青い四角形の範囲内なら、他の駅を割り込ませることができます。

こんな風に。ここでも接続方向は重要なので、きちんと正しく管理するようにします。実装は大変です。

線路を交差させない

新しく駅を追加したとき、既存の線路と交差しないかどうかのチェックが必要です。これは、駅の整数座標を端点とする線分の交差判定を用いて行いました。ただし、この判定も非常にややこしくなります。

まず、同じ駅から伸びている複数の線路は交差すると判定すべきではありません。そのため、端点が一致しているケースは交差なしとして除外します。

では内点での交差判定のみでいいかというとそうではなく、片方の線分の端点がもう片方の線分の内部に乗っている場合は交差ありと判定する必要があります。

最終的に判定コードは以下のようになりました。

int orientation(ivec2 a, ivec2 b, ivec2 c) {
    int val = (b.i - a.i) * (c.j - b.j) - (b.j - a.j) * (c.i - b.i);
    return (val > 0) - (val < 0);
}

bool inSegment(ivec2 p, ivec2 a, ivec2 b) {
    ivec2 mins = a.min(b);
    ivec2 maxs = a.max(b);
    return p.i > mins.i && p.i < maxs.i && p.j > mins.j && p.j < maxs.j;
}

bool segmentsIntersect(ivec2 a1, ivec2 b1, ivec2 a2, ivec2 b2) {
    // check by AABB first
    ivec2 mins1 = a1.min(b1);
    ivec2 maxs1 = a1.max(b1);
    ivec2 mins2 = a2.min(b2);
    ivec2 maxs2 = a2.max(b2);
    if (maxs1.i < mins2.i || maxs2.i < mins1.i || maxs1.j < mins2.j || maxs2.j < mins1.j)
        return false;
    if (a1 == a2 || a1 == b2 || b1 == a2 || b1 == b2)
        return false;
    // actual check
    int o1 = orientation(a1, b1, a2);
    int o2 = orientation(a1, b1, b2);
    int o3 = orientation(a2, b2, a1);
    int o4 = orientation(a2, b2, b1);
    if (o1 != o2 && o3 != o4)
        return true;
    if (o1 == 0 && inSegment(a2, a1, b1))
        return true;
    if (o2 == 0 && inSegment(b2, a1, b1))
        return true;
    if (o3 == 0 && inSegment(a1, a2, b2))
        return true;
    if (o4 == 0 && inSegment(b1, a2, b2))
        return true;
    return false;
}

ivec2 は 2 次元の整数ベクトルの構造体で、いい感じに演算が定義されています。

接続方向を確定させる

ビームサーチの完了後、それぞれの駅で使う出口を確定させます。

各接続に対して、使える可能性のある出口は高々二つなので、確定していない接続があったら、出口をどちらかランダムに選びます。

確定前

確定後

残念ながら、このとき矛盾が発生することがあるので、複数回試します。運が良ければ一度失敗しても上手くいくことがありますが、本質的に接続が上手くいかない場合もあります。

その場合はビームサーチの解を使うことができないので、矛盾が発生しない地点まで巻き戻らなければなりません。そのため、ビームサーチではベストな解だけでなく、複数の予備の候補を保持しておく必要があります。

評価関数

ゲーム終了時の資金を予測し、評価関数としました。ナイーブには $T=800$ ターンまで進めて資金を求めればいいですが、このゲームでは時間経過に伴い指数的に資金が増加していくので、最後の駅を設置したターンから終了ターンまでの間に発生する複利を組み込んでやります。割合は $M$ や $K$ に応じて調整します。

また、家か職場の片側だけカバーされているペアについて、もう片方をカバーした際に得られる収入の一部を上乗せして資金を計算します。

さらに、最後の駅を設置したターンから最終ターンまでを単純に早回しするのではなく、「もう一つ駅を設置するために必要なターン数」を考慮した計算を行います。ビームサーチの評価関数は「先読みが上手くできるほど強い」ので、一手先が定数時間で計算できる場合はそこまで読んでしまうのが良いです。

ただし、最初に設置する 2 つの駅については、重要度が高く、かつ同じ評価関数を使うとあまり上手く行かなかったため、また別の評価関数を用いて有望なペアを絞り込み、その中からビームサーチを開始しています。

高速化

このビームサーチでは、頑張ると各候補に対する評価値の上界を $O(1)$ で求めることができます。

各候補の厳密な評価値を求めるために必要な情報は次の二つです。

駅を接続させるために追加で必要な線路の個数
駅を設置した際に増える収入（と片割れの収入）

ここで、1. については、それぞれのマス目に対して最も近い駅への距離を格納しておくことで、配列を参照するだけで上界が求まります。この配列は、新たに駅を設置した際に BFS で更新します。

ただし、最初のうちは広い範囲の値を更新しなければならない^[2]一方で、距離を判定すべき駅の個数は少なく、差分計算のコストが割に合いません。そのため、適当な個数が溜まった段階で最初にまとめて計算をし、そこから追加された駅に限って差分計算を行います。逆に後半は更新すべき面積が小さくなるため、非常に高速になります。

また、2. についても同様に、各マス目に対する収入の増分を計算して格納しておきます。こちらも新しく駅を設置した際に増加的に計算できます。ある場所（家 or 職場）が新たにカバーされると、もう片方のペアの周辺の地価が上昇するイメージです。

スコアの上界を使って枝刈りを行う

さて、各候補のスコアの上界が分かれば、一旦それらを降順にソートすることで暫定的なランキングを作ることができます。

このランキングの上位から、実際に厳密な評価値を計算していきます。ビームサーチの幅を $W$ とすると、上位 $W$ 個を評価した時点で、次の候補が実際に生き残るために必要なスコアの下界が計算できます。

このスコアの下界は新たな候補が採用されるたびに上方修正されていきます。そして、スコアの上界がこの下界を下回ったときに、それ以降の候補を全て切り捨てることができます。

この枝刈りにより、候補の大部分の厳密なスコアを計算せずに済みます。また、解の実行可能性を確認するのも、この厳密なスコア評価のタイミングで構いません。

序盤のビームを太くする

後ほど触れるように、ビームサーチで得た解はその後焼きなます際に、最初に設置した駅ほど焼き辛くなります。そのため、最初の方の解は特に慎重に決定する必要があります。

自分の解法では、ビームの幅を序盤ほど太くすることでこの対応を行いました。

また、一番最初に接続する 2 つの駅については、評価関数があまり上手く働かなかったため、別の方法で選択した有望なペア^[3]のうち上位 500 個を始点にしています。

大方針 2: 焼きなまし

最初にビームサーチが候補に挙がると書きましたが、実はこの問題は焼くこともできます。

解の局所的な変更が全体を破壊しない

ターン制のゲームでは、基本的に将来の選択肢は過去の自分の選択に依存するので、ある時点の選択を変更してしまうとそれ以降の解が無効になったり、激しく悪化してしまったりということが多々あります。

しかし、今回の問題では、過去の駅の置き場所が変わったところで、道さえ塞がれていなければ、資金が貯まるまで待てば将来の行動は有効なままです。

というわけで、ビームサーチで得た解を初期解としてさらに焼きなますことを考えます。

何を焼きなますか

最初に設置する駅を 0 番とし、0 番の駅を根とした木を考え、これを焼くことにします。

こうすることで、木に変更が入ったとき、部分木に対する再計算のみで新しいスコアが求まります。

例えば次のような木があるとします。

[0] <-- [2] <-- [1] <-- [3]

このとき実際に行われる行動は、

0 番の駅を設置する
1 番から 2 番への線路を伸ばす
2 番から 0 番への線路を伸ばす
1 番の駅を設置する
2 番の駅を設置する
3 番から 1 番への線路を伸ばす
3 番の駅を設置する

のようになります。

それぞれの頂点に対して、その頂点以下の部分木に含まれる最小の頂点の番号がこの問題において重要になってきます。これをカッコで表すことにすると、先程の木はこうなります。

[0(0)] <-- [2(1)] <-- [1(1)] <-- [3(3)]

頂点 2 は、カッコ内の数字が 2 よりも小さいです。このことは、2 番の駅を設置するときには、既に周辺の線路が整備されており、新たに線路を引く必要がないことを意味します。

また、自身の数字がカッコ内の数字と一致する場合は、親を辿っていき、自身より小さなカッコ内の数字を見つけるまで線路を建設します。

例えば、1 番の駅の場合は、頂点 2 のカッコ内の数字 (1) は 1 未満ではないので再び親を辿り、頂点 0 に到達したときにカッコ内の数字 (0) を見て線路の建設を終了します。

この判定方法は、木に枝分かれがある場合にも有効です。

禁止された状態

全ての木が解として有効になるわけではありません。例えば以下のような木を考えます。

[0(0)] <--- [3(1)] <--- [2(2)]
              ^
              |
            [1(1)]

この木は解として無効です。なぜかというと、3 番目の駅を設置する前に頂点 3 において線路の分岐が生じてしまうからです。T 字路の線路は設置できなかったことを思い出してください。

このような状態が生じていないかどうかもカッコ内の数字を使って判定することができます。

「ある頂点が、自身の番号より小さいカッコ内の数字を持つ子を 2 つ以上持つ」ときにこのような分岐が生じます。実際、頂点 3 は 2(2) と 1(1) を子に持ちます。

カッコ内の数字を逐次更新するようにすれば、異常な状態への遷移を高速に弾くことができます。

状態遷移

以下のような状態遷移を用いました。

頂点の swap

2 つの頂点の番号を swap します。操作の単純さに比べ、頂点の繋ぎ直しが非常に面倒です……

頂点の移動

頂点を一つ選び、ランダムな方向に少しだけ動かします。線分の交差には注意する必要がありますが、交差判定は遷移が受理されるまで遅延できます。

親の付け替え

頂点を一つ選び、親を近くにあるランダムな頂点に置き換えます。繋ぎ直しは簡単ですが、親として自身より高い位置にあるものを選ぶとループが発生する可能性があるので注意が必要です。辺の交差にも注意が必要です。

頂点の追加

新たな頂点を、既存のどれかの頂点を親としてその近くに追加します。頂点の番号もランダムに選び、それ以降の番号を一つずつずらします。スコアの差分計算が大変ややこしいです。

頂点の挿入

既存の辺の途中のランダムな位置の近くに、新たな頂点を挿入します。頂点の番号もランダムに選び、それ以降の番号を一つずつずらします。スコアの差分計算が大変ややこしいです。

頂点の削除

ランダムな頂点を削除します。削除の結果、親の次数が増えることがあるので注意が必要です。

貪欲改善

ある頂点がある辺に対し挿入可能な位置に存在する場合、それらの頂点の設置順序に応じた繋ぎ直しをします。スコアが悪化することがないタイプの遷移です。

以上全ての遷移で、スコアを高速に差分計算します。 $M$ が大きい場合はカバーされたかどうかの判定も律速になるので、それぞれの家/職場がどの番号の駅にカバーされたかを同時に差分計算することで、ある駅を設置した際の収入（および片割れの収入）の変化量を定数時間で求めます。

また、遷移の受理率を増加させるため、頂点を swap する際は近い番号の頂点を高い確率で選ぶようにしました。

さらに、番号が小さい頂点は差分計算の量が多い＋遷移が失敗する確率が高いため、あまり選ばれないようにしています。

最終的に数百万程度の反復が回っていたと思います。

スコアの差分計算

スコアの差分計算方法の概要を説明します。

まず、最終的なスコアは

各駅を設置するために伸ばす必要のある線路の数
各駅を設置した際に増加する収入

が分かれば、駅の数を $S$ として $O(S)$ で計算できます。

ここで、駅を設置した際に伸ばす線路の数は、各頂点から親を辿ってカッコ内の数（部分木の最小頂点番号）を確認することで平均 $O(1)$ で計算できます^[4]。

各駅を設置した際に増加する収入については、以下のように計算します。

まず、全ての家と職場について、「その場所をカバーしている駅の集合」を保持しておきます。すると、あるペアから収入が入るようになるターン数は、駅の集合の最小値の最大値で求まります。

例えば、あるペアの家が駅 $\{4, 8, 20\}$ で、職場が $\{8, 12\}$ でカバーされているとします。このとき両者がカバーされるターンは、 $\max\{\min\{4, 8, 20\},\min\{8, 12\}\}=8$ 番目の駅が設置されたターンになります。

各駅に対する収入の増加を配列で管理しておき、上記の値が変わるたびに配列の値を足し引きして整合性を保っておくことで、スコア計算中は収入の変化を $O(1)$ で参照できます。

また、木が部分的に変更された場合は、変更されるまでの値は再利用できるので、結果を配列に格納しておくことで変更があった場所からの再計算で済みます。

細かい工夫点

一定期間ベストが更新されなかったときにベストに巻き戻す

よくあるやつです。

今回は多少焼きにくい問題であるということもあり、潜ったまま一生浮上してこないということがよくあるので、適当な回数反復を回してもベストが更新されない場合は現在のベストからやり直します。

このとき温度についてはいじらない方がスコアが伸びました。

木の根を入れ替える

0 番と 1 番の駅はどちらを先に設置してもスコアに影響がなく、0 番の駅は親が存在しないため付け替えなどの遷移を行うことができません。そのため、定期的に 0 と 1 を入れ替えることで木の根元に対しても変化する可能性を与えます。

……が、これが実際どの程度有効だったのかはよく分かっていません^[5]。もともと根に近い部分は非常に焼きにくいため、ほとんど効果はなかったかもしれません。あったとしても $M$ の非常に小さいケースに限られると思います。

定期的に実行可能性を保証する

ビームサーチパートでも触れた通り、駅の出口を割り当てることができても、重ね合わせの状態を潰す段階で失敗する可能性が出てきます。

また、重ね合わせを確定して出口を一つずつ割り当てられても、何やかんやあって最短距離で線路が引けないこともあります。

とにかく幾何的な要素が絡むことで把握しきれないほど多様なコーナーケースが発生するため、解は常に失敗する可能性があるものとして扱う必要があります。

そのため、焼きなましでもビームサーチと同じようにベストな解をスタックしておき、一定時間（＝全体の 10 %）経過するたびにスタックの一番上から実際に解を構成することで実行可能性を確認していきます。

ここで実行不可能だった解は捨てられ、ベスト記録が実行可能な地点まで巻き戻されます。

この仕組みによって、陽に線路を持たないことで遷移を高速化しつつもロバスト性を確保することができました。

ハイパーパラメータ調整

焼きなましの進捗と $M$ の値に応じて、各近傍を選択する確率を調整します。

ハイパーパラメータとして

焼きなまし開始地点、 $M=50$
焼きなまし終了地点、 $M=50$
焼きなまし開始地点、 $M=1600$
焼きなまし終了地点、 $M=1600$

の 4 点での重みを遷移ごとに持っておき、バイリニア補間して現在の重みを決定します。

ハイパラ調整は最終日に Optuna に丸投げしました。

最終結果

最終日にプレテスト（50 ケースで暫定順位を出す）で nikaj に抜かれてしまったのですが、システムテスト（2000 ケースで最終順位を出す）で微妙に差がついて 1 位になりました！

順位表

延長戦

コンテスト終了後、実は大きな改善を一つ見逃していたことが発覚します。

詳細順位表を見ると $M$ が大きいケースで Rafbill や Jirotech に負けていることが分かるのですが、これは解の最終出力時に「先回りして線路を設置する処理」を入れているかどうかが非常に大きかったようです。

例えば収入が 1000 程度ある状況で、線路を引いた後に駅を設置するために資金が 5000 溜まるまでに 5 ターン待たなければならないとします。

このとき、5 ターン待って駅を設置するよりは、次の駅のための線路を先に引いてしまった方が最終的に得をする可能性が非常に高いです。線路の値段は駅の 1/50 であるため、資金が貯まるまで待っているより収入を 100 減らしてでも次の線路を設置してしまう方が時間を効率的に使えます^[6]。

収入が一定以上になったときに線路を先置きするものとして、解の出力前に閾値を全探索するようにしたところ、圧倒的なスコアが出るようになりました。

延長戦に線路先置きを実装したバージョンを投げておきました。49.8B が出ていて草です pic.twitter.com/M2QksBGabt

— さはら (@shr_pc) February 26, 2025

これを本番中に思い付かなかったのは大いに反省しないといけないですね……

延長戦その後

その後延長戦では一度抜かれてしまった（！）のですが、焼きなましとビームサーチの最中にも線路の先置きを近似的に評価することでさらに 1.1% ほどスコアが伸び、1 位に復帰することができました。

線路の先置きを厳密に評価するためには「最終的に必要な線路の個数」が分かっている必要があり、線路を伸ばした影響で過去の最適な行動が変わってしまうことがあるため、スコアの差分計算が上手くできなくなってしまいます。

そこで、収入が閾値を超えた段階で、本当に必要かどうかに関わらず常に線路を置いたことにします。こうすることで、後から路線が短くなって先置きした線路が不要になっても、過去の行動を修正する必要はなくなります。また、焼きなましの近傍に「線路を先置きする収入の閾値の変更」を加えます（重みは 0.01 で固定にしました）。

ビームサーチ中は閾値を変更できないため、 $M$ に応じて 110 ～ 600 の範囲で決め打ちしたものを用いました。また、評価関数では先置きした線路の個数だけ複利にかかるターン数を上乗せしています。

副作用として不要な先置きのため実際よりもスコアが低く出ることがありますが、近似精度としては十分良いようで、目立った問題は起こりませんでした。実際のところ、ほとんどのケースで不要な先置きは発生しておらず、最終的なスコアと一致していました。

現在の延長戦順位表はここから見ることができます。

設定の「全ユーザーを表示」にチェックを入れないと自分以外の結果が見えないのて注意してください！（これデフォルトで ON になっていてほしいですね）

おわりに

今回優勝したことで今年の目標だったレート 3200 到達を達成することができました！　世界ランクも瞬間的ですが 3 位になっています。

今年からレートの時間減衰が導入されるようになったので、油断しているとまたすぐ下がってしまいますが、頑張ってこの値をキープしていきたいところです。

すなわち、どの方向の出口も利用できなくなること ↩︎
マンハッタン距離におけるその駅のボロノイ領域の面積に比例するコストがかかります。 ↩︎
収入の増分と半分満たされたペアによる収入、線路の長さによるスコアの減衰を考慮した評価値を使っています ↩︎
親を辿る回数が全体で $S$ のため ↩︎
他の変更と併せて入れたので、効果を検証できていません ↩︎
ちなみに、駅と線路を置いた個数で DP を回すことでも厳密解が求まります。 ↩︎