AHC031参加記
はじめに
TYZといいます。ちょうど１年くらい前にAHCに参加してみて、それ以来長期コンテストにはほぼ参加してます。初心者でも考察してアイデアを実装すればそれが結果に反映されるのが好きなところです。散歩したり、お風呂でのんびりしてアイデアを考えるのが好きなので、今では時間に余裕がある(時間に追われない)長期コンテンスト専門になっています。
ちなみに自分はいわゆるIT業界で働いてますが、仕事でプログラミングすることはほぼなく、プログラミングは完全に趣味として割り切って楽しんでます。なお、言語はGoを使ってます。
今回AHC031の参加記ということで、時系列でどういう風に進めていったか書こうと思ったのですが、
細かいところは忘れてしまったので、どういう風に解こうとしたのか簡単に紹介したいと思います。
問題内容
今回は以下をオフラインで解く問題でした。
- 一定日数にわたるイベントホールの予約情報として各日の予約毎に必要に面積が与えられる。
- イベントホールの大きさは1000×1000のサイズのグリッドで、各予約毎に四角形のパーティションで区画を決める必要がある。
- 区画した面積が予約された面積を下回ると１サイズあたりコストが100発生する。また、日をまたがって区画の境界が変更となる場合は1サイズあたり1の設置・撤去のコストが発生する。
- 適切な位置でパーティションを区切ってできるだけコストを低くおさえたい
結果
コンテンストの結果からいうと50位でした。過去最高順位なので１年通して成長できたかなと思います。嬉しかった反面、一時は20位台後半くらいまでいってあわよくばという気持ちがあったのですが、日曜〜月曜まではほぼ何の改善成果もだせず、ただ順位がさがるのを見守るだけで悔しくもありました。(最終日の月曜は仕事休みとったのに…)
パラメータ毎の結果に注目してみると、空き面積に余裕がない場合のパターンが強くて、空き面積に余裕があるパターンが相対的に弱かったです。どちらかというと何とかしてペナルティをなくそうと、前者の改善に80%くらいの時間を使っていた感じで、後者はなんとなくスコアが小さいから後回しにしてたことが原因ですが、どのパターンを改善するのが効果的ななのか、見極めが難しいと思いました。
さらに細かくみてみると、空き領域（eps<=0.06)の場合、RANK１位になってました。バランス悪かったとしても、力入れたところには結果がでてて結構嬉しい。ということで解法を簡単に説明したいと思います
解法
縦壁作ってを全ての日で固定する方式としました。
空き面積に余裕がある場合
下記の流れで処理しました。先程の結果からすると100位前後の解法ではないかと思います。
- ランダムに1000の長さをN個に区切る。
- 各日でサイズが大きい予約領域から順に詰め込んで全て詰め込めたら回答候補として確保、詰め込めなかったら棄却。
- 簡易スコア計算(横幅×本数)してベストスコアの場合に回答候補を保管。
一定回数回答の生成に成功したらNを増して分割数を増やしていく。(縦を固定しているため、分割して横幅を減らしたほうがスコアに貢献できるため） - 横幅を長いものは短くしたほうがスコアが低くなるため、移動や1対1交換、1対2交換をランダムに繰り返して全体の横幅の合計が小さくなるよう山登りを行いました。
※１００回やっても１度も成功しない場合は「空き面積に余裕がない場合」の処理を行いました。
空き面積に余裕がない場合
まずは前後日でつなげることを考えず、１日だけノーペナルティーの配置方法を考えてみます。
先程の解法では縦壁の位置を最初に固定していましたが、こちらのパターンでは固定せずに効率の良い組み合わせを積み上げて行って配置を決めます。
例としてランダムな組み合わせとして要求サイズ180030、119500を縦1000のサイズに収めようとすると必要な横幅は300になります。この区画がよい区画かどうか評価したいです。
Seed0922だと各日の全体の空き面積は1282〜3785しかなく、空き面積率でいうと0.1282%〜0.3785%になります。仮に全体の空き面積率が0.3785％だとします。
先ほどの部分組み合わせのの例だと要求サイズ299,530に対して割当サイズ300,000であることから、空き面積率は0.1566%になります。全体の空き面積率が0.3785%なので効率がよい組み合わせになります。全体の空き面積率を下回る組み合わせを複数生成し、合体させることでノーペナルティで条件を満たす区画を作成することができます。
次に各日で縦壁の位置を共有する方法です。
事前に部分組み合わせは生成しておき、各日の空き面積率を下回る組み合わせを列挙しておきます。各日で共通のサイズをあらかじめ計算しておき、bit処理を使いながら、利用できる部品を探索して組み合わせを作成します。
Seed=0034くらいだと全日連結させることも可能です。ただ、全日処理は重いので10日単位で区切って部分的に再作成して良いスコアを選択したほうがスコアは良かったです。Seed0922だと全日連結はできませんでした。部品評価時の空き面積率のしきい値を動的に変えるととか考えてたのですが、時間なくてやりませんでした。
あと、横棒の縦位置の焼きなましはやっていないので、伸びしろは若干あるかもしれません。
Seed=0922 Score=489813
最後に
AHCやりだして1年たちましたが、ビームサーチとか焼きなましをコンテンスト中に使えたことがないので、そろそろ使って実績解除したい。
Discussion