解法概要

始めに駅の位置，それらを繋ぐ全域木の形，辺に対応する線路の位置を決め打ち， 建設による集金額の増分が建設への投資額を回収する期間が一番短くなる建設を貪欲に選択していきました．
（十分なターン数があった場合の建設ターン数や総建設費用を小さく抑えられる点は良いものの， 前半の遠回りによる出遅れが痛い点， 折角扱いやすい形にしたにもかかわらず貪欲による選択に終わってしまった点で，筋が悪かったように思います．）

解法詳細

駅を頂点，線路を辺としたグラフを作り，グラフへの操作によって建設が進むようにしました．

駅の位置の決定

中心からの距離が遠い順にまだ駅を利用できない人を見ていき， その人が駅を利用できる周囲13マスについて，利用できる人の数が一番多い場所を選んでいきました．
既に利用できる駅がある人の価値は小さく（1/1000）しています．
駅数は50~230程度となっていました．
（駅を配置済みの人であっても駅の選択肢は多いほうが良いと思い小さな価値を与えていましたが， タイブレークにそれよりも大きな乱数を与えてしまっていたため，実際はほとんど意味を持っていませんでした．
また，コンテスト後にその乱数を外してみたものの，スコアはほとんど変わりませんでした．）

全域木の形の決定

まず，最初に繋ぐ2頂点（=駅）を選びます．
これは集金額が一番大きくなるものを選びました．
（等しい場合には中心からの距離の和が小さいものを選んでいます．）

次に，経由する頂点を選びます．
元の盤面に戻って考え，2次元グリッド上でDPを行い， 最短路のうち最も多くの駅を通るような経路上の頂点を選びました．

最後に，全域木を作ります．
最初に繋ぐ2頂点とその経路上の頂点については先に辺を張り，その後残った辺を張りました．
残った辺については，全頂点間について両端の方向全通り（駅の位置関係によって最大で2×2の4通り）の辺候補を用意し， 短い順に接続を試みていきました．
辺を張る際の実際の線路の位置については，

• 行と列とで目的地への差分が大きい方に進む．
• 目的地への差分が等しい場合はランダムに選択する．
• 進みたい方向が既に取られている場合は残った方向を選択する．
• そちらも取られている場合はその辺を張るのを諦める．

としました．
（差分が大きい方に進んでいるのはできるだけ経路の選択肢を減らさないようにしています．）
全域木を成せなかった場合には辺をすべて消して何度か繰り返し， それでも駄目な場合には最初に2頂点を繋ぐのをやめて同じことを繰り返しました．
（始めの辺候補を列挙する段階で試行ごとに異なる乱数によるタイブレークを加えています．）
試した限りこれで構成できないケースには遭遇していないようでしたが， それでも駄目だった場合には最初に選択した2駅間のみに線路を建設して終了としました．
（全域木の構築過程でも家や職場の情報を使いたい思いもあったのですが，距離情報のみで終わってしまいました．）

建設によって接続する2頂点の決定

投資回収期間を \( \max((建設期間)-1,(資金準備期間))+ \lceil (建設費用)/(集金額の増分) \rceil \) として，これが一番小さくなる2頂点の辺（・頂点）を建設していきました．
以下詳細です．

グラフの状態管理

グラフの頂点数を\(n\)として，\(3n-1\)頂点のDSU（Disjoin Set Union / Union-Find）を用いました．
頂点\(i\)に対応する\(s_i\)，頂点\(i\)の建設状況に対応する\(s_i'\)，\(ij\)間の辺に対応する\(e_{ij}\)を考え，

• 頂点\(i\)を建設する場合 : \(s_i\)と\(s_i'\)とを結ぶ．
• 頂点\(ij\)間の辺を建設する場合 : \(s_i'\)と\(e_{ij}\)とを結ぶ．\(s_j'\)と\(e_{ij}\)とを結ぶ．

としました．
実装上は\(s_i\)にDSUの頂点\(i\)を，\(s_i'\)にDSUの頂点\(i+n\)を， 辺\(i\)にDSUの頂点\(i+2n\)を対応させました．
（実際には誤って\(3n-2\)頂点を用意し，辺\(i\)を操作する場合\(i+2n-1\)を操作してしまっていました．
コンテスト終了後に修正したものの，スコアはほとんど変わりませんでした（!?）．）

相手となる頂点候補・連結成分内の家や職場の管理

サイズ\(3n-1\)のvector<set>を用いました．
初期状態は各頂点\(s_i\)に対応する駅の周囲にある家・職場を見て， 相手となる頂点候補や家・職場を\(s_i\)に対応する場所に入れました．
そして頂点や辺の建設を行うたびにDSUのリーダーへと情報をマージしていきました．
マージする過程で不必要となった情報（同一連結成分の相手・既に行き来のできる家と職場）は捨てていきました．
\(s_i\)の接続相手を考える際にはその頂点を建設することになるため， \(s_i\)と\(s_i'\)のリーダーとの両方の情報を見ます．

建設費用などの管理

全域木をオイラーツアーして，3つのBIT（Binary Indexed Tree / Fenwick tree）を用いました．
それぞれのBITについて，

• 距離用のBIT（\(dist\)）
  • 辺に対応．頂点間の距離を持つ．
  • 辺を建設 : 値を0に．
• 未建設マス用のBIT（\(unbuilt\)）
  • 頂点に対応．更地の場合に値1を持つ．
  • 頂点・辺を建設 : 値を0に．
• 余分に必要な駅用のBIT（\(obstacle\)）
  • 辺に対応．線路を駅に置き換える必要がある場所の情報を持つ．
  • 辺を建設 : その辺の値を0に．両端の頂点の周囲の未建設の辺に+1．（各頂点1回限り）
  • 頂点を建設 : 周囲の未建設の辺に-1．
  • （すでに建設されている線路を未建設線路から未建設線路へ1点で横切ろうとする場合2とカウントされてしまう．）

としました．
2頂点を選んだ時，

• 必要な駅数 : \(obstacle\)．両端に駅が未建設ならそれぞれで+1．
• 必要な線路数 : \(dist+unbuilt-(駅数)\)．両端に線路が建設されている場合はそれぞれで+1．

としました．
（建設済みの線路上の頂点を選んだ場合，建設済みの辺を経由して未建設の辺へ分岐する時は良いのですが， いきなり未建設の辺へ進む場合は駅数が余分にカウントされてしまいます．
そのため始めは\(obstacle\)はパスの両端を除いた辺について和をとって計算していたのですが， 最終的にはそのままパス上の和を利用する形になりました．
設置済みの線路から1辺で繋がる頂点を考えた時に計算が合わなくなったのか， 連結成分上の別の頂点から接続相手を考えた場合にカバーしてくれると思ったのか， 変更理由をあまり覚えていませんが， 後記のように一度見た連結成分は飛ばすことにしている上， 初手分岐なら2駅で良い所を3駅としてしまうのはかなり良くない話だったように思います．）

接続する2駅の選択

全頂点\(s_i\)について相手候補をすべて見ていき，投資回収期間が一番小さくなるものを選びました．
調べた\(s_i\)についてDSUのリーダーをメモしていき，調べていた場合は飛ばしました．
投資回収がターン制限を超える場合は終了しました．
（今の選択ではまだ接続出来ずとも，カバーしている人数は多い方が後々良いため計算に入れようとしたのですが， うまく組み込めずスコアが悪化し止めてしまいました．）