AtCoder Heuristic Contest 001 - AtCoder
プレテスト時点で 48,139,425,583点 の 237位 でした。 やったことをざっと書きます。
解法
概説
- 面積１で全広告を希望位置に設置後、希望サイズ以上になるまで広げる形で初期化
- スコアを基準に焼きなまし。近傍は１広告を四方いずれかに１伸ばす
で、0000.txt の結果が下画像のような感じ。
提出コードはこちら https://atcoder.jp/contests/ahc001/submissions/20923126
初期化
まず面積１で全広告を希望位置に設置し、 その後、四方を順に選択し、希望サイズに達していない広告達を他広告にぶつからずに１伸ばせるなら伸ばす、 を対象広告がなくなるまでやりました。
初期化の時点で89G点くらいになります。
焼きなまし
スコア変化をそのまま判定基準に使いました。温度変化は 1e-3 ~ 5e-6。
近傍は、
- 対象広告
- 方向(四方)
- 伸ばすか縮めるか
をランダムに選び、その操作を長さ１だけ実行、としました。 伸ばす際に他の広告にぶつかるなら、その分ぶつかった広告を縮めます。
振り返り
考察過程
割と序盤に考えた方針を高速化したものが最終提出になる形だった。 １広告0.96点くらいに収束することは調査済みだったので、当然ここに着地するよなという感じ。 局所を抜けられてなさそうな感覚はとても有ったのだけど、打開策が思い浮かばなかった。
考察がここより進まなかった原因として、スコア計算式を勘違いしていた(希望面積に近いほど、面積1差のスコアへの影響が大きいと思っていたけど逆だった。コンテスト後に知った)ことが大きかった気がする。 問題文はきちんと読み込むべきってのと、出力結果や上位のスコアに違和感は感じていたので、その辺の感覚に沿って精査すべきであった。。
もう一個考察が進まなかった大きい要因として、ビジュアライザーとか作らず(れず)、近傍を感覚で考えるだけになっていた、とかがある気がした(を、コンテスト後のTLでビジュアライザー自作例を見て思った)。 次回までには対策しておきたい所。
他の方の解法を見て
- 上述した通り、ビジュアライザーは要るよなって思った。
- 広告を壊して作り直す近傍を見かけてなるほどなと思った。局所抜けるには確かにそれくらいのことが要りそうに感じる。
- スライド移動が、比較的簡単に実装できそうかつ有効そうなものに感じた。これはコンテスト中に思いつきたかったなあという気持ちに。
とかをTLをざっと見て思った。まだブックマークしただけであんまり追えていないので、これからゆっくり見ていきたいお気持ち。
