AHC001 参加記

暫定 58 位で、システムテスト待ち

方針

• とりあえず常に各広告が (x, y) を含むとしよう。さもなければ少なくとも 0.5 点の損失となるし、N の分布からして平均的に1点はありそう。正確に計算できると思うが、よくわからなかった。実験してもよかったが、そこまで重要な数値ではないと思う。
• 常に s ≦ r としてよい。そうじゃないほうがいいケースも稀にあるが、たぶんほぼ無意味、ほんとか？と思って電車の中からスマホでそこだけ変えて再提出した。ちょっと伸びました。よって常に "ほぼ" s ≦ r としてよい。（幅 w のときに、wh < r < w(h+1) なる h が存在して 1-wh/r > w(h+1)/r-1 のとき、とか。）
• とりあえず上記を満たしたまま最小の広告たちから山登り。機械的に焼きなましに移行する。最序盤は1位だった瞬間もあった。嬉しいねぇ。
• 変形操作は最終的なものだけ挙げると、「ある辺を内側に動かして、隣接するいずれかの辺を外側に動かす」「全体を動かす」の2択。実際には、内側に動かすのは 確率=現時点でのスコア でやった。変形量は 0〜可能な最大値 の範囲で一様ランダムに。0含めたほうが良かったんですよね。謎。分布がいい感じとかそういうアレかな。衝突チェックは毎回全部やった。
• 1-(1-0.9)² = 0.99 で、min(s/r) の最大化が肝要なことに気づく。（ここですべての広告が点 (x, y) を含むのはやはり正しそうだと思う。）どうするよ……と思ったが、r を ceil(min( (t/1.5+0.4)r, r) ) (t は時刻で、t in [0, 1])にすると良い感じだった。なぜかは、知りません……、そこまで上手くいっている気はしなかったが、いっか〜という感じ。

やってないこと

• 基本的に Introduction to Heuristics Contest の解説を頼りにやっていたのだけど、巨大近傍法を考えることはできず。
• ビームサーチとかあり得るのかな。端っこから矩形充填みたいな感じでやっていく？
• 最初から充填された状態でやって、最後にオーバーしたやつを減らすのはかなりいい方針にみえる。上位こんなんなのかなー、ふつうに難しくて、できず。