arimattiの競プロ精進日記

競プロ問題の解法を記録していきます

estie プログラミングコンテスト2022(AtCoder Heuristic Contest 014)参加記

はじめに

estie プログラミングコンテスト2022(AtCoder Heuristic Contest 014)に参加しました。
結果は、プレテストで 24 位、システムテストで 21 位と過去最高順位を大きく更新することができました。せっかくの機会ですので参加記を残しておきたいと思います。

問題

atcoder.jp

方針

焼きなましをしました。解を一部破壊して構築しなおす、というのを繰り返します。
各試行において、ランダムに四角を 4 個選び依存するものを含め削除したあと、評価値に従って四角を作れるだけ作ります。

初期解の作成

同じ辺は二度使えないので、辺を多く使う大きな四角は不利だと考え、小さい四角を優先的に置いていくことにしました。

以下のデータを管理します。

  • 各グリッド点が印付きか否か
  • 各グリッド点の 8 方向への最寄り印付き点の座標
  • 各辺が使用済みか否か
  • 候補となる四角の集合(priority_queue を使う)

最初に候補となる四角を全列挙します。
印のついた点を p3 として全探索します。d 方向にある点を p4、d 方向から時計回り 90 度方向にある点を p2 とします。幾何的に点 p1 の座標は求まります。使用済みの辺を使用していないか、各辺上に別の点が存在しないかをチェックし、違反していなければ priority_queue に突っ込みます。

priority_queue から候補となる四角を取り出し、点を打つ → 新たに発生する四角の候補を priority_queue に突っ込む、を四角の候補がなくなるまで繰り返します。
取り出したタイミングで再度違反チェックをかけます。突っ込んだタイミングと取り出したタイミングで盤面の状態が変わっているためです。
新しく点を一つ打った際に新たに発生する四角の候補は以下です。

  1. 新しく打った点 を p3 として使う四角
  2. 新しく打った点 を p2 or p4 として使う四角

1. は上記の全列挙のときと同じ方法で見つけることができます。2. は打った点から 8 方向に最寄り印付き点を探し、見つかった点を p3 とすればあとは 1. と同様です。

焼きなまし

解の部分的破壊
四角をランダムに選び削除します。それに依存する四角も削除します。
当然ですが、「依存する四角」は「削除する四角」より ans 配列上後ろのインデックスにあります。「削除することになった依存する四角」に「依存する四角」はより後ろのインデックスにあります。従って、四角を削除した際の解は以下の手順で作成できます。

  • 削除する点の集合を管理する
  • ans 配列を前から見ていく。四頂点のいずれかが削除する点の集合に属していれば、ans[i].p1 を削除する点の集合に加え、ans[i]を削除する

実装において、削除する点の集合の管理に set を使うと遅かったので配列を使いました。また、ans の削除は実際は削除せず、削除フラグを立てておき、削除フラグが立っていない要素を tmpans に詰めなおしました。ソースコードは以下のようになりました。

/* ans配列のidx番目の四角を削除する */
/* ※変数pxは 2次元座標を1次元に置き換えた値とします ( (i,j) → i*n+j ) */

// 削除する点の座標にフラグを立てる(配列del_p1は焼きなまし中使いまわす)
del_p1[ans[idx].p1] = true;

// ans配列の削除するインデックスにフラグを立てる
vector<int> del_ans(ans.size());
del_ans[idx] = true;

// 削除した点の座標位置を記録しておく
vector<int> marks;
marks.emplace_back(ans[idx].p1);

for (int i = idx+1; i < ans.size(); ++i) {
  // 削除する点を使用している四角かを判定する
  if (del_p1[ans[i].p2] || del_p1[ans[i].p3] || del_p1[ans[i].p4]) {
    del_p1[ans[i].p1] = true;
    del_ans[i] = true;
    marks.emplace_back(ans[i].p1);
  }
}

// del_p1に立てたフラグをおろす
for (auto mark : marks) del_p1[mark] = false;

// 削除する四角は除きtmpansに詰める
vector<Action> tmpans;
for (int i = 0; i < ans.size(); ++i) {
  if (!del[i]) tmpans.emplace_back(ans[i]);
}

削除の起点となる四角は複数のほうがスコアが良くなったので、最終的には 4 つランダムに選びました。ただし、削除する四角が多すぎると処理時間がかかり、また accept 率が低そうだったので 40 個以上の場合は選び直しとしました。

解の再構築
印のついた点の集合は set 等で管理する必要はなく、入力で与えられる M 個の点 + tmpans 内の p1 で列挙できます。初期解の作成と同じ要領で貪欲に四角を作れるだけ作ります。
ただし、焼きなましの試行ごとに貪欲の評価値を以下からランダムにひとつ選択しました。

  1. 四角の面積のマイナス値
  2. 四角の面積のマイナス値に乱数をかけたもの
  3. 追加する点の重み
  4. 追加する点の重みに乱数をかけたもの
  5. 追加する点の重みを四角の面積で割ったもの
  6. 追加する点の重みを四角の面積で割ったものに乱数をかけたもの
  7. 完全ランダム

※ここでの乱数はすべて 1 ~ 3 の整数値です

コンテスト時の時系列

(後から書いたので記憶の改ざんがあるかもしれません)

1-2 日目(9/17 - 9/18)

問題文を読む。難しい。とりあえずの提出をするにも割とハードルがあるなぁという感覚。
ちょっと時間をかけてデータの持ち方などを考えることにする。

3 日目(9/19)

共有されるビジュアライザでは点がぎっしり詰まっている方が高得点を取れそう。小さい四角を貪欲に詰める実装を書くことにする。案の定バグだらけのコードができたが、バグ取りをがんばり提出。33M 点を得る。スタートとして悪くなさそう。

4 日目(9/20)

「小さい長方形を順番に作る」に若干のランダム性を加え時間いっぱい解を生成する。その中で最も良い解を出力することとした。これで 40M点を達成。

5 日目(9/21)

何をすればいいのかわからなくなってしまった。ビジュアライザのマニュアルモードで考察しようとするも、マニュアルでやるの難しすぎて何もわからない。現時点で「割りと良い初期解を作れている」という見方をすると焼きなましってできるのかなぁ。でも焼きなますって言っても何をするのって感じ。

6 日目(9/22)

仕事の合間に閃いた。現状やっていることは解を一から作り直す山登りである(山登りとは言わないかもしれない)。では、解を一部破壊してまた作り直す山登りをすればどうか。でも依存関係をほどく実装重そうだし、スコア伸びる自信もない。

すきま時間でヒューリスティック関連の記事を漁った。
chokudaiさんのブログを読んだことがこのコンテスト中のハイライトだったかもしれない。
chokudai.hatenablog.com

コンテストが終わったら、「もうやりたいことはやり終わった」と言えるレベルでないと、コンテストに参加したとは言えません。ここで躓いている人は論外です。

ん-、思いついたからにはやらなければならないようだ。
帰ったらがんばって実装してみるか。

帰宅後、山登りを書いた。40M 程度。スコアは伸びていないけど、感触は悪くない。局所解にはまっているだろうから焼きなましにすればスコアは伸びそうだ。翌日は休みなので、焼きなまし実装結果を楽しみにして就寝した。

7-9 日目(9/23 - 9/25)

焼きなましをした。スコアは 51M を超えた。伸び具合にびっくりしてしまった。19 位で 1 ページ目入り。時間を延ばすとスコアがかなり上がるので当面高速化をがんばることにした。

細かい部分の修正と高速化でどんどんスコアが伸びる。めちゃくちゃ楽しい。
自分がざっと書いたコードはあまりにも高速化の余地がありすぎる(追加する四角の辺が使用済みでないかのチェックをなぜか二重で行ったりしていた)。馬鹿だなぁと思う反面、高速化の余地が残っているのはモチベーションにつながっている気もした。

スコアは当面の目標になっていた 60M を超え、順位は 9 位になった。

10-13 日目(9/26 - 9/29)

高速化のネタも尽きてきて、苦しくなってきた。何かアイデアが欲しい。

詰まったときはビジュアライザをよく見ると良いらしい。こういうときに自作ビジュアライザを作るスキルがあると捗るんだろうな。
地道に高得点が得られる場合とそうでない場合を出力して見比べてみる。

なるほど高得点が取れる場合はピラミッドを形成しながら外に張り出しているようだ。ピラミッド形成メカニズムを詰めてみよう。

14 日目(9/30)

休暇を取っていたのでなんとか進捗を生みたい。
ピラミッド形成メカニズムを整理する。ピラミッドを形成するには菱形が一定間隔で並んでいる必要ありそうだ(コンテスト後に最小四角を市松模様に配置すればいいことを知る)。この配置を良い配置としてボーナス評価をしてみることにする。スコアは悪化した。うまくいかなさそうだったので諦めてしまった。ここを詰めるのは当たり筋だと強く感じていたのに詰め切れなかったのは反省。

15 日目(10/1 最終日)

最終提出に向け、パラメータの調整をし、ローカルテストを回す。休憩がてらコンビニに行く途中で、解の破壊プロセスで高速化改善余地があることに気づく。ローカルでの平均試行回数はこれまでの 2 倍近くの 15 万回となった。期待するほどのスコア上昇はなかったけど、最後にベストな提出ができてよかった。暫定順位は 24 位で 1 ページ目には残れなかったけど、それでも十分な満足な結果を残せてコンテストを終えることができた。

感想

今回もとても楽しい問題でした。焼きなましが当たって順位がジャンプアップしたときは興奮で心臓バクバクでした。後半は焼きなましに持って行ったあとの引き出しがなくほぼ高速化するだけで終わってしまいました。詰まったときにパラメータ調整に走ってしまうのも反省ですね。解説放送であった、点が持てる残枠といった問題特有の考察を深くできるようになりたいです。終盤は何をやって結果がどうだったかを思い出せず混乱しがちだったので、日記をつけるのも大事かなと思いました。

最後に

スポンサーの estie さん、writer の wata さん、参加者の皆様ありがとうございました。
最初から最後までのめりこめる最高に楽しいコンテストでした。次のコンテストも楽しみにしております。
最後まで読んでいただきありがとうございました。