AtCoder Heuristic Contest 001

この記事はシステス前に書いている．現在 49,247,218,607 点で 71 位．新レートの詳細は不明だが，アルゴ水色程度の判定が欲しいところ．

解法

素直に焼きなました．評価値は丸める前のスコアを使った．遷移は 2 つ．

1. 矩形を 1 つ選び，適当な直線で分割．要求点を含まないほうを削除したのち，もう一方を拡張．
2. 矩形を 1 つ選び，適当な直線で分割．要求点を含まないほうを削除したのち，別の矩形を拡張．

過程ではスコアが複数あったり，遷移も 5 つほど作成したりしているが，試行しているうちに上記の結果に落ち着いた．各変更の有効度をなんでもいい¹ので把握しておくことは大事．

結局，よく見る「矩形を 1 つ選んで +1 だけ拡張して，他の矩形は重複部分を避ける」遷移は採用していない．理由としては，自分の実装では重複判定に $O(N)$ かけている分，拡張する遷移は総じて重く，±1 程度の近傍では時間内の収束が見込めなかったからである．意外と 5 sec は短い．ただ，最終的な解も時間内に収束しないようで，高速化が肝だったが頑張れなかった．

もう少し付け加えると，必要以上に面積を大きくとるメリットは無いはず（一矩形が得る微妙な点の違いよりも，複数矩形の自由度のほうが重要）という感覚があり，各矩形の面積は基本的に要求と同じかそれより小さくしてある．このとき，面積の増減とスコアの増減が大体一致する．また，スコア計算式は 2 乗を含むため，各矩形はバランスよく面積条件を満たすべきである．以上から，複数矩形の面積が減少する遷移は改善が刺さりにくい．

遷移 1

「矩形を 1 つ選び，適当な直線で分割．要求点を含まないほうを削除したのち，もう一方を拡張．」

分割のみを一遷移とするとスコアが確実に悪化するので，拡張と抱き合わせている．拡張する方向は任意だが，実装では切る方向と同一（図では矩形 1 を水平に切ったので，水平方向に拡張）とした．拡張量は上限を求めておいて三分探索すると最適がわかる．上限を求めるパートに工夫がないので，$O(N + \log W)$．$W$ は盤面の一辺．

分割しないでただ拡張するパターンもあったが，各矩形の面積は基本的に最適－ε で，分割しないと大抵のケースで拡張量 0 になる感じがあり採用しなかった．

遷移 2

「矩形を 1 つ選び，適当な直線で分割．要求点を含まないほうを削除したのち，別の矩形を拡張．」

「この矩形は明らかに邪魔」みたいなパターンが多かったので採用．拡張時に全矩形を見てしまうと $O(N\log W)$ だが，この遷移で恩恵を受けるのは消滅部分と接している矩形のみなので，そこで枝刈りする．

（思いついたが）やっていないこと

• 重複を許す遷移
  • 罰則の決め方がいまいちわからず，失敗すると 0 点なので安全側に倒した．
  • あとで「係数を動的に変更する」方法を見かけて確かにとなった．
• 条件を満たさない矩形の作成
  • 一つ犠牲にして他でスコアを稼げるケースはもちろんあると思う．
  • 一度条件を満たさなくなった矩形を再度復活させるのは，スコアの期待値としてかなりマイナスで実装する気にならなかった．
  • 上位のスコア的にそんなことしてないだろとも思った．
• スコアの工夫
  • 本番スコア + サブスコア みたいなことをしていた．
  • 縦横比
    • 向きが揃って良いと思ったが，幅 1 の矩形がたくさん出現した挙句，拡張すると面積が異常に増えるので遷移が成功しにくい．
  • 要求位置と頂点のマンハッタン距離
    • これが優先されると BLF 法のようになると思っていたが，そんなことはない．
• 高速化
  • left[i] := 左上の頂点の x 座標が i である矩形の id
  • 重複判定が軽くなって嬉しいつもりが，$N \sim 50$ 程度だと普通に見たほうが早く，$N \sim 200$ で等速ぐらい．
  • 実装が下手だっただけかもしれない．

（思いついていない）やればよかったこと

• 多点スタート
  • 初期解が優れていることのありがたみを忘れていた．
• 参加記や上位の提出をあまり追えていない…

その他

• 初 Rust．
  • 実装がそこまで複雑にならなかったのであまり恩恵を感じなかった．
  • むしろ C++ で書いていたら収束してたんじゃないかという不安が強かった．
  • 書きにくさとかは全くなく，そこは嬉しかった．
• 最初 2 sec だと思って提出していた．
  • 気付いて提出し直したが，特にスコアは変わらなかった．
• ツールを少し作った．
  • ハル研プロコンのスコアマップを気に入っていたので，そこに生成した svg をかぶせた．
  • スコアが露骨に低いケースを潰すのに役立つ．
  • 焼きなましそのもののビジュアライザが流れてきて羨ましかったので，次回以降の課題．
• 久々のブログ
  • 今更気づいたがスマホから見ることを考えていないレイアウト．ごめん…

Tweet comments powered by Disqus