AHC040解法メモ

解法を雑にまとめたものです。

全ての解法で前提としていること

• \(i\)番目の配置方法の\(b_i\)は\(b_i=-1\)または\(b_i=i-1\)、\(d_i\)はUのみ。
  • これらの守ると箱が引っかかることがなくなる。
• 推論は行わないので、全て初期の計測値をもとに考える。

解法

1投目(暫定テストの絶対スコア: 57,909,381)

• 正方形に近いとスコアがよさそう
• 形状を箱の形状を無視し、箱の合計面積をギリギリ超える正方形が理想形なので、その付近で横幅の基準値を決める。
• 順番に置いていき、その段の横幅が基準値を超えそうであったら次の段に移動する。ということを繰り返す。
• 回転は全ての箱が縦長になるように置く。
  • 各段で縦長と横長が入り混じるのは無駄が多そうに思えたのでこのようにした。
• \(T\)回の操作は横幅を理想値\(\pm10^5\)の範囲でランダムに変化させて貪欲に配置した。(本当は\(\pm2\times10^5\)のつもりだったが、コードを見たら掛け算ではなく足し算になっていた)

2投目(暫定テストの絶対スコア: 56,611,677)

• 最終段だけ短くなるケースがもったいなく感じたので、各段の横幅が均等になるように配置することを考えた。
• スコアに用いられるのは最大の横幅のみなので、最大幅の最小化をするのがよさそう。
• 長方形の回転が決まっていると全長方形の横幅が定まる。段の数も決め打つと、 Yokan Partyを解けばよさそう。
• 段の数は\(N\)通りなので全探索で推定値の\(W\)と\(H\)の和が最小になるものを貪欲で選べばよい。
• 時間と操作回数が余るので焼きなましを行った。
• 遷移はある長方形の回転を変えることのみ。
• 評価は毎回\(N\)通りの全探索を行うのは時間がかかるので、最初に行った貪欲での段数\(\pm2\)の範囲を探索した。