乐胖代购免代理版

得点率97.4％で130位でした。

f:id:betrue12:20210320121932p:plain

seed値0の入力に対する解のビジュアライザ出力です。

f:id:betrue12:20210320135516p:plain

考察

スコアの計算式を見ます。各企業が指定する1マス（以下、指定マスと呼びます）を含めないとその企業からの点は貰えないので、まずこれは含める必要があります。

企業ごとの得点は希望面積 $r_{i}$ と実際の面積 $s_{i}$ の単純な比ではなく、 $s_{i}$ が $r_{i}$ に近づくにつれて伸びが緩やかになります。例えば面積を希望の50％確保すると75％の点が貰えるので、面積が足りなくても全ての企業からまんべんなく点を得たほうが効率が良さそうです。

そして面積が $r_{i}$ を超えてしまうと今度は得点が下がるので、面積が $r_{i}$ を超えることにほとんどメリットはないことが分かります。

最初は希望を叶えるのが難しい企業、つまり希望面積が大きく指定マスが密集地帯にあるような企業は諦めたほうがトータルで良いスコアになるのではと思うこともありました。しかし順位表の上位陣の得点率がコンテスト初期から98％以上と非常に高く、1つの企業の得点が0％になるだけでこの得点率はほぼ絶望的なので、その可能性はないと判断しました。

方針

焼きなまし法です。初期解は指定マスだけからなる $1\times 1$ の正方形として、スコアは問題通りに計算しました。

近傍は3種類使い、それぞれ試す頻度を変えています。近傍1を1回実行する単位をイテレーション1回と呼ぶことにします。

近傍1

1つの企業ID $i$ と4方向のうちの1つをランダムに選び、長方形をその方向にマス1つ分伸ばします。盤外に出る、面積が $r_{i}$ を超える、他の長方形と被る場合はその近傍を諦めます。

面積を広げてスコアを高めるための基本となる近傍です。イテレーション1回につき1回近傍を取ります。

近傍2

1つの企業ID $i$ と4方向のうちの1つをランダムに選び、長方形をその方向にマス1つ分伸ばします。盤外に出る、面積が $r_{i}$ を超える場合はその近傍を諦めます。しかし他の長方形と被っている場合は、押し潰すようにそちらの長方形をマス1つ分縮めます。縮めることで指定マスが含まれなくなってしまう場合は諦めます。

スコアを悪化させる可能性がある近傍です。最初は近傍1に、20％の確率で長方形を縮める方向に近傍を取るという処理を入れていたのですが、縮めたマスを他の企業が使わないと結局スコアが増えないので、こちらの取り方に変更しました。

イテレーション10回につき1回近傍を取ります。

近傍3

1つの企業ID $i$ と、4方向の優先度を決める $\lbrace 上, 下, 左, 右\rbrace$ を並び替えた順列をランダムに選びます。その企業の長方形を指定マスのみの1マスに初期化し、優先度の高い方向から順番にその方向に伸ばせるだけ伸ばします。「伸ばせるだけ」とは、盤外に出ず、面積が $r_{i}$ を超えず、他の長方形と被らないように最大限伸ばすことを指します。

後半に動きづらくなった長方形を大きく動かす目的で導入しました。制限時間の半分が過ぎた以降、イテレーション1000回につき1回近傍を取ります。

高速化など

特にやっていません。スコア計算は近傍を取ったときに変更された企業のものだけを差分計算しました。他の長方形と被っているかの判定は自身以外の $n-1$ 個全てに対して愚直にやりました。

seed値0の入力（ $n=52$ ）に対して、コードテストでイテレーション5400万回くらい回っていました。

振り返り

最初に貪欲解法を考えてみたものの良いものが思い浮かばず、 $1\times 1$ を初期解としてただランダムに伸ばすだけの焼きなまし解法からスタートして、近傍の取り方を考えていきました。

上位陣との得点の離れを見て、焼きなまし以外の解法を色々と考えたものの、シンプルな焼きなましを超えることができませんでした。お約束としてビームサーチも考えてみたけど、遷移先の候補をどう取れば良いか全く分からず撃沈しました。

近傍の取り方のアイデア、逆に言うと改善できそうな悪い所を見つけるためにビジュアライザ出力は非常に有用です。しかし今回は画像を眺めても、ここをこうすれば良くなるというアイデアをあまり思いつけなかったのが厳しい点でした。「この長方形、縦じゃなくて横に伸ばしたほうが面積大きくなるのに」と思うことはあり、その結果として近傍3が追加されました。近傍3を入れたのは最終日で、それでスコアが少し伸びて今の順位に落ち着きました。

変化が大きすぎると思うくらいの近傍も含めたほうが良い、という経験則はありましたが、単純に伸び縮みの長さを増やしたり乱数で決めたりするだけでは逆にスコアが悪くなってしまいました。もっと近傍の取り方そのものを工夫して多様な変化を作るべきだったと思います。

とはいえ最終日の頑張りで得点率が96.2％から97.4％くらいまで上がり、最終順位が想定で100くらい上がっているので、この粘りは今後も大事にしていきたいですね。

f:id:betrue12:20210320164913p:plain