Skip to content

AtCoder Heuristic Contest 025

問題概要

  • N個のアイテムがある
  • ただし、アイテムiの重さw[i]が未知
  • 天秤によって、指定した2つのアイテム集合の重さの総和を比較した結果を知ることができる
  • Q回天秤で比較を行うことで、できるだけ重さの総和の等しいD個の集合に分割せよ

時間

  • 199 時間

個人的メモ

  • 基本的な局所改善を見つけて、より効率よく行う方法を見つけるのが重要だったみたい

基本アプローチ

  • 2つの集合を選んで、アイテムを移動・swapする、を繰り返す局所改善(山登り)
    • 操作後に重さの差が前よりも小さくなっていれば採用
    • これは、「操作前の重い集合の重さ」と「操作後の重い集合の重さ」を比較して操作後のほうが小さければ良い
      • 重い集合から重いアイテム、軽い集合から軽いアイテムを選んでswapする場合は、必ず重い方が減って、軽い方が増えるので、元の軽い方の高さをチェックすれば良い
      • ここで、同じアイテムがある集合を比較することになるが、この比較は、それぞれから同じアイテムを除いたもの同士で比較すればよい
  • 特に、2つの集合はできるだけ重い集合と軽い集合を選んだほうが(差が大きいので)成功率が高く、集合を常にソートした状態を維持すると、必ず選べる
  • さらに、アイテムの重みの推定までやる場合は、重みの期待値から改善の可能性が高いものを選んで操作することで効率よく操作できる

ソート

アイテムのソート

  • Qが多い場合、各アイテムをソートする余裕がある
  • 最初にソートしておくことで、2アイテムの大小関係を把握した上で操作できる
    • ランダム割当より良い初期解が作れる
    • あるアイテムiより小さいもので最大のアイテムを選ぶ
    • あるアイテムiよりも小さいものがなければ打ち切れる
    • あるアイテムが移動後に不採用なら、それより重いアイテムは不採用とわかる
    • など
  • Qが少ないときでも、X個のアイテムだけソート、真ん中以外を狙ってソート、など

集合のソート

  • 集合について、最大重みのものと最小重みのものを対象にすると差が最大のため、ランダムに2集合を選ぶよりも差が大きいので改善できる可能性が高い
  • 常に集合をソートしておくことで、最大のものと最小のものを対象にできる
    • 二分探索で挿入位置を決めるO(2logD)
  • (自分はランダムに2集合を選んで既知の情報からできるだけ重みが離れるようにしたりしたけど、常に選べるわけではないので差がついてしまっていた模様)
  • 解説放送だとだいたい50位相当

ソートの種類

局所改善操作

  • 2つの集合(できれば最大と最小の重みの集合)について
    • 重い集合から軽い集合にアイテムを移す
      • (正確には、動かすアイテムを除いた上で比較して低い方に置くほうがよい)
    • 重い集合から軽い集合にアイテムをswapする
      • 1要素同士のswapの場合、2つの集合間の全部の組み合わせは必要なく、2つの集合のアイテムをまとめてソートして異なる集合での隣接だけ見れば良い
      • しゃくとり/二分探索的に探索したりなども
    • Largest Defferencing Methodを適用する
  • ランダムに操作を選ぶというより、操作できなくなったら他の操作を有効にする、優先度を決めるとかがよいみたい
  • 2つのアイテムをくっつけて扱う、2つの集合を混ぜて真ん中を2分探索でみつけて分割、とかも

大小関係の推定

  • 問い合わせ内容によっては、過去の問い合わせ内容から大小関係を導き出せる
    • 推移律からA<BとB<CがわかっていればA<Cがわかる
    • A+B<CならA<CかつB<Cがわかる
    • など
  • あるX<Yが判明した場合、「Xより小さいとわかっているアイテム」と「Yより大きいとわかっているアイテム」の間にも大小関係が成り立つ
  • ただ、上位の方だと重さの推定の方をしていそうで、あんまりここを頑張る感じではなかったっぽい？
    • 1対1より多い組み合わせを考えると計算量とかも厳しい

必要クエリ数の推定

重さの推定

  • 指数分布のため、軽いのが多く、重いのが少ない
  • 推定しようとすると、重いアイテムの分散が大きく推定が難しい
    • 例えば、アイテムがソートされていて、i番目の重みの期待値を考えたり
  • そのため重さの推定だけで上位に行くのは難しかった模様(解説放送)
    • これに上記の山登りを組み合わせるなどは必要

線形計画法(LP)

重さの推定

writer(wataさん)解

  • https://twitter.com/wata_orz/status/1716034332241051794
  • (詳細は解説放送)
  • Qが小さいときに強い
  • アイテムの移動操作前後の改善量の期待値を考え、一番期待値の高い移動を試す
    • 分散なので重みの2乗和で考えると、軽い方Aと重い方B+bについてA^2+(B+b)^2が(A+b)^2+B^2になるのでその差が改善量
    • この改善量の期待値は解析的に求められないので、各アイテムの重みの推定値から考える(複数のwを用意すると分布)
    • アイテムの重みは、w[0],w[1],...を順番にギブスサンプリングで求める
      • 具体的には、w[i]を考えるとき、それ以外を固定して、w[i]が満たすべき値の範囲からリサンプリング、を1周する
    • 参考：HTTF2022予選
  • 実際の各アイテムの重みの推定値を見てみるとうまくいっていないように見える
    • 例えばアイテムaとアイテムbが常に一緒に扱われていたら、その和だけが重要で、それが正しければ十分
      • aとbを分けるときに具体的な重みが必要になる
    • そういうケースでは各アイテムの重みを正確に当てに行くよりも効率がよいみたい

順位スコアの扱い

  • 今回は「順位スコア」(順位率)だった
  • topの最適解がどの程度か見積もるのが難しいし、生スコアの悪化がどの程度影響するかも見積もりにくい
  • 絶対スコアも相対スコアも適用しにくい問題だったっぽいが、ランダム性が強いところでぶれやすかったりもする

順位スコア採用の裏話

  • (解説放送)
  • 相対スコアを使った場合、分散が大きい
    • 1位の人でもケースによって相対スコアの分散が大きい
  • ケースの重要度が変わりすぎてしまうので、それを抑えるために順位スコアを採用

ローカルでの改善判断

  • 何を参考にすればよいだろう？
  • スコアの扱い
    • 相加平均、相乗平均
    • logを取ったスコア(相対スコア)
    • ケースごとの勝ち負け数
    • スコア*f(Q,D,N)
    • 手元でのベストスコアとの比較(ただしスコア1とか出ると微妙になる)

その他

数分割問題

Merge-Insertion sort(Ford–Johnson algorithm)

スターリンソート

トーナメントソート

Largest Defferencing Method(LDM)

  • 差分法、Karmarkar-Karpアルゴリズム
  • 数字を降順に並べて、最大と最大の次に大きい数をその差分で置き換える、を繰り返す
  • 要素が1つになったら、そこからバックトラックで実際の分割を復元する
    • 復元でどちらの分割にいれるかは、大きい方を自分と同じ分割に、小さい方を異なる分割にいれる
  • 例: 数字の集合S={8,7,6,5,4}を集合K=2に分割する場合
    • 8と7を選んで差の1に入れ替えてS={6,5,4,1}
    • 6と5を選んで差の1に入れ替えてS={4,1,1}
    • 4と1を選んで差の3に入れ替えてS={3,1}
    • 3と1を選んで差の2に入れ替えてS={2}
    • 分割2|φを考える
    • 2は3と1だったので、3|1に戻す(3を2があった方、1を他方に入れる)
    • 3は4と1だったので、4|1,1にする
    • 1は6と5だったので、4,5|1,6にする
    • 1は8と7だったので、4,5,7|6,8にする
  • グラフで考えると2分木になる
  • 3分割以上にも拡張できる

Largest Processing Time Heuristics

類似問題

その他

解説

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