Skip to content

AtCoder Heuristic Contest 057

問題概要

  • L*L (L=10^5)のサイズの2次元平面(トーラス構造)上に、N(=300)個の原子がある
  • 各原子は、初期位置と初期速度が入力として与えられる
  • 各時刻tでは、「結合フェーズ」と「移動フェーズ」が順番に繰り返される
    • 結合フェーズ: 異なる連結成分(分子)の2原子を結合する。このとき、連結成分の速度は、運動量保存則に従う。
    • 移動フェーズ: 連結成分の速度に従って、位置を移動する
  • 結合時、2つの原子の距離がコストとして発生する
  • 時刻T (T=1000)において、連結成分数がちょうどM(=10)個、かつ、各連結成分のサイズがちょうどK(=30)個になるようにしたい
  • 結合コストの合計ができるだけ少なくなるような結合計画を求めよ

時間

  • 4 時間

個人的メモ

  • 「グループの作り方」「マージの仕方(どの原子を、いつ結合するか)」を考える必要がある
    • "グループ"という用語は、最終的に作られるM個の分子(やその中の原子集合)の意味で使ってます

原子、分子の速度

  • 原子
    • 遅い原子と速い原子があり、速い原子は時刻Tまでに、平面の広い範囲を移動するので、いろんな分子に近づく可能性が高い
      • とはいえ、速度の絶対値が0に近いようなものはほぼない
    • 速度は各軸方向に最大100で、1000ターンなので、最大でも画面を端から端までの距離ぐらいしか動かない
    • 速い原子は動いている間にいろんな原子や分子と近づく可能性があるが、遅い原子はあまり移動しないため繋げられる候補が少ない可能性がある
  • 分子
    • 結合すると速度が平均化していくため、大きくなるほど速度が遅くなりやすい
    • 大きい分子同士を結合しようと考えると、どちらも速度が遅い可能性があり、時間内に十分近づけないおそれがあり得る
    • 一方、大きな分子に、原子か小さな分子が結合する場合、大きな分子側の速度変化は小さく、結合後の速度が予想しやすい

分子の形

  • 結合したら分子内の原子の相対位置(形)は固定になる
  • 理想的には、ある1点ですべての原子が結合できればゼロコストで分子が作れる
    • が、それは難しいため、ある程度の大きさの塊になる
  • 結合コストが同じ分子を考えた場合、どういう形になってるとよさそうか考えると、できるだけ分子は広がっていた方(棒や面など)が、その分子に結合しやすい原子分子が増えそうに見える
    • スターグラフっぽい感じよりライングラフっぽい感じ
  • ただ、ライングラフだと局所改善しにくいかもしれず、できるだけ小さな塊ができるように狙うほうが改善しやすいかもで、よくわからない
  • 結果的には、最上位はかなり小さい塊を作ってそうだけど、4時間ではそこまできれいに作るのも大変だったので、小さい塊を長い辺でつなぐ感じでも上位を目指せた

分子の誘導

  • 2つの原子を結合した場合、それらの平均速度に変化するため、うまくペアを選ぶと、ある程度狙った方向に移動するよう誘導できる
  • また、逆向きの速度の原子を結合すると、速度を相殺してほぼ停止させることができる
    • ただ、小さい分子で動きが遅くなると不利なので、逆に作らないようにしたほうがよいっぽい(速度が落ちない方がうれしい、を評価に組み込む)
  • 似た速度ベクトルの原子同士を結合してもあまり速度ベクトルは変化しないので、向きや最終地点などがあまり変わらない

2原子の結合タイミングの計算

  • T=1000程度なので解法によっては愚直にシミュレーションしても求められるが、より高速に計算することができる
  • 無限に広がる2次元平面上の2原子a,bで考えると、その原子が一番近づくときの時刻と距離はO(1)で求められる
    • (ABC426Eでも出ていた問題らしい)
    • 時刻tでの位置を、p_a(t) = p_a(0) + v_a tとp_b(t) = p_b(0) + v_b tとする
    • 相対位置r(t)=p_b(t)-p_a(t)と相対速度v=v_b-v_aとすると、距離の2乗|r(t)|^2 = r(t) \cdot r(t)=r(0)\cdot r(0) + 2(r(0) \cdot v)t + (v \cdot v) t^2をtで微分して0になるタイミングと考えられる
    • tについて整理すると、t=-r(0) \cdot v / v \cdot vになる
      • 成分で書くと、t=- (r(0)_x v_x + r(0)_y v_y) / ({v_x}^2 + {v_y}^2)
      • 相対速度が0の場合は、相対位置関係が変化しない
  • 時刻はt=0〜T-1までなので、その範囲を超える場合は0かT-1にclampする必要がある
  • また、今回はトーラスで、位置のx,yが-L,0,+Lになったものも同一視するので、相対位置を-L,0,+Lで変えた9パターンについて確認し、最小距離となるものを使えば良い

アプローチ

  • きっちり「K個からなる分子をM個作る」必要があるので、グループをどう作るかが悩ましい

時刻ｔでまとめてMST構築

  • ある時刻で、原子をグループに分けて、MSTを作る、がベースラインアプローチとして考えられる
    • MSTにするのは、つなぎ方によるコストを最小化するため
    • グループ化はK-meansなど
    • いろんな時刻で試してみる、などができるが、これは、偶然いい感じにまとまるタイミングを狙う感じになる
  • すべて同時に結合する必要はないので、いい感じに時間をずらして結合することで、より改善につながる可能性が考えられる

評価関数を作って貪欲

  • マージコストやマージ時刻で評価関数を作って貪欲にマージ
    • うまくグループ作れるかは別途チェック

グループ内は貪欲構築で、原子のグループ割当を局所改善

  • グループをK-meansなどで決めたとき、そのグループ内の原子を貪欲にいい感じに構築できると、グループ割当の方を局所改善できる
    • 初期グループと貪欲法がそれぞれ良い感じにできる必要はありそう
  • 時刻tにおいて、一番距離の近い原子ペア(同じ分子内は除く)に対して、今マージするか、少し後の方が近づくなら保留するか判断、をTターン繰り返す、など賢い

段階的マージ

  • 時刻をフェーズに分けて、各フェーズで2個の分子をたくさん作る、4個の分子をたくさん作る、など、どんどん大きくしていく
    • ただし、K=30のため、2個の分子&原子 -> 3個の分子&4個の分子 -> 7個の分子&8個の分子 -> 15個の分子 -> 30個の分子、のような作り方をする必要がある
  • どれと結合するか？はマッチング問題になる

最初に団子を作って、残りはマッチングし、結合していく(writer解)

  • https://x.com/prussian_coder/status/1994710494809325831
  • (解説放送)
  • 早い時刻での原子がたくさんある状態では、適当に「近くに来たらくっつける」としてもある程度のグループが作れる(10個程度。団子とする)
  • そこで、ある程度散らばるようにM個の団子を先に用意し、残りの原子はその団子のどれかにくっつけていく、というアプローチが考えられる
    • 団子を作った後の時刻で一番近づくタイミングで原子を団子につなげていく
    • writer解だと、適当にM個を同時に作るわけではなく、1個ずつ団子を作ってみて、他の団子に近かったり個数が少ない場合はやり直してそう
  • 団子を作った後で残っている原子をどの団子に割り当てるか？が問題になるが、これは、マッチング問題として解ける
    • コストは、団子と原子の距離
    • 団子は結合ごとに微妙に速度が変化してずれるため、これを段階的に、結合時刻が小さいものを何個かずつ採用しながらマッチングを解き直すようにするとかなり改善する模様
      • ローリングホライゾンというらしい
  • 原子単位ではなく分子(2原子)で速度を誘導するのも含めるとさらに改善する
    • 整数計画法でortoolsで解く、焼きなまし(厳しい？)、など

集合場所を決めて、そこに集まるよう誘導(wataさん解)

  • https://x.com/wata_orz/status/1994709061309534597
  • 原子をペアにした分子の時刻Tでの位置を考える
  • 目標地点集合を決めておき、そこにできるだけ近くなるようにペアを作る
  • 最後に、全ペアをできるだけコストが小さくなるよう結合する

焼きなまし

  • グループの作り方もマージの仕方も微調整(局所改善)できるので、全部を焼きなましする方法が考えられる
    • また、貪欲解などを初期解にして、時間があまったら使える可能性があるので、実装がやや重いが、書いて損にはなりにくい
  • コストの計算が重く、探索空間も大きくなりやすいので、前計算やグループの作り方に制約をいれるなどは必要
    • 「分子に原子を結合」に限定
      • 分子と分子をつなげるようなものは複雑になりすぎるので考えない
      • どのグループに結合するかと結合時刻だけ考える
      • 分子内のどの原子と結合するか、までいれたりすると探索範囲が広がりすぎる恐れ
    • スターグラフに限定→任意グラフに緩和
    • など
  • 近傍は、グループ割当のswapや結合時間を変更で、工夫すると、かなり良いスコアが取れる模様
    • 各グループで一番距離のある原子を入れ替える
    • 距離に比例して選ぶようにする
    • 正規乱数で結合時間をずらす
    • など

t=0ではなくt>0の時点での位置でグルーピング

  • 団子解や初期グループ構築などで、グループを考えるときに、t=0ではなく、t=100〜400などt>0の時点での位置でグルーピングを考えるのが有効だった、という人が見かけられた
  • (一応考察メモ)
    • 時刻t付近で原子の結合タイミングを調整すると考えると、t=0の場合、t<0には調整できないので、位置は近いけど、離れる方向に移動している原子はt=0で結合しなければいけない
    • 一方で、t>0での位置で考えた場合、位置がある程度近い原子は、時刻tの前後でその付近を通るはずなので、近づく方向に調整できる可能性ができる
    • また、時刻tが500以上など遅いタイミングだと、分子は結合するほど遅くなる傾向があるので、t以前で結合したせいで、時刻tでの想定位置とズレてしまう可能性がでてしまう

その他

スコアと平均距離の関係

  • 順位表のスコアでいうと、各辺の平均結合距離は以下のような感じ
    • スコア9億点 -> 平均1562
    • スコア8億点 -> 平均2480
    • スコア7億点 -> 平均3937
    • スコア6億点 -> 平均6250
  • 上位に入るためには平均2500以下ぐらいを目指さないといけなかった

ローリングホライゾン方式

  • 現時点からT期間(ホライゾン)だけ先までを考慮して最適化し、その最初の1〜数期間を確定・実行して、状態を更新し、期間をずらして、同じことを繰り返す、アプローチ

General Weighted Matching

AI活用

  • 上位でAI活用したと言及してた人が結構多かった印象
    • そして、指示が難しいという旨も、、、
    • かなり丁寧・曖昧がないように書く必要がある(余計な近似や処理を入れがち)

解説

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