Skip to content

ALGO ARTISプログラミングコンテスト2023 (AtCoder Heuristic Contest 020)

問題概要

  • 放送局がN(=100)局、放送局間をつなぐ通信ケーブルがM(=100〜300)本、家がK(=2000〜5000)件ある
  • 各放送局は0〜5000の出力強度を設定可能で、通信ケーブルはONかOFFを選べる
  • 放送は、原点の放送局からONの通信ケーブルで連結な放送局から発信可能で、各放送局の出力強度の範囲にある家が受信可能
  • すべての家に放送を届けられるよう、できるだけ通信ケーブルを使う数を少なく、かつ、できるだけ出力強度を少なく設定せよ

時間

  • 4 時間

個人的メモ

  • いろいろ考える要素があって、バグらせずにきちんとコンテスト時間内にコードを書ききるのが難しい、と感じた問題
  • ざっくり「強度の組み合わせをいろいろ探索するために部分破壊再構築する」のが強かった模様

問題固有の性質

  • 施設配置、集合被覆、シュタイナー木の複合問題
  • 家の位置は正規分布的に生成されるので、ある程度はカタマリができている
  • スコアが「強度の2乗」になっているので、「大小」な組み合わせより「中中」な組み合わせの方が良い可能性がある
  • 基本は、すべての家をカバーする必要がある
    • カバーできないと 10^6 点以下だが、カバーできていると 10^6 点以上になる
    • 300M点以上なら平均全点カバーできている
    • コストが0なら3.3G点ぐらいだけど、実際どのぐらいが理論値になるかは見積もるのが難しい？

方針

  • 使う放送局を決めると、最小コストは最小シュタイナー木の問題になる
  • 大雑把には、以下の方針が強かった模様
    • 強度を状態にして探索＋使う放送局をつなぐ
    • 使う放送局を探索＋強度を乱択greedy(家を適当な順番に最小コストでカバー)
  • 強度の組み合わせの探索の方が重要度が高かったかも
  • また、ポイントとしては、「時間内でバグなく実装しきれる」必要があるので、実装時間も考慮して方針選択するほうが良かったかも

最小シュタイナー木

  • 無向グラフにおいて、ターミナル(頂点の部分集合)をすべて連結にする木、のこと
    • AHC018でも出ていた
  • 厳密解は求めるのが難しいため、基本的には近似的なもので代用

厳密解

primヒューリスティック

MST＋連結判定

  • 「使う放送局」集合を考えて、使う放送局だけでMSTしてルート放送局とすべて連結ならvalid、とすると強度の探索と一緒に探索できる
  • MSTはprim法かkruskal法で求めればよい

MSTから不要葉ノードを削る

  • 自分はAHC018でも、kruskal法してから不要リーフノードを削る方法を取っていた
  • ただ、今回はルート放送局は必ず含むようにしないといけなかったりする必要があった
    • ルート放送局がリーフになって非連結でスコアが0点近くになってしまった

強度の探索

  • 強度を増減させるのに、適当に値を変化させるだけだと、無駄な探索が多い
    • 「カバーできている家の集合が変わらない」という意味のない近傍移動が発生してしまう
    • ぎりぎり家をカバーするような強度のところだけ探索したほうが効率的
  • 探索空間がなめらかではないので、部分破壊再構築系の近傍が良さそうで、強度を少しずつ調整系は、多点スタートや何回か実行か、高速化で相当回数探索できないと厳しいかも
  • 基本、すべての家がカバーできている状態を保って探索
    • すべての家をカバーしない(invalidな)状態を許容するともっと良くなる可能性はある
  • 更新がしばらくなければベスト状態に戻す、なども有効そう

近傍

  • 部分破壊再構築近傍
  • 少しずつ調整系
    • ある放送局について強度を増減
      • ただし、カバーされないような家ができないようにするのと、その判定を放送局に近い順にソートしておくや、各家のカバーされている放送局数などを持って高速計算(数百万〜一千万回ぐらい回す)
    • ある放送局の強度をカバーする家が1つずつ増えるように増加させて、近くの放送局はそれによって強度を減らす
    • 辺で連結している放送局を調整
    • ある放送局でカバーしている中で一番遠い家について他の放送局でカバー

近似スコアで高速化

その他

2つの最適化要素のどちらが重要か?

  • 今回、「強度」と「ケーブル」の2つの最適化要素があった
  • うまく問題が調整されているため、どちらが重要という感じでもなかった
    • また、基本、問題によって変わりうるので、見極めが大切
    • これらをまとめて扱うか、片方を探索してもう片方をgreedy、など扱い方もいろいろ考えられる

強度・距離の2乗(小数を介さず整数)で判定

  • 家がカバーできているかの判定は、強度・距離の2乗を使って整数で計算
    • 強度と距離がそのままだと小数計算を挟むため誤差がでうる

500M超え

Prize-collecting Steiner Tree Problem

解説

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