この記事は、MMA Advent Calendar 2024 2日目の記事です。
こんにちは。dyktr_06 です。
今回は、Heuristic Contest のススメということで、AtCoder Heuristic Contest が面白いので布教しよう！というモチベーションで記事を書き始めました。
この記事は、主に以下のいずれかに当てはまるような人向けに書いています。
- Heuristic Contest が気になっている
- AtCoder Beginner Contest などの Algorithm のコンテストには参加したことがあるが、Heuristic のコンテストには参加したことがない
AtCoder Heuristic Contest とは？
AtCoder Heuristic Contest は、問題についての最適解を求めるのではなく、できるだけ最適解に近づけるような解を構成するコンテストとなっています。
競技プログラミングのコンテストとして有名な AtCoder Beginner Contest では、最適解を高速に求めることができる問題が出題されますが、AtCoder Heuristic Contest では、最適解を高速に求めることが難しい問題が出題されます。
実際の問題を見てみよう！
以下の問題を見てみましょう。
問題概要
二次元平面上に
匹のサバと
ある条件を満たす多角形を構築し、その内側に含まれるサバの総数から内側に含まれるイワシの総数を引いた値を最大化せよ。
制約として、
で固定であり、座標の範囲
は
である。
構築できる多角形の条件として、周の長さの上限が決まっていたりするのですが、ここでは細かい条件は気にせずに具体例を見てみましょう。
AHC では、基本的にビジュアライザが提供されており、入力例を可視化して見ることができます。
試しにビジュアライザを利用して入力例の 1 つを見てみると以下のようになります。
たくさんの赤い点と青い点が描かれているということが分かります。
ここで、赤い点がサバを表し、青い点がイワシを表します。つまり、赤い点をなるべく囲って、青い点をなるべく囲わないような多角形を構築しなければなりません。
試しにプログラムを作ってみよう！
この問題を解く簡単なプログラムを作成してみましょう。
アイデアとして、多角形で考えるのは難しいので長方形に限定して考えてみます。
適当な 2 点を選ぶと長方形が一意に定まることを利用して、何回か長方形を生成します。そして、その中に含まれる（サバの個数 - イワシの個数）が最も大きいものを選ぶということを行ってみましょう。
このプログラムで先ほどの入力例を試してみると以下のようになります。
良い感じの結果が得られていることが分かると思います。実際、上記のようなシンプルなプログラムでもコンテストにおける上位 50 % 程度のスコアを出すことができています。
さらに良い解を作るには？
ここでは深くは触れませんが、上記の問題でより高いスコアを目指すには以下のような方法が挙げられます。
- 入力の生成方法に着目する。例えば、今回の入力例を見てみても分かる通り、サバなどの座標はランダムではなくある程度固まっていることが分かります。
- 焼きなまし法やビームサーチなどのヒューリスティックで良く用いられる探索アルゴリズムを用いる。
このように、より良い解を追求するためのアプローチは多岐にわたります。良い解を求めようと思うと、奥が深いところも Heuristic Contest の魅力の一つです。
コンテストの種類について
AtCoder Heuristic Contest には、期間が 4 時間程度の短期コンテストと 1 週間以上の長期コンテストの 2 種類があります。
全体的な傾向として、長期コンテストのほうがやりごたえのある問題が出題される傾向にあります。（先ほど紹介した問題は、短期コンテストで出題されたものです。）
つまり、短期コンテストで出題される問題の方が取り組みやすくはありますが、短期コンテストの方は期間がかなり短いので、アルゴリズムを素早く考察して実装する能力が求められます。
それぞれに異なった特徴があるため、まずは参加してみることがおすすめです！
最後に
Heuristic Contest は Algorithm Contest とは違った面白さがあります。
AtCoder Heuristic Contest は AtCoder Beginner Contest と比べると開催頻度が少ないため、気軽に参加してみるのも大変ですが、AHC Survey - AtCoder によると、来年はコンテストの合計回数が増えるそうです。楽しみですね！
