延長戦一位ではなくなりました

{+x%}という表記は延長戦一位の提出から該当部分の工夫を除いたときに比べスコアがx%上昇したことを表します。

大まかな方針

---

焼きなまし法を用いて探索しました。
焼きなましでは、駅の位置と設置順のみを探索します。駅同士の接続関係は貪欲で評価毎に毎回決定し、シミュレーションして評価します。
レールの配置などの具体的な経路は、焼きなましでは一切考慮せず、最後に解を出力するときに決定します。

線路先置きについて

---

レールの設置には 100 資金が必要なのに対し、駅の設置には 5,000 資金が必要です。 つまり、駅の設置は資金が貯まるまでの待機時間がネックなのに対し、レールは1ターンに1つしか設置できないことがネックとなる時間帯があります。 そこで、駅設置の待機時間を利用し、将来的に設置予定の線路を先行して敷くことで、全体の建設に必要なターン数の削減が期待できます。
具体的には、incomeがある閾値を超えたら待機せずに今後置く予定の線路を先に置くように実装しました。
コンテスト終了後に線路先置きを実装したところ、スコアが約3%向上し、順位も4位から1位相当まで上昇しました。

ビームサーチ(0.2sec)

---

• ビーム幅200
  
  
• 6個の駅の配置をビームサーチで探索
  
  
• 最初の2駅は全探索
  
  
• 評価
  • 現在のmoney、incomeから総収入が60,000を超えるまでに必要なターン数
    
    
• 重複除去
  • 駅により被覆されている家や職場の集合
    
    
• 家と職場の両方が駅により被覆された人の集合が異なる配置を集めて、その中から評価の良い上位100個を焼きなましの近傍候補として列挙

焼きなまし(2.75sec)

---

• 探索する状態

  • 線路先置きを始めるincomeの閾値
  • 設置する駅の位置と順番
    
    

• 評価

  • 具体的な経路は決めずに、駅の接続関係のみを貪欲に決定し、駅同士は最短距離で結べると仮定して、必要なレール数を見積もってシミュレーションし評価
    • 駅の接続はマンハッタン距離の総和を変えない挿入を優先し、それが不可能な場合は、接続可能な駅の中で最も近い駅に接続
    • 最後の経路の構築に失敗しないよう、最短経路で結べなくなる原因の部分構造をいくつか禁じて駅を接続
      • Level1
        • 5つ以上の駅につながる
        • $(a,b)$ に駅が存在するとき、その駅につながる4つの駅が $a\leq x$ の領域に集中している $($$a\geq x$ , $b\leq y$ , $b\geq y$も同様$)$
        • $(a,b)$ に駅が存在するとき、その駅につながる3つ以上の駅が $a\leq x$ かつ $b\leq y$ の領域に集中している
          $($$a\geq x$ かつ $b\leq y$ , $a\geq x$ かつ $b\geq y$ , $a\leq x$ かつ $b\geq y$ も同様$)$
      • Level2
        • Level1の判定に、軸平行な経路であるためにレールが敷かれることが確定しているマスに隣接するケースも考慮
        • 線分の交差
      • Level1の判定は高速に行えるが、Level2はそうではないので、Level2まで考慮した貪欲は最後の山登りでしか行わない
        
        

• 4段階の焼きなまし

  1. Level1の部分構造を禁じて400ターン時点でのincome最大化の焼きなまし (0.15sec) {+0.1%}
  2. Level1の部分構造を禁じて生スコアの焼きなまし (2.5sec)
  3. Level1の部分構造を禁じて生スコアの山登り (0.05sec) {+0.07%}
  4. Level1、Level2の部分構造を禁じて生スコアの山登り (0.05sec)
     
     

• 近傍（段階1～段階4で共通）(カッコ内の数字は各近傍を試す確率)

  1. ある駅の設置順を現在の順序から$±10$のランダムな範囲に移動させる (0.33)
  2. ある駅の位置を現在位置からマンハッタン距離が2以内のランダムな位置に移動させる (0.33)
  3. 駅を削除 (0.15)
  4. 家と職場のどちらかが被覆されていない人をランダムに選択し、それらを被覆できる駅をランダムに挿入 (0.15)
  5. ある駅と、それに対して設置順が$±10$のランダムな駅の設置順を交換 (0.04) {+0.1%}
  6. 線路の先置きを開始する閾値を、現在の閾値から$±30$の範囲でランダムに変更 (0.02) {+0.3%}
  7. ビームサーチで列挙した駅の設置順から1つをランダムに選択し、その列 $a$ の先頭から、 $2 ～ len(a)$ のランダムな長さの連続部分列を現在の解の先頭に挿入する (0.02) {+1.3%}
  8. 家と職場がどちらも駅で被覆されてない人をランダムに選択し、その家と職場を被覆できる2つの駅をランダムに挿入 (0.005) {+0.1%}
     
     

• 高速化

  • $0～n$ の整数の集合に対し insert、remove、clear、fill、random_choice などが $O(1)$ でできるデータ構造(この提出の2707~2749行目)を用いて、家と職場の片方だけ被覆されてる人やどちらもも被覆されていない人を管理 {+0.5%}

  • 各駅に対してその駅より前に設置される駅の中からマンハッタン距離が一番近い駅を差分更新し、貪欲をしたときにマンハッタン距離が一番近い駅と繋げられなかった場合に限り、繋げられる駅の中から一番近い駅を線形探索 {+2.4%}

  • 駅同士をつなぐ線分が軸平行の場合、マンハッタン距離の総和を維持できる挿入領域が固定される。そのため、まず軸平行な線分上に挿入可能かを $O(1)$ で判定し、不可能なら他の線分を探索する {+1.6%}

  • Level1の9通りの部分構造の存在判定を、各領域に含まれる駅の数の計算をビット演算で並列化して高速化 {+0.05%}
    
    

• その他の工夫

  • 近傍3および4でランダムに人を選択する際、incomeの増分が大きい人優先的に選択する。{+0.2%}
    入力を受け取った後、家と職場のマンハッタン距離が降順になるよう各人に番号を割り振り、条件を満たす人を2回ランダムサンプリングして、そのうち番号が小さい方を近傍の対象とするように実装した

解の構築

---

• 上下左右の接続方向を決定
  • 接続されている駅の数が多い駅から順に決定
  • 距離の総和を保ちつつ、線分の交差が発生しないように接続
    
    
• $(a_i,b_i)$ と $(c_i,d_i)$ をつなげるとき $min(|a_i-c_i|,|b_i-d_i|)$ が小さい $i$ から順番にbfsで具体的な経路を決定
  
  
• 上下左右の割当に失敗したり、最短距離で結ぶことができなかった場合は、原因となった駅のうち一番最後に設置された駅を削除して再構築（ただし、再構築が発生するケースは約0.5%と稀である）
  
  
• 経路が確定したら、焼きなましで決定した線路先置きを開始するincomeの閾値を用いてシミュレーションを行い、行動を確定する

参考

---

実行時間が2倍になればスコアが+0.7%、10倍になれば+2.0%上昇するようです。