Skip to content

RECRUIT 日本橋ハーフマラソン 2023冬 (AtCoder Heuristic Contest 018)

問題概要

  • 200*200のグリッドで表される土地がある
  • 各マスには10〜5000以下の頑丈さの岩盤があるが、これは不明で、1度にC+Pの体力を使ってPだけ岩盤を削ることができる
    • 頑丈さはパーリンノイズで生成される
    • Cは、入力で与えられる正の整数(1,2,4,8,16,32,64,128)
    • Pは、削るときに毎回決める値(5000以下の正の整数)
    • 各マスについて、最初の頑丈さ以上に削った場合に岩盤が破壊される
  • W(=1〜4)箇所に水源、K(=1〜10)箇所に家があり、水源から岩盤がなくなっているマスを辿って水が流れる
  • できるだけ少ない体力で、岩盤を削り、すべての家に水が流れるようにせよ

時間

  • 199 時間

個人的メモ

  • 探索と活用のバランスを取りながら、硬いところをできるだけ回避してルートを作る、のが難しい問題
  • ざっくり、「格子点や不確実性が高いなどのマスを試掘し、その情報から地図を作成し、水路ルートを更新、を繰り返す」方法が強かった模様
  • また今回は、結構似たようなアプローチを取った人が多かったためか、細かい処理・関数の違いやパラメータ調整具合でかなり順位に差がでていた可能性がある

問題固有の性質

  • 家や水源の位置の頑丈さは、柔らかい場合が多い
    • 頑丈さに反比例する確率で選ばれるため
  • 近くのマスは同程度の頑丈さであることが多い
  • 柔らかいところを軽く調べるのは低コストでできる
  • 硬いところを通らないルートを作ることが大事
    • 頑丈さが、やわらかい(低い)ところは数十程度なのに対し、硬い(高い)ところは数千程度あるため、100倍ちかく違う
    • そのため、硬いところを超える短いルートよりも、柔らかいところのみを通る長いルートのほうがよい、などがある
  • 試掘で地図を正確さを高めるのと、どの程度不正確な地図で水路ルートを決めるかバランスが難しい
    • コストに見合わない場合も多く、高度な手法ではなく単純な貪欲などでも十分強かった
    • コストを抑えるために、不正確・少ない情報で判断する必要があったため、ヒューリスティックを入れまくるほうがよかった？
  • 掘るときのパワーは小さいと、回数が増えてしまう一方、正確に推定でき、また、その近くの地点の推定も正確にできる
    • Cが128程度でも、正確に推定できるメリットが大きいためか、powerは小さい方がよく、あまりCによる違いが大きくなかった模様

頑丈さの推定

  • 頑丈さについて、正確な情報が得られないため、2つ推定したいものがある
    • 現在の試掘状態から真の頑丈さ
      • 掘りきった、掘りきっていない
    • 試掘した地点から、まだ試掘していない(周囲)地点の頑丈さ
  • これらを考慮して、試掘地点の選択、頑丈さを推定、掘削パワーの決定、を行う必要がある

現在の試掘状態から真の頑丈さの推定

  • 掘りきった/掘りきっていないしかわからないため、正確な頑丈さを得るのが難しい
    • 細かく刻めば真の頑丈さに近い値がわかるがコストがかかり、荒く刻むとコストはかからないが真の頑丈さの推定精度は低くなる
  • 真の頑丈さについて、区間で表現するすると扱いやすい?
    • 最大(上限)、最小(下限)
    • 分布(正規分布) -> ガウス過程回帰
  • 今回、おおよその値が入力データの統計から分布を見て推定
    • 指数的だった模様?

試掘する地点の候補

  • 近くのマスが同程度の頑丈さであることが多いので、あまりすでに掘った地点の近くを調べる必要がない
  • そこで、ある程度離れた地点を調べたかった
    • 格子点
    • 不確実性が高い地点
  • また、通らないような地点を調べても無駄なので、現状でのベストな水路ルートを作ってみてそのルート上の地点を調べることで無駄な試掘が減らせる
    • 掘削していないところは無駄に調べない、など細かい非効率が重なると差がつく可能性がある
荒いグリッドやメッシュの格子点
  • フィールド全体をM*M程度の荒いグリッドにして、その格子点を調べる
    • 軸に直角/斜め、三角格子、ハニカム、サイコロの5の目のような感じ、など
    • Mの値は人によって違っていて、10程度〜30程度など
      • 細かくすると、水路ルートが計算するたびぶれまくったり、計算コストが増える恐れもある
  • 家や水路も含むようにしておく
不確実性が高い地点
  • 格子点ではなく、任意地点で調べる価値があるが不確実性が高いところを調べる
  • ルートの中間地点(二分探索的に調べる)
  • なんらかの方法で、不確実性が高い順に調べる
次に破壊された場合に嬉しい地点

推定方法

逆距離加重和、距離を考慮した重み付き平均
  • Inverse Distance Weighting
  • 距離の逆数を重みとした加重平均
  • パーリンノイズはユークリッド距離的な感じなので、距離を使うときはユークリッド距離で計算したほうがよいかも
線形補間
近傍マスで重み付け
ガウス過程回帰
MLS(Moving Least Squares?)

試掘時のパワー

  • 基本は、推定値程度(か、少し弱めのパワー)で試す
  • また、岩盤が壊れない場合に、壊れるまで試してしまうと、硬い岩盤の場合にかなりコストを使ってしまうので掘り切るのは避けたほうが良い
  • 壊れない場合は、小さいパワーで追加で削ったり、しきい値以下までしか削らない等で、コストを抑えておく必要がある
    • 回数を抑えるために、power_i = init_power * alpha^i的な感じで徐々に増やす感じ、など
    • 今回、追加で調べるときのパワーは小さい方がよかった模様
    • 小さいと回数が増えてしまいCによるコストが増えるが、正確に推定でき、周囲の推定精度やルートを削るときのコストが減らせる副次的メリットが大きい

水路ルート生成

最小シュタイナー木

  • 平面上の点を結ぶ(点を追加してもよい)直線で総距離が最小のものは最小シュタイナー木で求められる
  • が、200*200程度の地点もあるため、かなり計算コストもかかってしまう
  • また、不正確な推定情報しか使えないのもあるため、最適解である必要があまりなく、厳密に最小を狙わず、近似的に低コストなルートが作れれば十分だった
    • 候補点が多いと、ルートが更新毎にぶれまくってしまう
    • 高速に計算できると、総実行時間も減らせて、パラメータチューニングなどを多く試行できるメリットがある

格子点上のみで計算するか、全マスで計算するか

ダイクストラを繰り返す、で近似

  • 水源に近い家から貪欲に、ダイクストラ等で一番近くの水があるマスにつなぐことを繰り返す
    • ダイクストラを使っている人が多かったけど、平面的なのでSPFAでもよかった？

MST上で最小距離でつなぐ、で近似

  • 格子点でのグラフでMSTを作って、そのMSTの辺のみを使って各家から水源への最小距離でつなぐ
    • (自分はMSTの不要な葉頂点を繰り返し消してルートを作ったけど、普通に最小距離で繋げば余計な処理を削れた、、、)

水路ルート上の掘削

  • 基本は推定値程度で掘って、壊れなければ壊れるまで掘る
  • 試掘時の推定値や、格子点の場合は両端の値から推定
    • 平均、期待値DP、など
  • 基本、1マスずつ壊すのだと、一つ前の情報も使える
  • 1マス飛ばしで調べて、前後の値を使うなども工夫可能
    • どの程度効くかは不明

パラメータチューニング

  • 今回、高度な手法やアイデアというより、十分汎用な手法でパラメータチューニングをきちんとするのが重要だった可能性がある
    • 「Cごとに1000〜10000ケースでチューニング」みたいな上位に多かったかも
  • 高速に大量のケースを試すために、高速な解法にする、並列実行(クラウド実行)、探索方法の工夫など

チューニングツール

焼きなましっぽく探す

  • 6位のarvindf232さんは、焼き鈍し法っぽい感じで、テストケースを時間とともに増やしながらパラメータ(十数個)を最適化した模様

その他

SPH(Smoothed Particle Hydrodynamics)

ボーリング調査

マンハッタン距離のとき単純な経路が選ばれやすい問題

サンプルがそこそこ強かった

  • 全制約を使っていてかつシンプルな解法、ゆえに結構強かった(解説放送)
    • Powerも100が適当に決めたわりによい値で、上げたり下げたりすると、結果は悪化してしまった模様
    • ここから工夫を入れようとしても、コストがかかってしまって逆に悪化しやすいなどあり、結構サンプルよりも良い結果を得るまでが難しい

手元での評価方法

問題の元ネタ

入力データの傾向の調査

visualizer周り

インタラクティブ問題のデバッグ方法

shake up/shake down

  • 今回は、暫定ケースがまあまあ偏っていた可能性がある
    • C=1のケースが少なかった？
  • そのせいか、暫定順位とシステムテストの結果で順位変動がいつもより大きかったように思われる

解説

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