Skip to content

RECRUIT 日本橋ハーフマラソン 2025冬(AHC043)

問題概要

  • 50*50の区画からなるグリッドに対して、M人の家と職場の区画の情報が与えられる
  • 各区画は、最初は更地で、コストを払うことで線路か駅を設置することができ、駅から距離2以下の区画の家か職場がその駅を利用できる
    • 線路はコスト100だが、駅はコスト5000
    • 線路は、上下左右の最大2つの区画と接続することができる
      • 線路は、設置後にあとから駅にすることもできる
    • 駅は、上下左右の最大4つの区画と接続することができる
  • 各人は、家と職場が駅と線路を経由して到達可能なとき、鉄道を利用できる
  • 各ターンでは、線路か駅の設置、または、待機を行い、その後、家と職場がつながっている人について、その家と職場の距離が資金として集金できる
  • 最初に資金K持っているとき、T(=800)ターン後の資金を最大化せよ

時間

  • 240 時間

個人的メモ

問題固有の性質

  • 拡大再生産系
  • 駅の位置、線路の形状、設置順番をどうするかが問題
  • 最初の方では資金不足で貯まるまでターンを待つ可能性があるが、incomeや資金に余裕ができるとすぐに設置できるようになっていく
    • 前半と後半で問題の性質が異なる
  • 1ターンを無駄にすると、最終的なincome分を損することになる
    • その無駄がなくなると最後の1ターンが増えるため
  • 線路は「周囲区画の2つ」としか接続できないため、接続をどうするかが問題になる
    • 線路を交差したい場合、駅を増やせば繋げられるが、コストがかかるので、序盤などはできるだけ交差しないように設置したい

駅、線路の形状

  • 木構造(連結成分1つ)になるように駅を追加していく形、が強かった
  • 序盤などは木構造に限定しないほうがよいケースもあるかもしれないが、基本的には、連結成分が1つだと考えやすかったり、駅を追加したときにカバーされるところが多いのでincomeも増えやすいなどメリットが多い

駅の設置場所の候補

  • 家か職場を含むように設置してなければ意味がないので、そういう場所を考えると、Mが小さい場合は有効な候補地点は結構少なくなる

序盤の重要性

  • 最初の2駅の設置を考えた場合、incomeが10の場合とincomeが50のつなぎ方があるとき、前者だと次の駅設置コスト5000分がたまるまでに500ターンかかる一方、後者だと100ターンで済む
  • 所持金が増えるまでにかかるターンが多いほど、後半のincomeがバンバン増えるフェーズに使えるターンが減ってしまうため、できるだけ少ないターンで所持金を貯めることが重要になる
  • 上位でも、序盤のターンや最初の何個かの駅は、大きめの幅のビームサーチで求めるなどしている人が多かった模様
  • 評価関数は、「最終的な所持金」にしてしまうと、最初に遠い距離を繋いだほうが得られるincomeが大きい場合が多いのでそういうのが先に選ばれやすいが、最初の所持金(K)がある程度多い場合は、近くを繋いでも3つ目の駅がすぐに設置できてincomeがより速く増える、などの場合もありえるので、「あるしきい値以上の資金がたまるまでに必要なターン数」が少ないようなものを探すようにすると良いみたい

いつ設置を辞めるか？

  • ある解について、各ターンについて、そこで設置をやめた場合、「現在の所持金 + 残りのターン*現在のincome」で最終的な所持金を計算できるので、それが最大になるターンで設置をやめれば良い

線路と駅の設置順番、線路先置き

  • ある駅を既存の駅・線路に繋ぐ事を考えた場合、incomeが増加するのは駅と線路がどちらも設置終わったタイミングだが、線路と駅の設置コストが違うため、序盤の資金不足のときは、「駅の設置→線路の設置」より「線路の設置→駅の設置」のほうが待ちターンが少なくなる可能性がある
    • 「駅→線路」の順番だと、駅を設置するまで待つしかないが、「線路→駅」だと、線路の設置と同時に「現在のincome-100」分のincomeも得られる
  • さらに、「線路の設置(a)→駅の設置(b)→線路の設置©→駅の設置(d)」という場合に、bのコストが貯まるまで待つのではなく、上記と同様に先にcをやっておくと駅dまでのターンが減る可能性がある
  • 最適な設置順はDPで求められる

線路の経路

  • BFSで近くの駅や線路までの経路を求めればよいが、計算コストが大きい
  • 「追加する駅からの距離」ではなく「既存の駅・線路からの距離」を求めておくなどすれば、追加駅ごとに計算しなくて済むが、それでも結構重い

経路を限定する

  • 駅の所以外は交差しないので、複雑な形状を考える必要がない場合も多く、駅間は「x軸方向に移動→y軸方向に移動」「y軸方向に移動→x軸方向に移動」の経路だけに限定する、とかも考えられる
  • ただ、後から設置する駅の考慮が難しく、カバーできていない家や駅の近くを通ったほうが良いケースなどに差ができやすい

線路の設置を遅延させる

  • 2つの駅を繋ぐ線路の経路は、最短経路で繋ぐ場合でもかなり自由度がある
    • 経路によっては、後で設置する駅が経路上にあれば1ターンで設置できるので、うまく経路を選ぶメリットがある
  • 上位は、探索時には実際に線路を決めずに後から決める方法を取っていた模様
  • 長方形領域で扱う
    • 経路を1つに決めずに、経路に使える長方形領域で扱っておき、領域が重なる場合や後で設置する駅が領域内にできたらその長方形領域を更新するようにすると、経路決定を最後まで遅延させることができる
  • グラフで考える
    • 探索時には駅を頂点とした木(ただし、次数に制限や交差しないなど制約をいれる)を考え、実際の線路は後処理や別途厳密計算時に考える

線路の種類

  • 線路の種類は、その線路の周囲(4近傍、パスの前後)がどうなっているかで決まる
  • 線路のパスさえ保持されていれば種類がわかる
    • 毎回種類を求めなくても、後から求めることができる
    • 線路の位置が欲しい場合も種類まではいらないので、各区画1bitで保持するなどできる

あとから経路を繋ぎ変える

  • 駅に線路を繋げる場合に、前に設置した線路の向きによっては接続できなくなる/遠回りになってしまうケースができる
  • その場合、線路を繋ぎ変えることで、解消できる可能性がある

アプローチ

貪欲、ビームサーチ/chokudaiサーチ

  • 「新しい駅を既存の駅/線路に繋ぐ」を1手として、貪欲やビームサーチ/chokudaiサーチ
    • chokudaiサーチを考える場合、「設置済みの駅数」か「ターン」かが考えられる
  • 評価関数
    • シンプルなのは「追加incomeが一番多い地点」「最終所持金を計算して最大になる地点」などだが、設置までのある程度ターン数が必要なども踏まえると、最終ではなく「xターン後の最大所持金」などのほうがよいっぽい
    • 家と職場両方をカバーしないとincomeにならないが、駅を1つずつ追加する場合片方ずつカバーされていくので、片方だけをカバーしていることも評価関数に組み込むとよい
      • ただし、最初の方は直近の資金のほうが大事なので小さめにしておく
    • 後半の所持金やincomeに余裕がある場合は、設置にかかるターンのほうがボトルネックになるので、「1ターンあたり得られるincome増加分」が大きい地点を選ぶなど、切り替える
  • 重複排除
    • ある区画をカバーするような駅の設置の仕方は13通り(距離2以下)あり、最短で繋いだとしても何通りかの組み合わせがありえて似たような盤面が発生しやすい
    • 他の多様性の持たせ方として、評価値での「〜ターン後の最大所持金のもの」でベストのものだけを残す、なども

焼きなまし

  • 今回の場合、駅の位置や訪問順を変えた場合でも、待ちターン数などは変化するが、形状は全体に対して部分的にしか変化しないので、局所探索系を考えることもできる
    • ビームサーチの解の改善として使うなどもできる
  • 状態としては、「駅の位置・接続先とその順番」を持つ、など
    • 設置順ではなく木構造を持つ、なども
  • 資金に余裕があるタイミングの、順番の隣接swap操作は、その後の所持金しか変わらないので高速に評価できる

その他

カバー範囲が被らないように敷き詰める駅配置

  • 駅が隣接していたりでカバーしている範囲が被っているのは、無駄そうに見えるので、できるだけ被らずに敷き詰められるような駅配置がよいのでは？と考えられる
    • 敷き詰めるように駅を配置すると、隣接駅と卍のような感じでつなげることができ、グリッド的に考えることができる
  • しかし、駅や線路の接続が最短経路にならず、細かく無駄なターンが発生してしまって、良い解が得られない
    • 有効なのは駅が大量に設置できるケースだが、そういう場合は資金に余裕があって、きれいに設置するよりも、隣接や近くに駅を設置しまくったほうがよい場合が多い

お絵かき

解説

(50位まで&発言を見つけられた方のみ)