最近、競技プログラミングを熱心にやっていますが、この記事では、競技プログラミングを一般向けに説明しようと思います。
競技プログラミングとは？
プログラミングによってアルゴリズムの問題を解く能力を競うものです。能力には、正答能力や解答スピードも含まれます。
超簡単な問題を紹介します。
問題: 2つの整数aとbが標準入力で与えられるから、その積が奇数か偶数か判定して出力せよ
このように、競技プログラミングでは、何かしらの入力が標準出力から与えられて、答えを標準出力にプリントして返すことが求められます。なぜこのようにしているかというと、どんな言語でも参加出来るようにするためです。一番使用者の多い言語はC++ですが、PythonやRubyなど、ほとんどのメジャー言語では参加可能です。私は、Rustという新しく、ややマイナーな言語を使っています。
ACとは？TLEとは？
今の問題では、あまりにもアルゴリズム感がないので、別の問題を考えます。
- 問題: 長さNの数列が与えられるから、大きい順に1000個を出力しなさい
- 制約: Nは1から107。配列の要素は1<=x<=100000
- 実行時間制限: 2sec
色々やり方はありますが、一番ふつうなのが、数列を降順にソートして、前から1000個をとるという解法です。これは、ソートのコストがO(NlogN)なので、計算量はO(NlogN)となり、ふつうの言語ならば2secで解くことが出来ます。実行時間制限を守って正答出来た場合、これをAC（Accepted）といいます。
しかし、別の方法として、
- N個のうち一番大きい数を探す。
- その数を消去する
- これを1000回繰り返す
という解法を考えたとします。ソートという概念を知らない場合、この解法が自然かも知れません。しかし、この解法は実行時間制限を守れません。O(N)の操作を1000回繰り返すため、オーダーが1010になり、どうやっても2secで計算することは出来ないでしょう。答えは合ってるのに、計算時間が超過した場合をTLE（Time Limit Exceeded）といいます。その他、そもそも答えが間違ってる場合をWA（Wrong Answer）、メモリ使用量の制限を超過した場合をMLE（Memory Limit Exceeded）といいます。
従って、この別の方法では、TLEとなります。
実際にはより難しい問題が出ますが、どの場合にも、TLEにならないようにいかに計算量を減らす工夫をするかというのが争点になります。
競技プログラミングって意味あんの？
情報学科ではそうですが、私が卒業した電気電子工学科でも「データ構造とアルゴリズム」という授業がありました。グラフ理論の授業もありました。競技プログラミングはこれらの延長線上にあります。プログラマとして学ぶことはこの他にもコンパイラだったりオペレーティングシステムだったり、計算機工学だったり、ソフトウェア工学だったり、色々あるわけですから、競技プログラミングが強いからと言って、プログラマとして強いかというとそれは嘘だと思います。
ただ、プログラミングの中でもっとも基礎的な部分を思いっきり強化するということには価値がありますし、競技プログラミングはそこらにあるアルゴリズムライブラリをポンポンくっつけて終わりというものではなく、問題自体にパズル要素・数学要素があるというのそうですが、コードを書く段階に至っても、複雑なロジックをいかにバグりにくく、すっきりと書くかという点も試されるので、やってみると学びが多いです。上級者の競技プログラマのコードはコーディングスピードを優先して変数名が適当だったりすることもあり、これが「競技プログラマはコードが汚い」あるいは「競技プログラミングをするとコードが汚くなる」という主張にも繋がっているのですが、じっくり読んでみるときれいということは多いです。ネーミングセンスというのは英語力の問題でもあるので、英語力がないと実際に読みにくいコードを書く可能性はありますが、英語力さえあれば、すっきりして読みやすいコードを書く素地があるといえます。
陸上選手やバスケット選手なども補強として筋トレをしますが、競技プログラミングはまさにこれに相当します。
AtCoderとは？
競技プログラミングでは、主にオンラインコンテストが行われ、成績によって参加者のレートが上がったり下がったりします。特に、超上級者のレッドコーダーというのは、一時期はTopCoderというコンテストのレッドコーダーになるとグーグルからお誘いが来ると言われたほど価値のあるもので、今でも参加者は自分のレートとそれに対応する色を上げるために努力しています。もちろんレッドコーダーを目指してる人もいますが、自分の才能や賭けられる時間を考えて、自分なりの目標を立てて向上していけることが良い点かと思います。私は今、赤よりはだいぶ下の青コーダーというのを目指して毎日何時間も勉強しています。
受験生の時に大数の学コンに挑んでた時のことを思い出して、楽しんでいます。
【大学受験】大数学コン55点から3ヶ月で名前を載せた最強の数学勉強法 - テストステ論
オンラインコンテストには色々ありますが、日本の会社が運営しているAtCoderというコンテストがあり、日本語で問題が書かれていることや、日本人も参加出来る時間帯に開催されることから、日本人の参加者が一番多いコンテストとなっています。競技プログラミングの黎明期には、それほど数は多くなかった日本人の競技者は先に挙げたTopCoderというのに主に参加していたようですが、参加時間が深夜帯だったり、問題文が英語だったりと、色々と大変だったようです。AtCoderが出来たことによって、日本人が競技プログラミングを始める敷居が相当下がったと言えます。私も、AtCoderがなかったら競技プログラミングはしていないでしょうし、そういう人は多いのではないかと思います。
勉強方法
プログラミングの勉強をしたいという人は昨今増えていますが、何からすれば良いかわからないという人は多いのではないかと思います。そんな場合にも競技プログラミングはおすすめです。なぜならば、プログラミングの中のもっとも純粋な部分を扱っているからです。これならば、いくらやっても無駄になることは絶対にないです。
ではどうやって勉強すればよいでしょうか。
競技プログラマの必読書とも言われているのが、通称「蟻本」と呼ばれるこの本です。
しかしこの本は同時に、ちょっと読むだけでも難易度が猛烈に高いことでも知られているので、その場合は、こちらの本がいいです。より基礎的な知識が詰め込まれていて、座学するにも向いています。
図を増やして、より簡単なトピックのみを網羅した入門書としては、このようなものもあります。絵でイメージするというのは学習にとって有効ですから、こちらもおすすめします。