Marathon Match 107

ラソンマッチ始めてみました。問題文

問題概要

縦 H 横 W のグリッドがあります。各マスに 9 以下の非負整数が書いてあります。マスのいくつかを塗って、塗られたマスに書いてある数の合計を大きくしてください。ただし 縦 h 横 w のどの長方形も塗られたマスを Kmin 個以上 Kmax 個以下含むようにしなければなりません。

とりあえず正の点をとる方法

h×w の subgrid の中から Kmin 以上 Kmax 以下の個数を塗る任意のパターンを作る。左上から順番に塗るとか、何でもいい。それを H×W に周期的に拡張すれば制約を満たす塗り方ができて正の点が得られる。

その後のいろいろ

初期解が作れるようになったので、とりあえずこれを動かして山登りをしてみた。何箇所か塗る/塗らないの状態を flip したものを近傍にした(最終的には二箇所だけにした)。提出してみたら 930070.87。この時点ではまだいろいろ効率のよくない部分があったが、高速化はいつでもできそうなので後回しにして、方針を改善できないか考え直すことにした。

初期解を作るときに点数が高くて端に近いやつを優先的に塗る(マスの点数をそのマスを含む subgrid の個数で割った値を優先度にする)ようにしたら、それだけで最初の山登り解と同じくらいのスコアが出ることに気付く。ただ、これだけだと問題があって、たまに制約を満たすものが見つからないことがある。中央付近があまり塗られてなくて周辺がたくさん塗られすぎている状態になってしまった場合、追加で塗るマスをどう選んで制約を満たせなくなる。例えば H = W = 4, h = w = 2, Kmin = 1, Kmax = 2 で以下のような配置になった場合とか。

 ****
 ....
 ....
 ****

そこで、うまくいかなかったらちょっとランダム性を入れて何度か作り直すことにした。それでもだめだった場合は周期的な解の中で一番スコアが高いのを作る。これは以下のようにすれば作れる。まず 0 <= i < h, 0 <= j < w の範囲にある各 (i, j) について (x, y) = (i, j) mod (h, w) になるような (x, y) のマスの値の総和を求める。和が大きいほうから Kmax 個まで (i, j) を塗って、それを周期的に全体に拡張する。

5×5 の場合は全探索で間に合うのでそうした。もう少し大きいケースも枝をちゃんと刈れば厳密解が出せたかもしれないがやらなかった。このあたりで 958728.41

高速化と焼き鈍しをやって、細かいことをいろいろやって、焼き鈍しのパラメータ調整をして 989241.86

ところで貪欲解の構成に成功した場合は焼き鈍しをやってもほとんどスコアが上がっていないケースが多いようだけどこれはどう解釈したらいいんだろうなあとずっと思っていた。

学びと反省

  • 時間を測るのに chrono を使ったら TLE が出た。調べてみると、rdtsc を使うとよいという情報が出てきたので真似してみたらまあまあいい感じになった。50ms ぐらい余裕をみておかないと TLE するときがあるみたい?
  • 盤面が制約を満たしているかどうかの判定をたくさんやってるので segment tree を使ったら速くなるだろうと思ってやってみたら遅くなったので悲しみを感じた。(落ち着いて考えてみると調べる矩形が O(HW) 個あるので全部で O(HWlogHlogW) になっていて遅いに決まっているのでは)