Heuristic Contest のススメ
この記事は、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 によると、来年はコンテストの合計回数が増えるそうです。楽しみですね！
AtCoderで黄色に到達しました
こんにちは。この度は AtCoder で黄色に到達したため記事を書いてみようと思います。
解いた問題数とか
皆さんお馴染みの AtCoder Problems の画像を貼っておこうと思います。
割とバランスよく解いている方だと思っています。
精進について
上の解いた問題数とコンテストの参加回数を見るとわかるのですが、自分から過去問を解きに行くということはたまにしかしていません。
基本的にコンテストに参加して解けなかった問題を解きなおすということを繰り返しています。
これは成長が遅くなる理由の一つでもあると思いますが、ABCなどは開催頻度が高いため参加して復習を行うだけで十分な成長が見込めると思っています。（AtCoder だけでなく、Codeforces や yukicoder の参加もおすすめです！）
新たなアルゴリズムの学習方法
ABCでは、アルゴリズムを知っているだけで有利に立ち回ることができます。
AtCoder で水色から青色の人は、Library Checker を見て回ったり、ABC の G 問題を積極的に解いたりすると知らないアルゴリズムを見つけることができると思います。
正直なところ、考察力などは青色になった頃からはあまり変わっていないと思っていて、既知のアルゴリズム・テクニックが増えたことにより ABC で良い成績を取れる確率が格段に上がったと感じています。（実際、ARC などではあまり良い成績を取れていません。）
作問について
作問は学習したアルゴリズムに対する理解を深める良い機会になるので実力の上昇に繋がったなと感じています。
MojaCoder という誰でもコンテストを開催できるサービスで MMA Contest という名前のコンテストを開催したりしていました。（毎回 Tester をしてくれる sepa_38 くんに感謝......）
そういえば、2023/5/28(日) に電気通信大学で MMA Contest 015 がオンサイトで開催されるようです。
開催前にこの記事を見てくれた方はぜひ参加してみてください。
ライブラリ整備について
ライブラリの整備は個人的にはかなり重要な要素でした。
自分自身は実装速度やタイピングの速度がそもそもあまり速くないため、ライブラリを積極的に作成して補っています。
また、脳のリソースを余計なところに割かないで済むというメリットもあります。
ライブラリの整備に興味がある方は Library Checker を埋めてみると良いと思います。（最近は更新が活発になってきており良いです。）
学んだアルゴリズムなど
ここで自分が学んだアルゴリズムを書いても需要がないと思うので、ABC の G 問題に出題されたことのある学ぶだけで即効性のありそうなアルゴリズム・テクニックを箇条書きで書いていきます。（もしかしたらネタバレになるかもしれません）
- 拡張ダイクストラ
- 行列累乗
- 最小費用流、最大流
- 添え字和での畳み込み
- 半分全列挙
- 平方分割
- ベルマン-フォード法
- bitsetによる高速化
- xor基底を掃き出し法で求めるやつ
- Baby-step Giant-step
- Convex Hull Trick
- Euler Tour
- Heavy Light Decomposition
- Lazy Segment Tree
- LCP Array
- Mo's Algorithm
- Suffix Array
- Z Algorithm
終わりに
これからもぼちぼち頑張っていきます。
ここまでお読みいただきありがとうございました。
