Zenn
😎

AHC016に参加しました！

2022/12/19に公開
AtCoder
tech

はじめまして。matchasongと申します。
HACK TO THE FUTURE 2023 予選（AtCoder Heuristic Contest 016）に参加しました。
だいぶ遅ればせながらではありますが、ぴよぴよ参加記を投稿したいと思います。

結果

  • 294位で、パフォーマンスは水色相当(1535)でした。
  • 最終提出の暫定テストは400,864,219点、システムテストは282,549,175,088点でした。

情報

提出言語

  • PyPy3

エディタ

  • PyCharm(Pythonを書くときに使いました)
  • Visual Studio Code(自動テストのシェルを書く時に使いました)
  • 2つになったのは、各言語で使い慣れているエディタを使った(気づいたら使っていた)という感じで特に深い意味はないです。

テスト

  • Web版ビジュアライザとローカルテスタが、問題欄に用意されていました。
  • 序盤は、Web版ビジュアライザをポチポチしていました。
  • 中盤で、ローカルテスタをダウンロードしました。
  • シェルでローカルテスタをラップし、100ケース分のテストを自動実行しました。
    (このおかげで後半たくさんテストを回せるようになり良かったです)

スプレッドシート

  • 自動実行したテストの計測値をまとめました。
  • いくつか解法が思いついたものの、どれがいいのか分からない時に使いました。
  • 得点を上げるのに、地味に役立ちました。

やったこと

やったことを振り返りたいと思います。

その1.初期値で提出する

全クエリに対して、予測=1と固定で答えるようにしました。
グラフの出力が上手くいかず1WAしましたが、30分後に再提出。
ACと出ると楽しくなってきます。
175,922点(絶対スコア=提出結果欄の点数です)

  • ACになって嬉しいの図

その2.ONのビット(1のビット)の個数を数える(方針1)

サンプルプログラムを見ながら、ONになっている(=辺が繋がっている=1になっている)ような
ビットの個数を数える方針で組みました。
頂点数Nは多い方が予測を当てやすいと考え、100に固定しました。
使えるビット数は、頂点の組み合わせなので100 * 99 // 2 = 4950個。

M個のグラフを区別しやすくするために、
1個目のグラフは、4950 // M 個がON、
2個目のグラフは、(4950 // M) * 2 個がON... 、
のようにグラフの番号に応じてONのビット数を増やしていきました。

ONのビットの個数をあらかじめ配列に持っておき、各クエリに対してONのビットの数が近いグラフの番号を、予測として解答しました。
若干点が増えたもののまだまだ予測が外れるケースが多いようでした。
10,244,033点

その3.エラー率を加味する

エラー率ϵが0.4と大きいと、ONが0個のグラフを与えても、戻ってくるグラフの40%はONで返ってくることに気づきました。
予測がかなり外れていたのはこのためだったようです。
「ONのビットの個数」ではなく、「エラー率を加味したONのビットの期待値」に変更しました。
エラーに若干強くなり、点数が上がりました。
176,158,640点

その4.ビット数ではなく、頂点単位でON/OFFを表すようにする(方針2)

頂点単位で全部ONか否かのグラフを作る方針に変えました。
1個目のグラフは頂点0が全部ON、
2個目のグラフは頂点0~1が全部ON、
3個目のグラフは頂点0~2が全部ON...みたいな感じです。

予測のアプローチを変えてみたものの、かえって得点が下がりました。
144,363,722点

その5.条件によって解答方針を使い分ける

正直これ以上思いつかなかったため、解答方針を使い分けてスコアが上がらないかを考えました。
ONのビットを数える方針と、頂点単位でON/OFFを表す方針の得点をスプレッドシートにまとめました。

さらにバブルチャートにしたのが下図になります。
今回の問題では、エラー率ϵと出力するグラフ数Mの2つが、与えられる変数でした。
エラー率ϵをx軸に、出力するグラフ数Mをy軸に取り、バブルの大きさを得点としています。
それぞれの方針において、有利なのは赤枠のあたりかなと思いました。

  • (方針1)1の個数を数える方針

  • (方針2)頂点単位でON/OFFを表す方針

全体としては方針1の方が点が大きい(バブルが大きい)ものの、
エラー率ϵが0.1以上、かつ、グラフ数Mが50未満の時には、方針2が良さそうと感じました。
分岐を作って方針を使い分けたところ、得点がだいぶ上がりました。
188,349,468点

その6.入力で与えられたエラー率が0の場合に、頂点数Nを小さくする

エラー率が0であれば頂点数が少なくても誤りは出ないと考えました。
点数の計算式から、頂点数を小さくすれば得点が上がることが分かったため、
頂点数N=100にしていた箇所を、頂点数N=M(10<=M<=100)に変更しました。
(解説を見てもっと小さくできると知り、驚きました...)

限定的なケースへの対応でしたが、大きく得点が上がりました。
321,177,655点

その7.テスト結果から、解法の組み合わせを変える

その5と同じように、解法の分岐を見直し、分岐を修正しました。
やったことは地味ですが、得点は上がりました。
400,864,219点

感想

  • 自分の今できる範囲では、色々試行錯誤できたかなと思います。特にローカルでテストを回して分岐を調整できたことが良かったです。
  • 解説を見て、数学や統計は少し勉強してみたいなと思いました。
  • 楽しかったです。次回以降も参加していきたいと思います。

お読みいただきありがとうございました！

Discussion