Atcoder Heuristic Contestの順位とアルゴリズムのレートの関係性を眺める

趣味分析 マラソンマッチ

はじめに

Atcoder Heuristic Contest(AHC)は最適解を出すのが難しい問題に対し、出来るだけ良い解を作成するコンテストで、 開催期間が1週間以上の長期コンテストと、1日未満の短期コンテストがあります。

ABC/ARC/AGCのような最適解を求めるアルゴリズムコンテストとは性質の異なるものにはなるのですが、 体感としてアルゴのレーティングが相対的に低い人は長期コンテストの方が良い順位がとりやすい感じがしたので、 それをデータを見て確認したいと思います。

必要なデータはAtCoderの順位表のページのURLに/jsonをつければjson形式で取得できるので、それを利用しています。

コンテスト種別

現在まででRatedのヒューリスティックコンテストは9回開催されており、 うち5回が短期、４回が長期コンテストでした。

コンテスト名 開催期間 種別
AtCoder Heuristic Contest 001 9日 長期
AtCoder Heuristic Contest 002 4時間 短期
AtCoder Heuristic Contest 003 9日 長期
AtCoder Heuristic Contest 004 6時間 短期
AtCoder Heuristic Contest 005 4時間 短期
RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 8日 長期
HACK TO THE FUTURE 2022 予選 11日 長期
AtCoder Heuristic Contest 006 4時間 短期
AtCoder Heuristic Contest 007 4時間 短期

データの確認

各コンテストの、順位とアルゴリズムのレーティングとの散布図が下記になります。 順位が縦軸、レーティングが横軸です。 参加回数が少ない場合は実力との乖離が出るため、今回アルゴリズムコンテストの参加回数が20回未満の人はデータから除外しています。

f:id:rmizutaa:20211215145701p:plain

どれもゆるい逆相関になります。若干ですが長期コンテストの方がばらつきが大きいように見えます。 各コンテストの相関係数は以下のようになりました。

contest 相関係数
ahc001 -0.45
ahc002 -0.52
ahc003 -0.44
ahc004 -0.54
ahc005 -0.63
recruit -0.44
httf -0.40
ahc006 -0.56
ahc007 -0.63

短期コンテストの相関は-0.4~-0.45、長期コンテストの相関は-0.52~-0.63なので、 全体の傾向としては、短期コンテストの方がアルゴのレートとの相関が低くなるようです。

次に、上位に入る人の傾向も変わるのかを確認するため、 各コンテストで100位以内に入った人のアルゴレートの色別比率を示します。

f:id:rmizutaa:20211216085333p:plain

100位以内に限定してみるとそれほど長期と短期で違いが現れないようです。

より絞って30位以内の色別比率を見てみます。

f:id:rmizutaa:20211216085342p:plain

30位以内に絞ると長期と短期で傾向に違いが出てきます。 特に青色以下の人が30位以内に入る比率が短期だと平均20%程度なのに対し、長期だと50%近くまで増加します。

まとめと考察

  • 長期コンテストの方が短期コンテストよりもアルゴの能力の影響は小さい。
  • アルゴのレートが相対的に低い人が上位(30位程度)を目指す場合、長期コンテストの方が優位になりやすい

という結果でした。このようになる理由としては、

  1. 長期コンテストではコンテストに使える時間が人によって異なる
  2. 長期コンテストの方が問題構造が複雑でアルゴと異なる能力が要求される

の2点が考えられそうかな思っています。 使える時間が異なる場合は時間をつぎ込んだ人の方が順位は高くなりやすいので、ばらつきが大きくなるのはそうだろうなーというのが1つと、 例えば長期コンテストのahc003やhttfではパラメータ推定をする必要があったのですが、こういった問題への対処はアルゴリズムとはまた別分野の知識が必要になりそうなので、アルゴレートとの関係性が低くなるのかなと思っています。

使用したコードは以下になります。

github.com