Heuristic Contest
AtCoderで最も有名なコンテストであるAtCoder Beginner Contest(ABC)や、AtCoder Regular Contest(ARC), AtCoder Grand Contest(AGC)などは、全てAlgorithm部門のコンテストです。一方、AtCoder Heuristic Contestは、Heuristic部門のコンテストです。
この二つの最も大きな違いは、最も良い解のみを正解とするか、そうでない解を正解とするかです。
例えば、以下のような問題があったとします。
整数列 A が与えられます。 A からいくつかの要素を抜き出し、その和をできるだけ 1,000 に近づけてください。
ここで、以下のような入力が与えられたとします。
100 123 157 256 345 364 399 563 722
この時、Algorithm部門であれば、1000に最も近い組み合わせである、256 + 345 + 399 = 1000を出力する必要があります。これ以外の回答は不正解となり、Wrong Answer(WA)となります。
Heuristicコンテストでは必ずしもそうではありません。
例えば、100 + 123 + 157 + 563 = 943となり、1000からの差は57となります。この答え自体もACとなりますが、1000ぴったりの答えより低い点数が与えられます。
このように、 最適解を求められるかどうかのゼロイチの問題ではなく、どれだけ良い解を導き出せるかという、自分の限界に挑戦するようなコンテストがHeuristicコンテストです。
また、 Heuristicコンテストでは、そもそも最適解が出せない問題が出題されます。 今回の問題の例では、例えば目標の和が1000ではなく10億で、Aの数の種類が10万種類などになれば、最適解を出すことは非常に難しいです。そうした問題に対し、いかに良い解を出せるか、という点で競い合います。
Heuristicコンテストで良い点を取るには？
Algorithmコンテストと違い、Heuristicコンテストでは、完全に解けた、という概念はありません。1点でも取れればそれは正解であり、しかしその正解より先にさらに良い正解があります。
Heuristicコンテスト初心者の方は、まずはできるだけ簡単な解で、ACを取る事を目標としましょう。先ほどの問題であれば、「最初のひとつの整数だけ出力をする」などをすれば、確実にACが取れます。
そこから、さらに改善できる要素を少しずつ探していきましょう。例えば以下のような改善が考えられます。
- 最初のひとつ、最初のふたつの和、最初のみっつの和のうち、最も良い解を出力する
- 大きい順に並び替えて、1000を越えない範囲で貪欲に採用していく
- まず大きい数で貪欲に採用し、最後の小さい数だけ探索やDPを用いて解く
最初から最適解に近いものを出そうとすると、たいていの場合は挫折してしまいますので、少しずつ改善していくのがポイントです。自分のアルゴリズムのレベルに合わせて、十分実装できる形に落とし込むことが大切です。できることから取り組みましょう。
上位を目指すのであれば、Algorithm部門では出てこないけれども、Heuristicコンテストでは出てくるようなアルゴリズムも勉強するとなお良いです。具体的には、焼きなまし法やビームサーチ法などがそれにあたります。
これらのアルゴリズムを学びたい場合は、Introduction to Heuristic Contestに挑戦してみましょう。 Introduction to Heuristics Contest→
さらに実力を高めるには？
コンテストに出た後に、さらに実力を高めたいのであれば、復習をしましょう！
AHCが終了すると、多くの人がTwitterやブログにて、AHCの参加記録を書いています。AtCoderのコンテストページの解説タブからリンクされていることも多いので、上位の回答を参考にしましょう。
