Skip to content

THIRD プログラミングコンテスト 2022 (AtCoder Heuristic Contest 017)

問題概要

  • 交差点と道路を表す無向平面グラフが与えられる
  • すべての道路について、D日の工事期間のうちどこか1日で工事を実施したい
    • 1日あたりK本の道路まで工事できる
    • 工事をしていない道路は通行可能
  • 「k日目の不満度」を異なる2頂点間の最短距離の増加分の期待値とし、「工事全体の不満度」は日の不満度の平均とする
  • 工事全体の不満度が最小になるように各道路の工事日を決めよ

時間

  • 200 時間

個人的メモ

  • スコア(不満度)の計算がとても重いので、それをどうするか、が難しい問題
  • 貪欲に初期解を作って、スコア計算を近似して辺の日を入れ替える山登り、が強く、上位では多かった模様

問題固有の性質

  • スコア計算がとても重い
  • 平面グラフ、重みはユークリッド距離(Euclidean distance)
  • 隣接する辺(最短パス上?)が同じ日に工事されるのがよい可能性がある

アプローチ

  • 今回は、スコア計算がそのままではめちゃくちゃ重いため、それを近似・別の評価関数、または、そもそも別の問題を解くなど対処する必要があった
  • ざっくり、「スコア計算を近似＋貪欲初期解＋山登り/焼きなまし」だった人が多い模様

スコア計算の近似

  • ある辺の日を入れ替えた場合、その入れ替え前後の日しか不満度は変化しないため、不満度の差はその2日分だけ再計算すれば求められる
  • 厳密スコア計算
    • 2日分について、辺を追加/削除した場合のグラフで、N頂点についてAll-Pair Shortest Path(APSP)を求める
    • 厳密に計算できるが、計算がかなり重い
  • 開始頂点を間引く
    • 何点か代表点(4〜11点ぐらいや、周上 or できるだけ離れた数十点とかが多そう?)を選んで、そこから他の頂点への最短距離・不満度を求めて、それをスコアの近似値として使う
      • 近くの頂点は、だいたい似たような感じになりやすいため、離れた頂点を選んだほうがよさそう
    • また、代表点数を増やすと近似精度が高まる(はず)
  • 変更する辺の周辺の頂点を選ぶ
    • 変更する辺の周辺が大きく影響を受けると考えて、その周辺の頂点(部分誘導グラフ)だけ考えて計算し、近似値とする
    • (自分もこれでやったけど、結構頂点数や選び方で計算コストや近似精度が変わる印象)
  • 各頂点のいくつかのパス(最短路?)に注目
  • 変更する辺から離れた2点間最短距離の差分を見る
  • 変更する辺の両端頂点から他の頂点への最短距離を見る
  • その他
    • 近似解は、頂点数などを増やすことで近似精度が高められる場合、最初のうちは荒く評価、最後の方は正確めに評価、など
    • 加えて、評価値として、各日での工事数が等しくなるようにするのを追加する、など

最短経路再計算の高速化

  • 制限時間内に山を登り切るのが難しいため、さらに高速化する必要がある
  • 代表点を決めて計算する方法の場合、辺を追加/削除しても大体の辺には影響がないので、変更の影響を受けるところだけ計算することで高速化できる
  • 最短経路木で部分木のみ計算
    • 変更があった辺の部分グラフ付近だけを再計算
  • 最短経路差分を辺の重みにしてBFS
    • 最短経路のところは0、そうでないところはその増加分のようなグラフを作る
      • (ポテンシャル?01BFSっぽく?SPFAではない?要確認)
  • ランダムな2点間の最短距離はA*を使うのも有効?

初期解(貪欲解)

  • (今回はイテレーション数が少ないのもあるので、よい状態/初期解からスタートするのも重要そう)
  • 各日について全頂点が連結になるようにする
    • スコアは無視して、適当に日を変えて連結になるようにする
  • 各辺について、スコアやなんらかの評価値が最大になる日を貪欲に割り当てる
  • 辺の選び方は、(貪欲に決めていく場合?は)ランダムに選ぶよりも、なんらか順番に選んだ方が良かった模様
    • 中心や端からBFSなど連続的に選ぶ
    • なんらかの評価順
    • より多くの最短経路で通過する辺
    • 最後の更新辺の近く
    • など

近傍

  • 辺の工事日を変える
    • ランダムに変える
    • 隣接する辺の工事日を選ぶ
    • 工事辺が少ない日
    • コストが一番小さくなる日
  • 2辺で工事日をswap
  • 頂点を選んでそこにつながる辺について、貪欲に工事日を決め直し
  • 工事する辺をパスとみなして伸ばす/縮める、工事日を変える
    • 近くの2辺を同時に変更

2辺の相性を最適化

その他のアプローチ

その他

最適解に近づくと、工事している道路がパス(最短路上の辺?)っぽくなる現象

  • 直感的には工事する辺はバラバラになっていたほうがよさそうに感じられる
  • しかし、ある程度改善した解では、工事日がパス(直線)っぽくまとまりになっている場合が多い
  • これは、ある工事している辺eについて見たとき、その辺の両頂点からそれぞれ少し離れた頂点間では、辺eをギリギリで迂回するというよりは、大きくなめらかに迂回するような最短経路になりやすいため、辺eの隣接辺についてもまとめて工事したほうがよい可能性がある(解説放送)
    • あと、直線的な感じだと、それに直角方向に通る最短経路は邪魔しないのも良い
  • 他、最短路a→b→cについて、そのa→bをとb→cを別の日に工事すると2日分使えないが、同じ日に工事すると1日は使えることになるので、まとめて工事したほうが良い可能性がある
  • https://twitter.com/not_522/status/1622199063583277056
  • https://twitter.com/gmeriaog/status/1622193079926288385/photo/1

工事道路が0個になった日があったら0個のままにしたほうがよい?

ユークリッド距離(三角不等式が成り立つ)ならBFSでよい?

SPFA

Dial's Algorithm

Floyd-WarshallのSIMD高速化

ダイクストラ時の状態の型

双対グラフ

Visualizerの使い方

  • 頂点クリックで、その頂点から他の頂点について、工事で増えた分の増量が見れた
    • この機能に気づいていない人も結構いたっぽい(自分も気づかなかった...)
    • visualizerの解説を読もう
  • 赤シートを活用

論文

小ネタ

解説

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