AtCoder Heuristic Contest 012(AHC012) -AtCoder 10th Anniversary- 参加記

問題

結果

99,533,533点で2位。パフォーマンスは3202で赤パフォ。嬉しい！

seed=0, score=981520

解法

線の引き方

円や斜めの線を考えるのは難しいので、縦横の線のみを引いて、グリッドで管理する。縦線なら (px, py) = (x, -1e7), (qx, qy) = (x+1, 1e7) のようにすることで、イチゴが直線上にくることがなくなる。

縦と横の線を何本引くかだが、円の内部に人数と同じくらいのピースが出来て欲しいので、縦本数 x 横本数 が 合計人数 * 4 / π に最も近くなるようにする(円の内部にイチゴは沢山あるので、イチゴ0個のピースはあまり出来なさそう)。隣接の線が十分近づけばイチゴ0のピースが増えるので、グリッドが多めに作られるようにした方が良さそう、と途中で思ったがスコアは下がった。

データの持ち方

以下のデータを管理する。

  • 各グリッドにイチゴが何個あるか
    • 2次元配列num[*][*] で管理すると、線を1本移動させた時に変化があるのは num[i-1][*] (or num[*][i-1]) と num[i][*] (or num[*][i]) になる
  • 1〜10個のイチゴを含むピースの個数
  • 各x(y)座標に存在するイチゴのy(x)座標を昇順にソートしたもの

焼きなまし

初期解は均等な幅で線を引く。

近傍は線を1本ランダムに選び、-30〜30移動させる。イチゴの個数の変化は、座標管理しているのでしゃくとり法(?)で O(移動量 * 線の数+所属が変わるイチゴの数) で計算できる。

// 縦線を正の方向に移動させる部分のコード
for (int i = v[r].qx; i <= v[r].px+m; i++) {  // m が変化量。iが所属が変わるx座標
    int h_idx = 1;  // しゃくとりで管理するインデックス
    for (const int _y : xp[i+R]) {  // x座標がiであるイチゴのy座標
        while (h[h_idx].py < _y) h_idx++;
        // vdは変化量を管理する配列。実際に遷移する時に個数を管理する配列に変化量を足す。
        vd[0][h_idx-1]++;  // イチゴの個数を増やす
        vd[1][h_idx-1]--;  // イチゴの個数を減らす
    }
}

評価値は ケーキが配られなかった人数 + 1〜10個の余ったピースの数 / 100。低いほど良い。最初の項だけなら素のスコアで、余って無駄なピースも減って欲しいので第2項も加えたがスコアは微増だった。

差分計算はジャッジサーバで16M回くらい。手元だと22M回くらいで、焼きなましの最適な初期値が手元とジャッジサーバで違うようで、提出で調整していた。

差分計算について[追記: 2022/7/5]

図のようにi番目の縦線をx=10からx=13に移動させることを考える。numが各グリッドに含まれるイチゴの個数を管理する2次元配列で、移動によって図のように値が変化する。この変化を高速(大体O(所属が変わるイチゴの個数)くらい)に計算したい。

  • xp[t] = x座標がtであるイチゴのy座標を昇順にソートしたリスト

となるデータを前計算で用意しておく。図において、x=10からx=13に移動させているので、所属が変化するイチゴはxp[11]とxp[12]を見れば全て分かる(簡単のためx=10,13にはイチゴはない)。あとはx座標ごとに、リストの手前からy座標が小さい順に、縦方向にどのグリッドに属するかをしゃくとり法の要領で計算していく。しゃくとりの頭がイチゴのy座標で、おしりがそのy座標を超えない一番上の横線、となる。

これで高速に差分が計算できるが、実装ではさらに個数の変化量を一時配列に入れておきnumの更新は遷移が採択された時に行う。numの更新を直接行ってしまうと、遷移が採択されなかった時に元に戻す作業が発生して無駄が生じる。

時系列

問題読み&考察 (0:00〜0:30)

まあ、線を移動させて焼きなましだろうなと思う。斜め線引いた時個数計算するのは自力では無理。テスターから引っ張ってくれば計算できるだろうけど、それで戦えるはずがないので却下。合計人数が最大1,000人でグリッドが50*50=2,500作れるので縦横で良さそう。初期解や高速化案を考える。

実装(0:30〜2:20)

頑張って実装する。山登りで微妙なスコアが出て、数行変えて焼きなましにするとスコア爆増するの、何回やっても気持ち良い。

初提出(2:22)

99.2M点でぶっちぎり1位でビビる。

提出2(2:43)

評価関数変更して微増。

パラメータ調整(〜4:00)

ひたすらパラメータ調整。焼きなましの初期温度はかなり低めにした方が良かった。

感想

2位で初赤パフォで出来過ぎた。1位の99.78Mはどうやっても勝てなかっただろうから悔いなし！正直なところ橙が限界で赤いくのはもう無理だと思っていたけど、上振れれば到達できることが分かったので頑張りたい。あとパフォ3000オーバーを3回位出せばいけるっぽい。何年かかるんだ…？