ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

Introduction to Heuristics Contest 参加記録

Introduction to Heuristics Contest - AtCoder

f:id:betrue12:20200629193803p:plain

33位でした。

戦略

焼きなまし法を選択しました。

理由は、問題の性質として解の局所改善がやりやすく、スコアの差分計算を高速化して大量に回せそうだと考えたからです。対して、1手の変更がその後の展開を大きく変えるような問題(落ち物パズルとか)であればビームサーチ等の手法を取る、貪欲やDPなどで近似解や確率的に良い解が得られそうな問題であればそれらの直接的な実装を頑張る、という印象です。

初期解

何通りか試したけど焼きなましたら結局同じくらいになったので適当です。最終提出ではペナルティを無視して各日ごとに  s_{d, i} が最も大きいコンテストを選んだものを初期解としています。

近傍の取り方

まずは「日をランダムに1日選び、ランダムなコンテストに変更する」という1点変更を試しました。次に「コンテスト種類が異なっているような隣り合う2日を選び、コンテストを交換する」という隣接スワップと混ぜるようにしました。

もう少し近傍のバリエーションを増やしたかったなという感想です。コンテスト後に試しましたが、隣接スワップに限らず、例えば  w = 1, ..., 15 をランダムに選んで  w 日離れている2つの日のコンテストを交換するようにするとスコアが伸びました。

差分更新

まず各コンテスト  j と日数  d について、「コンテスト  j を開く間隔が  d 日空いた時のペナルティ総和」を前計算しておきます。

差分を取る前の解における、各コンテスト  j についての「コンテスト  j を開く日を昇順に並べた配列(vector)」を管理しておきます。解を1点変更してこの配列に要素を挿入/削除しようとする場合、その前後にある要素は二分探索で求められるので、それらとの間隔を求めることでペナルティの変動量を計算できます。

最初は set でやっていましたが定数倍が重そうなので vector にしました。vector だと実際に変更を採用する時 の insert/erase で線形時間掛かりますが、これらの操作は定数倍が軽い(らしい)のと、変更を採用する回数よりもスコアを差分計算する回数のほうが多いので、トータルで見ると vector のほうが反復回数が多くなりました。

一応「日  d より前/後ろにある、一番近いコンテスト  j の開催日」を  365\times 26 の配列で常に管理しておけば差分計算が  O(1) なんですが、大して速くなりませんでした。

温度調整

何個か試して適当に初期温度  4000 にしました。私の実装だとこの辺が良さそうですが、近傍の取り方や時間経過による温度減少のさせ方等によって良い値は変わると思います。

テスター・ビジュアライザ

テスターはスコア計算(特に差分計算)があっているかを確認するのに重宝しました。実際結構バグらせたのでなかったら大変でした。

ビジュアライザは(そもそも視覚的に何か分かるような問題じゃないので)よく分かりませんでしたが、なんとなく「ペナルティの係数が大きいコンテストをまんべんなく開催している」「ある程度、各日で利得が大きいコンテストを開くことができている」という確認をすることができました。なんとなく。

振り返り

コンテスト中の成績は  12071 万点でした。上にも書きましたが、本番中に書いていた近傍を少し発展させるだけで  12567 万点、本番の2位相当の点を出すことができました。とはいえコンテスト中にこの「少し発展させるだけ」を思いつき、他の思いつきよりも優先して実装する、ということが難しいのも事実です。

「今のものと実装差分が少なければ、ちょっと変えすぎじゃないかと思うくらい遠い近傍も試してみる」というのは過去のコンテストでも試して、このときは成功しているので、ちゃんと意識していきたいです。

提出コード

本番での最大スコアコード( 12071 万点):Submission #14821684 - Introduction to Heuristics Contest

コンテスト後のコード( 12567 万点):Submission #14839906 - Introduction to Heuristics Contest