ganmo::cout

競技プログラミング始めました

Introduction to Heuristics Contest 参加記

Ranking: 4 / 1795

はじめに


AtCoderのIntroduction to Heuristics Contestに参加しました。2時間のマラソンマッチ（いわゆる「ハーフマラソン」形式）で、今後のAtCoderのratedマラソンマッチに向けて開催されたものだそうです。
運がよかったからか何なのか未だにつかめていないものの、結果的に4位という順位が獲れてしまいました*1。コンテスト中にやったことや考えたことや今振り返っての反省や、思い出せる限りでまとめました。

注

Z=26をコンテストの種類数を表す記号として使っています。

コンテスト (2020/6/28 21:00 - 23:00; 2 hrs)

開始 (21:00)

とりあえずざっと問題文を読む。A問題がメインで、B問題とC問題は初心者向けの誘導問っぽい。
B, Cは点数が1点なので飛ばす。Aを読む。
とりあえずスコア計算を実装する。増加分は単にs_{d,i}を見ればよく、減少分はコンテストiが開催と開催の間で\delta日空いたときc_i \frac{\delta}{2} (\delta - 1)減るのでO(D+Z)で求められる。
各日にランダムなコンテストを割り振って初期解にして、ランダムな1日をランダムなコンテストにする（1点更新）山登りを実装する。問題文をよく読むとビジュアライザとテスターがあったのでダウンロードして使ってみる。しかしこの手元テストではあまり伸びなかった。

1投目 (21:27)

Submission #14809976 - Introduction to Heuristics Contest
ビジュアライザを見る。山登りをした後の解はs_{d,i}が大きいコンテストを選んでいることに気が付いたので、思い切って各日dで一番s_{d,i}が高いものを選んで初期解にして山登りにする。
→ 93,962,619 点
ハーフマラソンは実装に時間かけてられないのでビームサーチか焼きなましの前準備として適当にやったが、いきなり13位になりはしゃぐ。


しかし以前にもマラソンマッチで序盤だけいい順位が出て強者たちが出そろうにつれずるずる順位を下げていくことがあったのでまあ…くらいに思っていた。

2投目 (21:34)

Submission #14810928 - Introduction to Heuristics Contest
山登りが書けたら遷移判定を少し変えるだけで焼きなましができる。温度は30度(固定)、時間計測は100ステップに1回にする。
→ 94,839,240 点
ずるずると順位が下がり始める。

3,4投目 (21:43, 22:04)

Submission #14811994 - Introduction to Heuristics Contest
1点更新の遷移の際にdをランダムに決めた後でコンテストの種類をs_{d,i}の中で上位10個だけを選ぶようにする。
→ 104,531,723 点
1億点の大台に乗る。

Submission #14814787 - Introduction to Heuristics Contest
遷移先を上位8個に絞り、温度を300度に上げる。
→ 111,039,176 点

反省：遷移先を工夫したのはいいが、温度調節を始めるタイミングが早すぎる。温度固定でうまくいくなら回す回数が足りないので差分計算を早くやったほうがいい気がする

5投目 (22:13)

Submission #14815852 - Introduction to Heuristics Contest
ようやく差分計算を実装し、いままで1ステップあたり(D+Z)かけていちいちスコア計算していたものをO(logD)に高速化する。ついでに固定だった温度を300+1000(1-t)度 (t \in [0,1])に変更。
→ 120,595,804 点
予想よりスコアが上がり、再びはしゃぐ。

6投目 (22:26)

Submission #14817575 - Introduction to Heuristics Contest
序盤はs_{d,i}上位4個、中盤以降はs_{d,i}上位8個をとるようにする。何パターンか試したけどこれが手元テストでは一番良かった。
そろそろコードが長くなってきたのでコメントを付ける。
→ 122,326,156 点
はしゃぐ。今この瞬間でコンテスト終わったらいいのになあとか思ったりしていた。

7投目 (22:39)

Submission #14819315 - Introduction to Heuristics Contest
いい改善をする遷移のいろんなパラメータの平均をとってみるとやはりs_{d,i}が大きいものに偏っているので、s_{d,i}が大きいものに偏るよう乱数×乱数×上位何個とるかで選ぶようにする。
→ 123,007,867 点

8,9投目 (22:45, 22:51)

Submission #14820134 - Introduction to Heuristics Contest
差分計算のイテレータの使い方を工夫して定数倍を改善する。set::erase(値)を使っていたのでset::erase(イテレータ)で消すようにした。
→ 123,120,736 点

Submission #14820918 - Introduction to Heuristics Contest
温度を300+10000(1-t)^2度に変更し、イテレータの使い方をもう少し工夫する。
→ 123,795,433 点

最終提出 (22:58)

Submission #14822075 - Introduction to Heuristics Contest
ここにきてようやくacceptよりrejectの方が多いことに気づいてrejectを高速化してacceptのときに処理を押し付けて定数倍高速化し、スケジュールが全く変わらない遷移をしないよう実装を変える。
→ 124,229,835 点 (最終結果)

結果

順位: 4 / 1795
振り返ってみれば立ち回りが行き当たりばったりすぎるけど結果オーライ（よくない）

反省

方針が良くない

飛ばしたC問題の問題文から引用：

この問題の場合、「日付dとコンテストタイプqをランダムに選び、d日目に開催するコンテストをタイプqに変更する」という変形操作は実はあまり良くありません。

chokudaiさんの解説ツイ


はい…

方針が良くないのにスコアが伸びたのなんで？

焼きなましの温度が十分に高くて2点swapみたいな遷移がうまくなされていた？
コンテストタイプが少なくてc_iの偏りでうまくいった？

差分計算を書き始めるのが遅すぎる

ハイパラチューニングは終盤！（素振り）

改善が行き当たりばったりすぎる

マラソンマッチでは最悪計算量より平均計算量が重要！（素振り）
スコア改善の期待値で仮説立てる！（素振り）

まとめ

流石に4位はめちゃくちゃ嬉しい！

*1:やったぜ