Skip to content

HACK TO THE FUTURE 2025(AHC040)

問題概要

  • N個の長方形があり、横幅と縦幅が決まっている
    • 長方形には番号がついており、区別される
  • 最初に入力として、各長方形を計測誤差あり(ガウス雑音)で観測した値が与えられる
  • クエリとして、選んだ長方形を以下の操作で配置することができ、配置後の長方形座標の縦と横の最大値が計測誤差ありで得られる
    • 配置する長方形の番号(ただし、番号は昇順に配置)
    • 90度回転するかどうか
    • 配置するときの方向
    • 配置するときに基準とする配置済み長方形の番号、または、壁沿いかどうか
  • クエリはT回投げる
  • スコアは各クエリでの「配置した長方形座標の最大値の和＋未配置の長方形の横幅と縦幅の和」の最小値としたとき、これを最小化せよ

時間

  • 240 時間

個人的メモ

「衝突」

  • https://x.com/Shun___PI/status/1866070101944053912
  • 正確な幅がわからないため、大小関係を見誤ると、想定していた地点に配置されずに、途中の他の長方形と衝突したり、止まると思っていた場所で止まらない、といったことが発生してしまう
  • これが配置中に発生してしまうと、想定よりも大きくズレた結果になってしまう
  • そのため、今回は、できるだけこのような現象が起きないような配置方法を考える必要がある

スコアの最小値

  • 面積の合計値だけで考えると、面積が一定で縦幅と横幅の最大値の和が最小になるようなものは正方形になる
    • min. W+H, s.t. W*H=const.
    • W=H=sqrt(面積)
  • 実際は配置によって隙間ができて達成できないが、この値を基にして、おおよその横幅の見積もりや枝狩りに使える
  • ケースによってスコアのスケールが違うため、この値を最小スコアとして、相対スコアで比較すると評価しやすい

誤差にロバストな配置方法

Uのみ

  • 方向をUのみ(または、Lのみ)で、ベースにする長方形は1つ前に限定すると、期待したところ以外に配置される可能性がない
    • 適当なところで折り返して(b=-1にして)あげると、ある程度正方形っぽい感じに配置することはできる
  • しかし、解の形がかなり限定されてしまうため、もっといろいろな配置を試せる方法を考える必要がある

帯状/階段状で考える

  • https://x.com/chokudai/status/1866394403696505313/photo/1
  • https://x.com/Shun___PI/status/1866061590661108020/photo/3
  • https://x.com/montplusa/status/1866061754494865588
  • (解説放送など)
  • 各段の高さが異なる本棚ように考えると、各段に対してどこにいれるかで考えられる(帯状)
    • 基本、方向はUのみ
  • また、「右下方向に長方形が配置されないようにする」を維持すると帯に限らず階段型としても考えられる(階段状)
  • このとき、配置のときにbに指定できる長方形は、各段(帯)や階段の端の部分の長方形だけで考える
  • うまく、十分な余裕を持ちながら配置させることで、想定外の衝突を避けながら配置することができる
    • 横幅が同じぐらいになったり、上の段の幅を追い越したりするようなことをすると、置くのに失敗したり、デッドスペースを作ってしまったりする
  • また、帯状/階段状だと、デッドスペースになる部分も計算しやすくなり、高速に良い評価値の計算ができる
貪欲・ビームサーチ
  • 順番に長方形を入れる操作をビームサーチで探索
  • 評価値
    • 端の部分の長方形から計算される充填率/デットスペースの面積
    • 残りの長方形を液体と考えて、デットスペース以外の部分に入れた場合の高さ(解の下界)
      • または、その残りの面積のα倍したもの
  • 多様性
    • 最終的な最大横幅
    • b=-1で配置した長方形をハッシュ値にしたもの
    • 入れた長方形の位置、幅
    • デットスペースの大きさ(？)
  • その他
    • 帯のマージ
焼きなまし
  • 各段に割り当てる長方形(や各長方形の回転の有無)を焼きなましでも考えられる
    • だいたい、sqrt(N)段ぐらいになると考えられる
  • 実際に配置したときのスコアだったり、各段に対して高さの分散が小さくなるようにしてからシミュレーション上位を選ぶ、など
    • 温度高めにしておくとか、初期解をいくつか用意するなど工夫は必要そう

その他

各長方形の幅の推定

  • 幅の推定値は正確なほど、より安全に配置が行える/配置のバリエーションが増やせる
  • 最終的に出力する解配置とかだと、どの長方形の幅の合計なのか？がわからないため、推定が難しい
  • そのため、解とは別に、推定しやすい配置を投げてそこから推定する

1つの長方形を投げる

  • 一番単純なのは、1つの長方形を投げて、その計測誤差ありの横幅と縦幅を取得して、平均を取る方法
  • しかし、操作回数Tがあまり多くないため、各長方形に対して十分な回数取得できない

複数の長方形をまとめて投げる

  • 例えば、横一列に長方形を並べれば、それらの幅の合計と高さの最大値が計測誤差ありで得られる
  • 合計値については、計測誤差が最終的な合計値に分散σ^2 でのるだけのため、最初に与えられる長方形の情報を使って出した合計値(m個の和であれば分散mσ^2)よりはかなり正確な値がわかる
配置の仕方
  • 横一列、縦一列
    • b=-1のみ、方向をUかLどちらかのみで配置すれば、横一列/縦一列に配置でき、その時の幅の合計が得られる
  • L字型(Г字型)
    • b=-1のみで方向を変えれば、L字型にでき、「横に並べた長方形の横幅の合計」と「縦に並べた長方形の縦幅の合計」が同時に得られる
      • 2個の合計値が得られるので効率的
    • 方向と回転の有無をランダムに決める以外にも、番号の前半は横方向/後半は縦方向にして回転の有無だけ変えるとかも
    • b=-1のみしか使わない場合は角(一番左上)に来る長方形が小さいときに別の長方形と入れ替わってしまうなど問題があるが、縦方向に置きたいならLと横方向に置きたいならUで各方向の最後の番号をbに指定するようにすると、気にしなくてすむ
  • T字型
    • bを配置した途中の長方形にすればT字型のようにもできる
誤差あり合計値情報から推定
  • 簡単のため、ランダムに、幅の計測誤差ありの合計値がt個与えられる場合を考える
  • 各幅を推定する問題は有名問題で、最小二乗法やベイズ推定などで求められる
  • 最小二乗法(正規方程式)
  • ベイズ推定
逐次推定
  • あらかじめランダムに選んでおく方法だと、分散(推定誤差)が大きそうなものを多めに調べる、みたいなことができない
  • 今回は、t-1回目までの結果を得た状態でt回目の配置を選ぶことができるため、より推定が不正確な(分散の大きい)ものを選んで調べる、ということができる
    • 分散共分散行列のトレースが小さくなるように投げる
    • writer解では、カルマンフィルタを使って、貪欲に、各iで横に並べる場合と縦に並べる場合でのそのiでの分散の増分が大きい方に入れるということを繰り返してるみたい
常に長方形0を角においてL字で推定する場合、長方形0の幅の推定値が悪化する

長方形の幅の大小関係の推定

  • 衝突を回避するためには、「長方形の幅の正確な値」までわからなくても「長方形の幅の大小関係」がわかれば十分な可能性がある
  • 例えば、比較したい2つの長方形を縦に並べて、方向Uで別の長方形を重ねたものを配置して衝突したかどうか判定、とかはできる
  • 複数の長方形の幅の和についても同様に並べて考えることができる
  • https://x.com/ToastUz/status/1866065633278046574
  • 今回は、幅を直接推定するアプローチの方が効率的だったかも？

「推定パート」と「配置/詰め込みパート」の回数のトレードオフ

  • 配置に失敗しやすいアプローチの場合は、なるべく多くの解を出力したほうが安定するが、推定に使えるクエリ数は減ってしまう
  • 配置に失敗しにくいアプローチだと、出力数が少なくてもスコアが安定し、推定に使えるクエリも増えて、よりスコアが上がりやすい
    • 十数件ぐらいを出力にして、それ以外を推定クエリにする

ビームサーチの時間調整

  • chokudaiサーチなどは時間いっぱい回せるが、ビームサーチだとビーム幅の調整が必要
  • 各ターンでは、それまでのビーム幅(の合計値)、計算時間、残りターン数、残り時間の情報などが使えるので、それらを使って調整できる

その他

bottom-left法

  • https://orsj.org/wp-content/corsj/or63-12/or63_12_762.pdf
  • 有名問題として「長方形パッキング問題(詰め込み問題)」があり、代表的な解法にbottom-left法(BL法)などがある
    • 配置可能な位置の中で、最も下で、そのような場所が複数ある場合は最も左のところに配置する貪欲

確率変数の和の分散

  • wikipedia
  • V[X + Y] = V[X] + Cov(X,Y) + Cov(Y,X) + V[Y]
  • V[\sum_{i}{a_i X_i}] = \sum_{i,j} a_i a_j Cov[X_i,X_j]

衝突判定のSIMD高速化

類題

シーケンスペア

Windowsでのローカルテスタの準備の仕方

best=unique

解説

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