TERRYのブログ

最近は競技プログラミングにお熱。

Sponsored Link

AtCoder Heuristic Contest 012 (AHC012) 解説

AHC012お疲れ様でした。98,254,833点で11位です。

今回も解説を書きます。

ビジュアライザ (seed=0)

問題概要

AtCoder 10周年おめでとう🎂

イチゴの数がいい感じになるようにケーキを切り分けてね。

atcoder.jp

方針

斜めに切るのは難しすぎるので、縦横にグリッド状に切っていくことにしました。

切る位置を少しずつ変えていくだけの比較的素直な焼きなましを行って、よい切り方を探索していきます。

焼きなましの様子 (seed=0)

解法

初期解の生成

縦横の分割数 m は、 k^2\ge \sum_{d=1}^{10}a_d となるような k を求めて、そこからちょっと余裕を持たせた m=k+3 としました。 3 という数字に深い根拠はなく、適当にいろいろ試して良かった数字を採用しています。*1

この分割数で縦横方向に等間隔に切りました。

解の持ち方

差分計算を行うことを考え、以下のデータを持つことにしました。

  • 縦方向に切断する x 座標の配列
  • 横方向に切断する y 座標の配列
  • 各イチゴがどのピースに存在するか管理する2次元配列
  •  n\ (0\le n\le N) 個のイチゴが載っているピースの個数を管理する配列

切断数は初期解のものから固定としたので、各配列の長さは固定です。

焼きなまし中に差分計算を行って高速化するため、各イチゴがどのピースに存在するかについて管理していきます。イチゴがちょうど切断線上に来るケースがあるためややこしいのですが、縦 (2m-1)\ \times(2m-1) の2次元グリッドを考え、左(下)から l 番目のピースの番号を 2l 、左(下)から l 番目の切断線の番号を 2l+1 と定め、2次元グリッドの左から i 、下から j 番目のピース(または切断線上)に含まれるイチゴの座標の集合を S[i][j] としました。*2

初期解を生成した後に、各イチゴの x,y 座標それぞれについて二分探索を行うことで、 O(N\log m) でこのグリッドを初期化することができます。

焼きなまし

「ランダムな切断線を選び、 \pm100 の範囲(ただし隣り合う線を跨がない範囲)で座標をずらす」という近傍のみを使って焼きなましました。この時影響のあるイチゴは切断線上とその左右(または上下)にあるものだけなので、そこだけ差分計算を行うことで高速に更新していくことができます。手元だと3秒でだいたい220万回くらい(AtCoderのコードテスト上では160万回くらい)回っていました。

評価関数

焼きなましを行う際、評価関数が \min(f,g) のような形だと評価値が平坦となる領域が多くなり、解がブラウン運動をするだけでうまく焼けないことが多いです。*3 そこで生のスコア S に加えて、「目的のピース数 a と現在の解のピース数 b について、 a_db_{d'} との間にコスト (d-d')^2 の辺を張ってマッチングを行ったときの総コスト C 」を考慮しました。

これは最小費用流で解くと死ぬほど遅い*4 のですが、辺が交差しないように貪欲に割り当てるのが最適なので、以下のような処理にすることで高速に求めることができました。

a = 目的のピース数の配列
b = 現在の解のピース数の配列

# 適当にinfで埋める
b[11] = 100000

# 総コスト
C = 0
j = 1

for i in range(1, 11):
    while a[i] > 0:
        while b[j] == 0:
            j += 1
        
        count = min(a[i], b[j])
        a[i] -= count
        b[j] -= count
        C += (i - j) * (i - j) * count

このようにして総コスト C を求めた上で、 S-1000C(1-t) を焼きなましの評価関数としました。ここで、 t\ (0\le t\le 1) は焼きなましの進行状態を表す変数で、焼きなまし開始時点を0、焼きなまし終了時点を1としています。「序盤はざっくりピース数を寄せて、終盤は生のスコアを最大化したい」みたいなお気持ちです。

コード

以上を実装して提出すると、98,254,833点が得られました。

atcoder.jp

日記

コンテスト中に考えたこと・やったことを時系列順に並べました。ここだけ常体です。長いので流し読み推奨。

AtCoder Marathon Replay

方針を立てる(〜0h10m)

幾何!?無理では……と絶望しながらビジュアライザを見てみると、イチゴが無限にあるので凝った切り方をしなくても良さそうだと分かる。グリッド状に切って焼いて差分計算を頑張るのが良さそう。

焼きなましを書く(〜1h13m)

まずは差分計算を行わずにナイーブな焼きなましを書く。切断数はとりあえず 50\times50 で固定。さすがに重くて、手元実行で1万回くらいしか回らない。提出すると70.6M点で92位。

切断数を変える(〜1h28m)

ちょっと試したところ、切断数は多すぎない方が良いらしい。多くしてもイチゴ0個のピースが増えるだけかなと思っていたが、線を跨がないという制約を入れているため焼きなましで動かしづらくなるのだろう。調整すると92.1Mで4位。

差分計算を実装する(〜2h48m)

かなりやりたくないが、頑張って差分計算を実装する。案の定めちゃくちゃバグらせた。

頑張った甲斐があって220万回くらいは回るようになった。97.6Mで6位。

評価関数等の調整(〜4h00m)

生スコアのままでは上位は狙えないと思われたので評価関数をいじる。マッチングをフローでやると1桁遅くなって使い物にならなかったが、線形アルゴリズムに書き換えた上で重みを時間とともに減らすようにすると微妙に伸びた。98.2Mで11位フィニッシュ。

終了前5分の段階で縦と横の分割数に差を付ける(アスペクト比を大きくする)ことを思い付いたが間に合わず。

できなかったこと

  • アスペクト比を変更する
    • コンテスト終了後に試してみたら99.2Mまで伸びた。もっと早く思い付けていればなあ。
  • カットする線を 10^{-9} だけ傾けることでイチゴを切らないようにする
    • 全く思い付かなかった……。効率上がるし実装も軽くなるし良いことずくめ。
  • 座圧して累積和でイチゴの個数を管理
    • こちらの方が高速に計算できそう。なるほど……。

感想

とりあえずは11位という順位が取れてよかったです。割と短時間で当たり方針を引けるようになったのも成長かも。あと10分時間があれば……というたらればはあるのですが、まあこれが今の実力ということで。

問題文(というか添付されている図)を見た第一印象としては重そうな問題でしたが、理解できてしまえば短期コンらしい問題でしたね。逆に凝った切り方をしないといけないような問題インスタンスを考えて、長期コンとして取り組んでみるのも面白そうです。

最後になりますが、AtCoder 10周年おめでとうございます!

AtCoder歴2年なのでイチゴ2個のケーキください!

*1:ケーキは円形なので、正方形グリッド上でピッタリな分割数だと足りないのはそれはそうなのですが、コンテスト中はそこまで頭が回りませんでした。

*2:イチゴが絶対に切断線上に来なくなるような切り方があると知るのはまた別のお話……。

*3:と私は理解しています。もしかしたらそんなことないかも。

*4:「全頂点間に辺を張るのではなく、隣り合う頂点間にのみ辺を張る」などの工夫をしても焼きなまし中にやるには重いです。