自己紹介
成城石井が大好きなエンジニアの@wonda-tea-coffeeです。普段はユーザーサポート部の方々が使う管理画面の改修をしたりしています。今回は私が最近ドハマリしている競技プログラミングについてお話したいと思います。始めたばかりでちょっと偉そうなこと書いてる気がしますが、温かい目で見てもらえると嬉しいです。
競技プログラミングとは何か
制限時間内に出題される問題を解き、解いた数や解くまでの速さを競う大会です。国内外で様々なコンテストが開催されており、私の知る限りでは、こんなコンテストがあります。
国内
国外
たくさんありますね。このように国内よりは国外の方が盛んな印象があります。この後私が触れたことがあるものをいくつか紹介します。
どんな問題が出題されるのか
コンテストによって傾向はありますが、ここではAtCoderで開催されるAtCoder Beginner Contest(通称ABC)から問題を紹介します。
上記から問題文等を引用します。
問題文
高橋君は、プログラミングコンテスト AXC001 に参加しており、問題 A にコードを提出しました。 この問題にはN個のテストケースがあり、すべてのテストケースに正解した場合のみ提出は AC となります。 高橋君の提出は、N個のテストケースのうち M個のテストケースに正解しました。 高橋君の提出が AC となるか判定してください。
制約
1≤N≤100 0≤M≤N 入力はすべて整数である。
出力
高橋君の提出が AC となる場合は Yes, そうでない場合は No と出力せよ。
入力例
3 3出力例
Yes
どの問題も問題文、制約、入力例、出力が記載されています。ちなみにこれはA問題なのでコンテスト内で出題される問題のなかでは最も易しい問題です。AtCoder Beginner Contestでは100分間で全部で6問出題されます。
何が楽しいか
自分の思考力の限界に挑戦できる
普段仕事でコードを書いている分には「これどう書くんだろう？」のような疑問はなかなか生まれません（個人の感想です）。ところが競技プログラミングでは、皆目検討のつかない問題や、何を問われているかは分かるけど愚直に実装したらいくら時間がかかっても終わらないような問題が山程存在します。一見不可能かに見える問題に対して試行錯誤することで活路を見出す所が醍醐味の一つです。問題が難しければ難しいほど解けたときの達成感はひとしおです。
また、多くのコンテストサイトでは、コンテスト後に他の人の解答を見ることができます。コンテスト内では問題が解けなかったとしても、その後に他の人の正答を見ることで自分が成長できます。問題に立ち向かった時間と真剣さに比例して、問題を解いた人への大きな尊敬の念が生まれます。正答や解説を見ても全然分からないこともありますが...。
レーティング要素
多くのコンテストサイトではユーザーに対してレーティングが割り振られています。コンテストで良い成績を収めるほどレーティングが上がっていきます。 ↓は私のAtCoderのレーティングです（コンテスト出場回数が5回に満たないとレーティングが極端に少なくなるそうです）。
練習を積み、コンテストに挑み、レーティングを上げる。上がったレーティングを眺めてニヤニヤするのもまた競技プログラミングの楽しみの一つではないでしょうか。
アルゴリズムやデータ構造、数学などの知識が増える
コンテストではしばしばアルゴリズムやデータ構造、数学に関する知識が要求されます。それらの原理を学び、手を動かして頭に馴染ませることで少しずつ自分のものにすることができます。繰り返し問題を解いていくと「あ、これは貪欲法でいけるな」のように脳内でパターン化することができます。このように自分が解決できる問題の幅が広がることがとても嬉しいです。また、コンテストを抜きにしても様々な問題解決のために編み出されたアルゴリズムを学ぶこと自体がとても楽しいです。「こうすると効率が良いのか」「こんな方法があるのか」のような発見の連続です。
競技プログラミングをやり込むことで得られるもの
コーナーケースに気を配れるようになる
競技プログラミングの問題に取り組んでいると、しばしば特定の入力でのみ意図した通りの出力がされない場合があります。そういうときはしばしば極端な値を考慮できていないことがあります。素早く正確に問題を解く習慣がつくと、競技プログラミング以外でもコーナーケースを意識したコードが書けるようになります。
計算量を意識するようになる
競技プログラミングで出題される問題では、愚直な実装（例えば全探索）だと制限時間内に終わらないが、工夫したり枝刈りを行うと計算量がグッと抑えられることがしばしばあります。普段コードを書くときも「例えばAとBの順番を入れ替えたらどうか」「〜まで終わったら処理を打ち切れないか」などといった考え方ができるようなります。
エンジニアとして市場価値が上がる（かもしれない）
データ構造やアルゴリズム、数学の知識は時間が経過しても生き続ける分野です。プログラミング言語やフレームワークは時間が経てば使われなくなることがありますが、先に上げたものが使われなくなることはきっと無いでしょう。市場によってどの程度寄与するかは変わりそうですが、どこにおいてもきっと無駄になることは無いです。
勉強方法
以下では私が触れたことがあるコンテストサイトについて紹介するとともに、それぞれにおいてどんな風に取り組んでいるかお話します。他にもっと良い勉強方法がある、このコンテストもいいぞ、などあったらぜひとも教えてください。
AtCoder
上でも紹介したAtCoder Beginner Contest(以下ABC)に出場しています（まだ2回ですが）。ABCはおおむね週に一度、週末に開催されています。コンテスト後はライブ＆PDFでの解説が提供されます。また、ABCの過去問も解いています。過去問に関しては有志が作ってくださった以下がおすすめです。最近の問題から取り組むと傾向がつかめると思います。片っ端から埋めていきましょう。
https://kenkoooo.com/atcoder/#/table/
TopCoder
私は今『最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド』という本を読んでいます。この本ではTopCoderで出題された問題を多数取り扱い、問題の解法や解くための考え方を紹介してくれています。この本を読むだけでもとてもいい勉強になりそうですが、TopCoderでもAtCoder同様に過去問がすべて公開されています。
問題が英語で敷居が高いかもしれませんが、案外Google翻訳を駆使し、入力例と出力例から問題を（場合によっては）エスパーすることができます。問題数はとても豊富なので練習課題には事欠きません。また、私が何度か観測した限りではコンテストが深夜帯であったため、健康的な生活をしたい方はなかなかコンテストに出場するのは難しいかもしれません。
yukicoder
私が今一番お世話になっているサイトです。難易度別、自分が解いたかどうかの絞り込みなど問題の検索機能がとても使いやすいので気に入っています。執筆時現在で200問くらい解きました。コンテストの出場はまだ1回だけですが、有志が問題を作っているためか、難易度の★に対して難しかったりする印象を受けました。また、こちらも問題に解説がついています。作問者の解説に加えて有志が書いた解説のリンクも併記されてる親切な仕様です。嬉しいですね。
LeetCode
こちらはすべて英語ですが、問題の解説や教育的なコンテンツの質が高く、また、量も豊富です。ただ、それらすべてを閲覧するには有料会員になる必要があります。執筆時現在月額35ドルと安くない金額ですが、真剣に学習したい方は前向きに検討してよいのではないでしょうか。また、週に一度Weekly Contestが開催されています。積極的にコンテスト出場経験を積みましょう。私はまだ2回しか出場していませんが...。
ProjectEuler
こちらはこれまで紹介したサイトとは少し雰囲気が違っていて、出題される問題の多くは数学要素が強めです。ものによっては数学的知識無しではまず解けないような問題もあったりします。ここの問題が解けずに悔しい思いをした、あるいは数学に興味を持った方は『はじめての数論』という本をおすすめします。この本は数論の入門書なのですが、章末の練習問題にコンピュータで解くことを前提として問題が多数紹介されています。この本を一通り読むことができれば、ProjectEulerで解ける問題がグッと増えていることと思います。
まとめ
競技プログラミングはいいぞ。
