allegrogikenというIDでAtCoderをやっている松崎です。今回は競技プログラミングについての語りをやっていきます。
具体的には「ヒューリスティックコンテストの勧め」です。少しでも楽しさが伝えられたら幸いです。

アイキャッチ画像は話題の Stable Diffusion に描いてもらった「マラソン大会で走るロボットたち」です。（ヒューリスティックは俗にマラソンとも呼ばれる）

伝えたいこと

  • ヒューリスティックのコンテストは実業務に役立つテクニックが多いです
  • 逆に、業務でプログラミングをやっている人なら優位に立てる面もあるはず・・！
  • 2022/09/17から AtCoder で 2週間のヒューリスティックコンテスト が開催されます
  • 長期コンテストは土日忙しい人でも参加がしやすいですよ！！
  • ぜひ参加してください！！！！

詳しく

競技プログラミングとは

「ある問題について、プログラミングを用いて解決する」ことを競技化したものだと思っています。
問題もさまざま、解決方法や競技種目もさまざまなものがあります。
日本では「AtCoder」というWebサイトがあり、コンテストがほぼ毎週開催されています。

ヒューリスティックコンテストとは

ある問題について、一定の制限下で「スコアの最大化を目指す」という競技種目のコンテストです。
理論上は「満点」が存在するものの、現実的ではない・・ という制限がいい感じに課されています。なので、満点に近いスコアを出せるようなプログラムを書けば良い、ということになります。

ヒューリスティックコンテストは最も短くても 4時間程度の長さがあります。4時間のコンテストは短期コンテストという扱いで、長期コンテストと言われるものは 1, 2週間程度の期間があります。
AtCoderでほぼ毎週開催される「AtCoder Beginner Contest」は100分間なので、かなり違いがあります。

期間が長いということは、その間はずっと提出ができるということで、参加もしやすいです！特に、土日の夜はちょっと・・ という人でも、ちょっとしたスキマ時間に取り組むことが可能です。

実際の例

2022/07/03 に開催された短期コンテスト(AHC012) を例として見てみましょう。
https://atcoder.jp/contests/ahc012/tasks/ahc012_a

「円形のケーキにたくさんの苺が乗っているので、それをいい感じに切り分けてくれ」という問題です。
苺は最大で 5,500 個、ケーキのピースは最大で 1,000 個作る必要があります。
また、ケーキをカットする方法は「直線を引く」のみで、最大 100 回までとなります。

さらに、「この人には苺を x 個」というオーダーが人数分渡されてきます。
このオーダーをできるだけ多く満たせるようにケーキを切り分けることでスコアが満点に近づいていきます。

どんな風に解くのか？

いろいろな解き方があり、一言では説明ができないですね・・・！
しっかり学びたい方は、参加者による解説を読むのがおすすめです。 https://atcoder.jp/contests/ahc012/editorial

ランダム解の実装

簡単のため「ひたすらランダムで解く」という例を提示します。(それでも立派な回答です！)

下のような Ruby のコードを用意しました。この問題でプログラムが出力すべきは「直線を表す始点・終点のリスト」です。完全なランダムで100本の線を引く、という非常に雑な実装です！

LINES = 100
XY_LIMIT = 10_000

puts LINES
LINES.times do
    puts 4.times.map { rand(-XY_LIMIT..XY_LIMIT) }.join(" ")
end

ところで、AtCoderのヒューリスティックコンテストでは多くの場合「ビジュアライザ」が提供されています。今回の問題ではケーキがカットされた様子が絵でわかるというものになっています。分かりやすいですね！

cake_cut_random

円（ケーキ）の上の表はピースに対する苺の個数のオーダーを表しています。
1行目には「d 個の苺が乗ったピースが a 個欲しい」というオーダーそのもので、2行目にはカットした結果の分布を示しています。

さすがにランダム解ということで、当初のオーダーをあまり満たせていません。視認できないほど小さいピースもできてしまっていて、なかなか酷い出来です。

しかし、これでも提出してみると 59,233,761 のスコアが得られます。満点は 100,000,000 なので、全体で 6割 程度のオーダーを満たせていると見て良さそうです。

固定サイズで格子状にカットする解の実装

もう一つ例を見てみましょう。今回は「定間隔で縦横に50本ずつカットする」ものです。Rubyでのコードはこうなりました。

LINES = 100 / 2
XY_LIMIT = 10_000
CUT_SIZE = XY_LIMIT * 2 / LINES

puts LINES * 2
LINES.times do |t|
    cut_point = t * CUT_SIZE - XY_LIMIT
    puts [cut_point, -XY_LIMIT, cut_point, XY_LIMIT].join(" ")
    puts [-XY_LIMIT, cut_point, XY_LIMIT, cut_point].join(" ")
end

ビジュアライザはこのようになりました。オーダーを満たせているかどうかはともかく、とても綺麗ですね。

cake_square_cut

提出してみると、スコアは 43,646,257 となりました。なんとランダム解よりも悪いです。丁寧に切ったのに・・

ヒューリスティック問題の面白さ

実例を見てもらいましたが、いかがでしょうか？個人的には、いろいろなアプローチで問題に取り組めるところがヒューリスティックの面白いところだと思っています。勉強してみると「ランダム性を取り入れる」のが有効に働くことが多いことがわかったりして面白いです。

今回、完全なランダム解の方がスコアとしては上になりましたが、この実装でスコアを伸ばしていくのは難しそうです。ピースの形が複雑になり計算が大変ですし、全てがランダムなので再現性が低いからです。

対して、格子状に切った方はいろいろなやり方で改善できる余地があります。カットした際にできる図形が四角形なので「どのピースに苺がどれだけ乗るか」の計算がやりやすいからです。目標に合わせて「不要そうなカットをスキップしてみる」とか「カット線の位置を微調整する」などのアプローチで改善することができそうです。

私が参加した時も、このような考えでスコアを伸ばして行きました。スコアの改善活動こそがヒューリスティック問題で一番楽しい瞬間だと思います・・！

ヒューリスティック問題には業務プログラミングのスキルが有効という説

最初に提出したコードからいろいろなアイデアを加えてスコアを伸ばしていく・・ という活動は業務でのプログラミングに感覚が近いです。
改善しやすいようにプログラムの構造を整えていくことも重要ですし、1週間以上のコンテストであれば世代管理がしたくなるかもしれません。問題に登場する概念をモデリングしてクラスや構造体といったもので表現する機会も多いです。

こうした術は業務でプログラミングをしている人であればすでに所持している可能性が高いスキルではないかな？と思います。

そういった理由で、業務プログラマーが競技プログラミングを始めるならヒューリスティックから始めてみても良いのでは？と思っています。
業務でプログラミングをしていない、あるいはこれから始める・・ という人にとっては、ヒューリスティック問題はおそらく良い練習になります。

近日開催予定のヒューリスティックコンテストの紹介

冒頭にすでに書いていますが、2022/09/17 〜 2022/10/01 に2週間に渡っての長期コンテストが開催されます！(AtCoderさん, estieさん, 開催ありがとうございます)
https://atcoder.jp/contests/ahc014

ヒューリスティックコンテストはとても面白く、実務に近い学びがあって、参加もしやすいです！今回の長期コンテストを機にぜひ参加してみてはいかがでしょうか？