Introduction to Heuristics Contest 参加メモ

Introduction to Heuristics Contest

B,Cの2完で2点でした！

……？？？

A - AtCoder Contest Scheduling

長いので問題ページ参照

公式の解説がメチャクチャ詳しいので、問題ページのリンクから読みましょう。

以下は終了後の提出。

1日目から貪欲で埋めた後に、どの日をどのコンテストタイプに変更するかをランダム抽選で山登り。

変更時のスコア差分を計算して、更新許容閾値を超えたら更新。閾値は-3000→0にループが進む毎に線形に増やしていく。

これで最高 115,832,333 点。

その後、以下の変更を試す。

• 途中経過の最高得点状態を保存しておいて、最終的にはそれを出力
  • 大幅には改善せず。乱数のブレの方が大きい
• 焼き鈍しのように、スコアが低くても低確率で強制的に更新
  • 却って悪くなる
  • 以下のバリエーションも試すが、同様
    • 強制的な更新の下限スコアを設定、あまりにスコアが低いものは更新しない
    • 強制的な更新はループの半分まで
• 1日のみを変更するのではなく、隣接する日のコンテストをswap
  • 10回に1回程度swapによる変更も加えることで、117,201,170 点
  • swapする日差を1～13日からランダムで決めたら 120,000,000 点に乗った
  • あまりswapを多くすると悪くなった（多分閾値とかいじると変わってくる）

スコア差分の計算方針の中で難しいのは、コンテスト開催間隔が空いたときの不満度。 ある日にコンテストを新しく開催/削除した際の増減分は、その日より前・後に直近で開催した日があれば計算できる。

あるコンテストの、1日あたり満足度の低下量
・c,e日目に開催していた場合
         _-~
      _-~
   _-~          _-~
_-~          _-~
---------------------
c           e

・d日目にも追加で開催した場合（d日目で0にリセットされ、翌日からまた増加）

   _-~    _-    _-~
_-~    _-~   _-~
---------------------
c     d     e
  
つまり、この平行四辺形の面積分だけ低下量は減る
         _-~|             縦: Ci x (d-c)
      _-~   |             横: e-d
   _-~|   _-    _-~
_-~   |_-~   _-~          → Ci x (d-c) (e-d) だけ満足度は増える
---------------------
c     d     e

よって前後に直近で開催した日がわかればよい。これは、C++でのstd::setなどのデータ構造をコンテスト毎に作ると $O(\log{D})$ で取得可能。

だが、ここがヒューリスティックコンと普段のコンテストの感覚の違うところだが、 今回、数値はランダムに決められているので、まず貪欲に埋めた時点で、 そこまで大きな間隔が空くコンテストは存在しないだろう（あっても少数だろう）と言える。 開催間隔が空くことに依る満足度低下は日数の2乗で効いてくるので、よほど $c_i$ がアンバランスでない限り、 開催間隔の空いたコンテストを放置することのデメリットが大きくなる。

なので、何日目にどのコンテストを開催したかを記録する配列を、$d$ 日目の前後に線形に探索しても $O(問題数)$ くらいで出現すると期待できる。

... 3 4 ... 8 1 3 5 ... 2 7 3 ...
    c           d           e

実装量が多く添字を取り違えやすいデータ構造を使うのと大きく変わらない計算量で、単純な線形探索で調べられる。

それならとりあえずは単純な実装でも十分だよね。特に今回は2時間コンテストで、手早い実装が大事。

コスト計算と更新の実装だけでほぼ時間を使い切ってるんだよなあ。

• せっかく使えるようになったNumbaを使うようにしたが、エラーの解消に時間を取られた
  • その分山登りの試行回数は $6 \times 10^6$ 回程度と、Pythonにしてはまぁまぁの回数回せたと思う
  • ただ、山登りのみだとある程度以降はほとんど改善の余地がなく、もっと時間の要する方法を試さない限り、無駄と言えば無駄
  • まぁ最初だしNumba用のいろいろな書き方が得られたことを収穫としておこう
• 力のいれどころを考える
  • 今回、差分更新計算を高速にするのにstd::setっぽい構造が有効そうで、それをBinary Indexed Treeで代替実装するのに時間を要した
  • だが、日数365、コンテスト数26において、多少効率の悪い方法を採ったところで、大きな影響はない
  • まずは簡単に済む方法で実装し、そこから必要なら高速化を考える

その他

• B,C問題のように、コスト関数等が正しく実装できていることをチェックできる機構があると、「そこまではあってる」という確証が得られて大変助かる
• ビジュアライザあるの忘れてた
  • 提出デバッグだと5分のロスタイムができるので、手元でちゃんとデバッグしようね
• Numbaはやっぱり制約が多い
  • 高速化はすごく助かる
  • numpy.random は普段のコンテストで使わないのでノーチェックだったが、関数自体はそれなりに対応されているようで、肝心な引数が未対応だったりする
    • choices の重み付け指定 p だったり、randint の一括生成指定 size だったりが未対応
  • print(file=sys.stderr) ができない
    • ビジュアライザに読み込ませるため、標準出力先をファイルにしたい
    • → 途中のデバッグ情報はエラー出力にすることでコンソールに出したい
    • → Numba関数内ではできない……
  • time.time() が使えない
    • 実行時間ぎりぎりまで回す、ができないので、適当にループ回数を決め打つ必要がある
  • ある程度、書くべきコードが頭の中で整理できている状態で書かないと、後戻りしたときに無駄が多くなる
    • まずは素のPythonで方法を考えながら実装し、そこから高速化、という方法もありかも知れないが、2時間ではそこまで行かなそう
    • そう考えると、素のPythonのままのコードでそれなりに高速に動くPyPyは強い
• 引数で混乱しがちなので、混乱しないルールを決めたい
  • って毎回言ってる気がする

時間の使い方としては、

• 普段のコンテストの最悪計算量の考え方にとらわれず、なるべく簡易に実装する
• 山登りなどで正の点数を得られるコードを書く
  • この辺、問題によって効果的な手法が違ってくると思われる
  • 戦略の参考
    • Introduction to Heuristics Contest 参加記録 - ARMERIA
• 人為的に決め打つ必要がある閾値がいくつか出ると思うので、5分ごとに投げてどの辺がいいか探る
  • 同時に、ランダムシードによるブレがどの程度生じるかも見ておくと、その後の改良に見込みがあるか無いかの判断材料になる
• その裏で、非効率な箇所の高速化や、ビームサーチなどちょっと重ための実装に置き換えていく

というのが基本かなあ。

ハイパーパラメータチューニングには、以下のようなツールもあるらしい。

• Optunaでハイパーパラメータチューニング - HELLO CYBERNETICS