競技プログラミングを布教したい
※この記事は「eeic2022 Advent Calendar 2021」の16日目の記事の一本目（！？）です、二本目についてはこちらをご覧ください（二本目は競技プログラミングとは関係ない記事です）。
※割と学科民向けに書いてるので具体的な講義名とかが出てきて外部の人には優しくない記事かもしれませんがご了承ください。
０. 自己紹介
何気にeeic内定してからここで記事書くの初めてでは？なわけで改めて、東京大学（まだ）理科一類のモグリン（AtCoder ID: mogurin）と申します。一応競プロの記事だしいつもの貼っておくとこんな感じ。
ん？君停滞してない？というかHeatMapの右側真っ白なんだけど......
はい、実は競プロサボりまくっててコンテストも出てないことがしばしば、いや、中間試験とシャニマスとルペルカリアがね......
やっぱ学科民の中に私より強い人もめちゃめちゃいそうだししかも競プロについて書く人既にいるんごじゃん、私がわざわざ競プロについて書く必要ないな！解散！！......と思ってたんですけどね、とある理由により書くモチベが生えたので私も書きます、ちなみにAPG4bからAtCoderへの導線を張ろうとした記事を過去に書いてるのでこっちも読んでね！（宣伝は基本）
１. そもそものお話
競プロってなにそれおいしいの？みたいな人は流石にいないと思いますがまあ一応ざっくり書くとこの記事で扱うAtCoderのように専用のコンテストにてプログラミングを用いて問題を解く（入力に対して要求された出力を返すプログラムを書く）、パズルのような遊びです（ちょくだいさん曰くネトゲ）。特徴としてはゴリゴリ数百行のプログラムを書く開発とは違い、あくまでも問題を解けるアルゴリズムを考えて実装するのが目的なのでそこまで重実装にならないことが多いです（もちろん例外もあるし難易度の高い問題程実装量は上がる）。その分短時間で適切なアルゴリズムを考え出さなければいけなく、特に計算量という概念が競プロにおいては超重要になってくるのですが、いかにして計算量を減らしたアルゴリズムを考え出せるかが競プロにおける醍醐味と言えるでしょう。この辺の面白さを短時間で知りたいならkort0nさんの記事がおススメです。
２. 結局何が楽しいの？
競プロの楽しみ方は結構人によって異なるため一概に「これが楽しくてこう楽しむのが正解！」みたいにいうことはできません、ここから書くことはあくまで私個人の感想であるためご了承ください。
１. 正解（AC）の快感
頑張って書いたコードが通った瞬間の気持ちよさが異常、ソフⅠの自動採点で祈ってた人はわかるはず。
２. 色んなアルゴリズムを知ることが出来る
競技プログラミング、最近はそこそこ競技人口多めなので色んな人が記事を書いてくれてるし最近はわかりやすい記事も大量に出回っています、割とよく使うアルゴリズムなら問題解いてわかんないワード調べてるだけでサクサク身につくのが楽しいです、特に演習教材となる問題にその場で取り組めるのも魅力的。余談ですが簡単なもののなかではめぐる式二分探索初めて知った時は感動しました、中の人誰だかわからないけどすごい。
twitter.com
【めぐるのアルゴリズム講座】
— 因幡めぐる@競技プログラミング (@meguru_comp) 2016年2月9日
二分探索（整数）の書き方
難しさ：４ pic.twitter.com/LGLbkS0D7l
３. コンテストが楽しい
やっぱり人間なので競う場があったほうが盛り上がるんですね、AtCoderでは時間内に複数の問題を解くコンテスト（代表的なのはAtCoder Beginner Contest、通称ABC）がなんと週一で開かれています。最近見れてないけどコンテスト後に他の人の賢い解法ツイートや感想ツイートを見るところまで含めてコンテストだと思ってる。
他にもレートの上下があるのが楽しいとか色んな意見がありますが私が競プロを楽しいと思う理由はこんな感じです。あと競プロは授業の役に立つ、競プロは研究の役に立つ！（いいえ）
３. 何から始めればいいのか
こっからは具体的な話です、ぶっちゃけ最低限の検索力とプログラミング経験があれば読まなくてもいいかもしれない、調べるのめんどくさい人だけ読めば良さそう。
まず、AtCoderに登録しましょう。
atcoder.jp
この時についでにTwitterで競プロ垢とか作ってしまうといいかもしれない。
さて、ここからは言語選択です、授業で習ったC言語、Pythonを含め色々ありますがここではC++をおススメしたいです。理由としては
- 速い（実行時間が少なくて済む）
- ネットで競プロの解説記事としてC++が使われていることが多くわからないことを調べやすい。
- 少なくともC言語よりは楽に書ける（STLの関数やクラスの存在）。
- 抽象化が便利、
特に他人のライブラリをパクる時に。
そして何よりもAtCoderの公式C++入門教材、APG4bの存在が大きいです。
atcoder.jp
何を隠そう私も競プロもといプログラミングそのものにここから入門しました。プログラミング初心者にもわかりやすくC++について説明されています、節ごとに演習問題があるのも嬉しい。特に競プロをやる言語にこだわりがない人は、C++でやってみるのはいかがでしょうか？
APG4bのレベルについてざっくり触れると、
- 1章：基礎基礎、ここは全部理解するようにしましょう、コンテストに出るのもここ全部終わってから。
- 2章：難しい、1章とのギャップがえぐい、特に2.04.参照、2.05.再帰関数はいきなり全部理解しようとすると相当骨が折れる.....、と思ったけどソフⅠのスピードを考えると学科民にはそんな難しくないかもしれん、ポインタもやってるしね。私は受験直後のずっと暇なはずの時期を使ってもここを理解するのに3週間かかりました。
- 3章：なんか今までと違って機能一覧みたいな感じ、どんなことが出来るのかだけ目を通しておいて実際の問題で使えそうだと思った時に戻ってきて都度読み返すのがいいと思ってます。
- 4章：3章と同じく機能一覧だけどよりadvanced、読んでなくても青くらいにはなれるけど4.03.テンプレートくらいは読んでおくと自分でライブラリを作りたくなった時に便利なのかもしれない？......（人のライブラリパクるばっかで自分で作ったことない人）。
みたいな感じです。わかると思いますが完全主観。
４. 次に何をすればいいか
APG4bがある程度終わった（決して全てではない）後に何すればいいかの個人的オススメは冒頭にも貼った以前の記事にも書いたので省略します。宣伝は(ry
mogurin1000000007.hatenablog.com
ただこれ書いた後に一つかなりオススメの教材が出来てたのでそれだけ紹介します、その名も競プロ典型90問。
atcoder.jp
怖いくらい競プロに必要な知識がギュッと詰まった濃縮還元率1000000007%くらいの超良問集です、下手な過去問埋めするより余程効率的にアルゴリズム力（あるごりずむちから）を鍛えることが出来ます。注意点としては決して簡単な問題ではないので自分に合った難易度のものを選んで解いていくことをお勧めします。
ちなみにこの問題集作ったの弊学のB1らしいですよ、近々本も出すらしい、怖くて泣いちゃった。
実は環境構築周りの話はどこにも書いてないんですがこれは私も未だに人に説明できるほど自分のIDEがしっかりしてない、だれかonline-judge-toolsの使い方教えてくれ。
５. 最後に
競プロをやりましょう
競プロをやりましょう
競プロをやりましょう
競 プ ロ を や り ま し ょ う
※学業との兼ね合いは程々に
