はじめに
先日、株式会社ゲームフリークさんの「ピカチュウきのみを探索中」という企画で、初めて競技プログラミングをする機会があったので、これを機に競技プログラミング(略して競プロ)について調べてみました。
そもそも競技プログラミングって何？
競技プログラミングとは、いかに課題を解決するプログラムをスピーディーに正確に記述するかを競う、プログラミングコンテストの総称です。
競技プログラミングにはいくつかジャンルがありますが、ここでは最も代表的なジャンルであるアルゴリズムについて説明します。
有名問題「Ants(蟻)」
競技プログラミングが実際にどんな問題を説いているのか、競プロ界の超有名問題を紹介したいと思います。その問題は「Ants(蟻)」と呼ばれ、内容は以下のようになります。
1. 棒の上に100匹の蟻がいます。
2. 棒は99cmで、蟻は棒の端から端に1cm間隔で並んでいます。
3. 左端の蟻は右を向いており、次の蟻は左を向いています。
4. その後の蟻も右・左・右…左と交互を向いています。(右端の蟻は左を向いています。)
5. 上記の状態から、全ての蟻が秒速1cmで歩き出します。
6. 蟻は他の蟻に出会うと即座に反対を向いて歩き出します。
7. 蟻は棒の端にたどり着くと棒から落ちます。
この条件で、全ての蟻が棒から落ちるまでにかかる時間を求めよ。
普通に解こうとしてみる
まず、一番左の蟻に注目してみましょう。
1. 蟻は開始と同時に右に歩き出します。
2. 右隣の蟻も左に歩き出すので、この2匹は0.5秒で出会います。
3. 蟻は左に向かって歩き出し、0.5秒後に棒から落ちます。
このように、一番端の蟻が落ちるまでにかかる時間を求めるのは簡単で、1秒かかると分かります。
しかし、内側の蟻になればなるほど、何度も他の蟻と出会うので計算量は増えていきます。
条件を全て設定してコンピュータに計算してもらうこともできますが、かなりの時間がかかってしまいます。
競技プログラミングでは、このように単純にコンピュータに計算させようとすると、計算時間がかかりすぎて答えが求められないような問題が出題されます。
「Ants」の解法
この問題は、蟻を区別しないことで一瞬で答えを求めることができるようになります。
どういうことかというと、この問題では最後の蟻が落ちた時間を求めればいいので、蟻は区別しなくてもいい、蟻は「出会って反対を向いた」のではなく「すれ違った」としても全体の位置関係に支障がないということです。
蟻が方向を変えずに他の蟻とすれ違っていくと考えると、落ちるまでに一番時間がかかる蟻は一番端の2匹だといえます。
蟻は秒速1cmで99cmの棒を歩くので、この2匹が落ちるのにかかる時間は99秒です。
つまり、元の問題で最後の蟻が落ちるまでにかかる時間も99秒であると言えます。
まとめ
問題「Ants」は、工夫によって圧倒的に少ない計算量で答えが求められる非常に良い例でした。
競技プログラミングでは、与えられた問題をいかに少ない計算量で解くかが重要だということがわかっていただけたでしょうか。こういったアルゴリズムを考える能力は、新たなシステムを必要とするモノづくりには欠かせないので、多くの企業も注目しています。
また、逆にいうと、プログラミングに必要な知識はほとんどないため、計算式を書き、答えを出力さえできれば誰でもコンテストに参加することができます。使用する言語も好きなものを選べるので、プログラミングをはじめたての方もぜひ挑戦してみてください。
補足
問題「Ants」は「プログラミングコンテストチャレンジブック」という本で紹介されており、そのことから競プロ界では"蟻本"と呼ばれています。プログラミングコンテストの問題を通してアルゴリズムのしくみや考え方を楽しく習得できる本なので、興味を持った方はぜひ読んでみてください。