Skip to content

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

問題概要

  • L*Lのグリッド(トーラス)で表されるAnother SpaceにN個の出口があり、1対1に対応するワームホールと繋がっている
  • Another Space側の各セルに空調設備を1つずつおき、温度調整ができる
    • 温度設定コストは周囲のセルとの温度差から決まる
  • 1回の計測では、ワームホールを1つ選び、出口を通って予め決めておいた移動を行った先のセルの温度を計測できる
    • 計測コストは、移動距離に応じて決まる
    • 計測機器の都合のため、計測した温度には誤差が含まれる
  • 設備の配置、計測、回答、の順で行うとき、できるだけコストが少なく、かつ、正しく対応関係を見つけよ

時間

  • 223 時間

個人的メモ

  • 配置をどうするか、計測をどうするか、推定をどうするか、それぞれアプローチの自由度が高く、よい戦略を見つけるのが難しい問題
    • どれがよいアプローチかは試してみないとわかりにくいため、いろいろ試すのが重要だった
  • ざっくり、きちんと対応関係を確率で表現し、可能性が高い順に計測する、という方法が強かった模様

問題固有の性質

  • 評価指標が複数ある(配置コスト、計測コスト、正解率)
    • 何がどう影響するかがわかりにくいので、やって見るほかなかった
  • ワームホールと出口は1対1に対応する(1つしか対応しない、順列、という情報が使える)
  • 0〜100よりも450〜550で盤面を作ったほうが0で打ち切られないため得られる情報が多い
    • 0から増やす方で考えるより、500を基準に減らす方/増やす方で調整したほうがよかったかも

主なアプローチ

  • いろんなアプローチがあり得たが、一部でいうと以下

bit埋め込み

  • Nは100個なので、7ビットで表現できる
  • Lが広く、Nが少なければ、周囲のマスをビット表現にしてそこから復元することができる
    • 計測コストが少なく済ませられる
  • しかし、この方法では、密度が高い場合(Lが小さい場合)では難しかったり、配置コストが大きくなってしまう問題がある

1点高い位置を作る

  • ある1マスを1000で、他を0としたりすると、各出口からそのマスを計測しようとして、計測できれば出口を特定できる
    • 配置コストを比較的少なくできる
  • しかし、Sが大きくなると計測が難しくなってくる

ワームホールiと出口jが一致する確率を計算

  • 今回上位の人の多くが取っていたアプローチで、ワームホールiと出口jの対応関係を確率で表し、計測情報が得られるたびにベイズの公式や確率計算をし直して、一番可能性の高いところを探す

推定パート

  • 得られた計測情報をワームホールiと出口jの関係性を明らかにするのに使いたい
  • 上位では、これを確率で表現して扱っていた
  • また、入口と出口が1対1対応するという情報を計算途中でも考慮できるのが強かった模様
    • 「ワームホールiはどの出口jに対応してそうか？」だけでなく、「出口jの確率が高ければ他のワームホールiには対応しなそう」という情報
    • 最後に加味するだけでは不十分で、計測中で考慮できると計測回数が減らせた

入口iが出口jに対応する確率

  • 観測データDが与えられて、入口iと出口jが対応する確率P(i=j|D)を考えると、ベイズの式から、P(i=j|D)=P(D|i=j)*P(i=j)/P(D)
    • どれが対応するかの事前知識はないので、P(i=j)は一様で、i,jについてすべて同じ
  • P(D|i=j)は尤度・同時確率分布で、正規分布の確率密度関数に観測値を入れたもの(の積)を使う
    • 0〜1000にclippingされるので、尤度(確率)計算ではそこも考慮する
  • P(i=j)である確率は、P(i=j) = P(i=j|D) / ΣP(i=j'|D)で求められる
  • 行列で表現すると、各行について求めている感じになるが、今回の場合、1対1対応するという情報から、あるi=jの確率が高い場合に「他のiがjに対応しない」という情報も加味できる(列方向)
    • ただし、厳密にiとjの対応関係を順列を考慮して確率計算しようとすると大変
  • これは二重確率行列というもので、Sinkhornアルゴリズムという反復解法で近似解を求めることができる
  • p/(1-p)を取るとよい話も
二重確率行列、置換行列
  • 入り口と出口の対応関係の確率を行列で考えると、1対1対応するので、二重確率行列というものになる
    • 各行の和が1であるような行列を確率行列
    • 各行、および、各列の和が1であるような行列を二重確率行列
    • 各行、および、各列のなかで1が1つだけありそれ以外は0であるような行列を置換行列
  • Sinkhornアルゴリズム、Sinkhorn-Knoppアルゴリズム

割当問題

  • 得られた計測データから、対数尤度を値として割当問題として解くアプローチもある
  • 最後に1対1対応になるように適用することが考えられるが、差分更新をしていくこともできる模様

ベクトルの距離の差

  • 自分は、各iについて、予め決めておいた相対位置で取得できる値を要素に持つベクトルを考えて、期待値ベクトルとの差を考える方法でとりあえずやっていたのを最後までそのままにしていた、、、
    • 未観測部分は期待値と一緒として扱う
    • 差が小さいものから探す
  • しかしこの場合、確率が高いやつよりも情報が少ないやつが選ばれやすかったかも、、、

計測パート

  • 計測コストでいうと距離が小さい方がよいが、どちらかというと計測回数を少なくするのが大事だったかも
  • 計測地点
    • 基本は、ある2つについて計測したときに識別することができるよう値の差が大きくなる地点、かつ、できるだけ近いところ、を探したい
    • または、予め用意した「計測地点」を計測するようにする
      • ある1地点を何度も狙って計測する場合は、全部の出口からできるだけ近いところにその1地点を持ってくる方が良い
      • ただ、距離の総和の最小値ではなく、近いところから決まっていくような場合は回数的な重み付けをしたほうが良い模様
      • https://twitter.com/Jiro_tech15/status/1693203779582386276
  • 計測順番
    • 距離がコストなので、距離が小さい計測から行ったほうが、最後の方で距離が長い計測する回数を減らせる
  • 一番怪しい/情報不足なやつから探すよりも、可能性が高い方から探したほうがよいっぽい
    • おそらく、可能性が高いの出口よりも情報がほぼない出口を先に計測する可能性があったりで計測回数が増えてしまうかも

measure(i, pos)のどちらを動かすか

  • 計測では、iを動かすか、posを動かすかが考えられる
  • pos側を動かす場合は、外した場合の情報はiでしか使えない
  • posを固定してiを動かす場合は、期待と違った場所を計測した場合でも、そのiの位置を特定する情報に役に立つ可能性がある

確率最大のものを計測

  • ワームホールiと出口jの対応関係を確率で表している場合は、その確率が一番高いところを計測しにいく
    • 一定以上の確率値になったら対応するとみなして計測しない

エントロピー最大/KL-divergence最小

二乗誤差

ジニ係数

配置パート

  • 一番自由度があり、配置によって計測や推定の方法が代わりうるので、重要そうだが、計測や推定方法が優れいている場合はそんな奇をてらったものは不要だったみたい

配置パターン

山の形での配置コスト最小の配置

その他

同じ地点を繰り返し計測した場合

  • ノイズが正規分布に従うので、1回での計測値の分散はS^2
  • 正規分布の再生性から、正規分布の線形結合は正規分布の形になり、同じ地点をk回計測した場合の分散はk*S^2で、平均化のためにkで割ると、k/k^2*S^2=S^2/kで標準偏差的には1/sqrt(k)倍になる
    • kを増やしてもある程度のkからは減少幅が小さくなり、Sが大きい場合は必要なkが大きくなってしまう
  • 反復符号的には、温度が0か1000かを区別するのに500をラインにするとそれを超えてしまう確率はS=900でも30%ぐらいだと思うので、繰り返して多数決とかすれば誤り率は減る、と見ることもできる

配置コストと測定コストのバランス

  • 同程度になったほうがよいかというと、アプローチ次第で、そうでもなかった模様

標準正規分布のロジスティック近似

実装周りの工夫

  • アプローチを切り替えやすいように実装する
    • 関数・クラス(〜Solver)に分ける、Strategyパターン、など
  • 最初から高速化しすぎない
    • 1秒とかで回して、評価時間を短くする方を優先
  • 評価結果の情報量を増やす

costtt

お絵かき

解説

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