はじめに
こんにちは、ysugiyamaです。今年もそろそろ終わりですね。卒論は...まぁどうにかなるでしょう。
今回は少し前からハマっている競技プログラミングについて少し書いていこうと思います。
対象読者としては、すでにコーディングをしていて競技プログラミングを始めたいけど雰囲気がつかめないという人、他の人がどんな感じの考えをもってるか知りたい競プロ初心者の人を主に考えています。僕自身、今の所競プロ関連でちゃんと参加しているサービスはAtCoderのみで、始めてから半年程度の水色コーダーなのであまり高度なことは喋れないです、ご了承ください。
競技プログラミングってなんだろう
こんな問題が出ます
この項目は他の記事でもたくさん紹介されている気がするのでそこまで力を入れるつもりはありませんが軽く紹介しておきましょう。
Wikipediaさんはこう言っています。
競技プログラミングでは、参加者全員に同一の課題が出題され、より早く与えられた要求を満足するプログラムを正確に記述することを競う。
まぁこういうことですね。「入力が与えられるので、〇〇を満たす答えを出力してください」みたいな形になることが多いです。簡単な例題をみてみましょう。AtCoder Beginner Contest 111 からこの一問。
この問題では入力としてNが与えられるので、「N以上で全ての桁が同じになる最小の数」を出力すればいいということになりますね。
こんな簡単な問題でもいくつかやり方が思いつくかと思います。数字の全ての桁が同じになるまでNに1ずつ足していく方法が一番素直だと思いますが、「全ての桁が同じ」という判定法もいくつかありそうです。数値を文字列に直して一桁ずつ比較するもよし、余りをとって10で割っていくのもよし、３桁であることがわかっているので「111で割れるかどうか」で判定するのもよしです。
また、1ずつ足していかなくても、111, 222, ... 999の9個の数値について「N以上であるか」ということを確認すれば計算は最高でも9回で終わります。これが一番速そうですね。
ここが面白いところで決して解法は一通りではありません。あとで述べますが、他の人の解法を聞く・コードを見ることは思っている以上に得られることが多いのでともに問題を解く界隈を見つけておくことを強くお勧めします。
とりあえず始めてみよう
細かいことは置いといてとりあえずアカウント作って始めちゃうのも賢いですね。日本のもの、海外のもの、有志が作っているもの、様々なコンテストのサイトが存在しますがここではAtCoderをお勧めしておきます。理由としては
- 日本の企業が作ったので全て日本語で書かれている(英語にも対応しています)
- 日本語なので当然日本のユーザが多い
- 初心者の割合が比較的多い
などが挙げられます。今までの過去問はAtCoder Problemsという有志によって作られたページに揃っているので最初はAtCoder Beginner Contestの問題をいくつか解いてみるといいでしょう。
競プロに向いている人・向いてない人
ではこの分野、どんな人に向いているのでしょうか。少しマニアックな世界である以上、どんな人でもハマるかと言われるとそうでもない気がします。僕なりに考えた競プロに向いている人・向いてない人についてちょっと考えています。
数学に対する興味・抵抗
コーディングといえど、かなり頭を使わされるのが競技プログラミングです。いくらコードで何か作りたいというモチベーションを持っていたとしても、例えば数学に対するかなりの苦手意識みたいなものがあったりすると競プロには向いていないと言わざるを得ません。はじめのうちの簡単な問題は言われた通りに書くことで正解できますが、少しレベルが上がってくると数学やアルゴリズムがその多くを占めるようになります。コーディングが好きだけど競プロは向いていないみたいな人は実際結構いて、そういう人たちはおそらく何かのアプリケーションなど形あるものを作ることに快感を覚える人たちだと思います。そのような人たちを無理やり競プロに引きずり込んだところで長続きしないのがオチなので、そこは価値観の違いとして捉えるのが大事なのかなと思ってます。
競争心
競プロのコンテストは基本的に順位が１位からビリまではっきりと決定され、その結果に応じてレーティングが上下するサイトなども多いです。つまり、人と何かを競い合ってその結果に応じてレートを上げていくみたいな作業が大好きな人には競プロは向いています。
僕自身もレートや点数が絡むような競争が大好きで、多分大学入試や資格などの試験を頑張れたのもここによるところが大きいように感じます。競プロでもレートが上下するタイミングになると普段以上のやる気が溢れ出し、いつも以上に結果に対してストイックになります。土曜日の夜などに一部の人が騒いでいるのはレートが上下するコンテストが土曜の夜に行われていることによるものです。
逆に、競争的なものがあまり好きでない人には不向きかもしれません。もちろん、自分のアルゴリズムの知識とコーディングの能力をひたすら鍛錬するために競プロをする人もいるかもしれませんが、モチベーションの維持という観点からすると少し難しいと僕は思っています。僕自身のモチベーションとしては、学科の同期の人が自分よりはるか上のレーティングにいるので抜かしたい、高校同期が気づいたらめちゃくちゃ競プロに染まって強くなっていたので追いつきたい、など競争心にまみれています。受験の時と似ていますね。
何かに打ち込みたい
何か打ち込めることを探している人にはもってこいだと思います。何か自分の好きなことに打ち込みたいけど、せっかくなら今後の役に立つことを選んでおきたい、そんな人には競プロをお勧めします。
先述したAtCoder Problemsというサイトを例にとると、このサイトではAtCoderで今までに出された過去問を全て掲載しているのですが、自分が解き終わった問題は色が変わって表示されるのです。つまり、自分が問題を解けば解くほど表が埋まっていきます。また、各ユーザごとの解いた問題数の比較や、いつどれくらいの問題を解いたかの時系列データも提供されます。ゲームなどでとにかく要素をコンプリートしたい、全部やらないと気が済まない、みたいな人にとってはより競プロにのめり込ませるような重要なコンテンツだと僕は思ってます。こうして競プロerは日々「精進」しなければいけない衝動にかられてよりのめり込んでいくのです。
競プロをやることによるメリット
だんだん競プロをやってみたくなってきたと思います。競プロをやることによるメリットは必ずしも自分のアルゴリズム力や数学力を鍛えることだけではありません。
自分の考えを素早く形にできる
競プロはいかに問題を素早く解くかを重要視するゲームです。したがって、たとえ問題を解く方法をすぐ思いついたとしても、それをコード上に正確に素早く書き起こす能力が必要となります。そのためには自分の思考を素早く整理しておく必要があり、すぐにアウトプットとして提示してあげる必要があります。
この能力は必ずしもコーディングの時にのみ役立つものではないと僕は考えていて、例えば研究において自分のやりたい実験を行うためにどのようなプロットを立てて進めていけばいいか、などのようなプロジェクトマネジメントに活きていくんじゃないかなと思います。ちょっと大げさだったらすみません。
就活に役立つ
これは主に大学生向きですが、最近やっと競プロが就職界隈に注目されてきました。これもAtCoderさんの成果なのかもしれないですね。AtCoderは就職やインターン支援サービスであるAtCoder Jobsを作成し、AtCoderで蓄積したレーティングを条件としてプレイヤーと企業のマッチングサービスを行なっています。
「競技プログラミングなんてマニアックなもの就活には役に立たない」みたいな意見がまだあるのも現状ですが、僕は競プロができる人は開発を行うには十分すぎるくらいの状況整理能力を持っていると思います。地頭は確実にいい集団なので、少し開発のノウハウを仕込んであげることで化けること間違いなしです。あとは最低限のコミュニケーション能力を持ち合わせていれば大丈夫だと思います。そこはみんな大丈夫ですよね...?
コミュニティが増える
これは僕自身が最近実感していることです。競プロを始めたことで同じレベルで競い合っている人たちの情報がたくさん知りたいと思い、ツイッターで同士をたくさんフォローし始めました。すると、高校生ですでにプログラミングをがっつりやっている人たち、同じ大学生で卒論との両立に苦しんでいる僕と同じ境遇の人たち、働き始めてから競プロをふと始めたくなったエンジニアの方達など色々な人が競プロに勤しんでいることを知りました。
また、こないだ僕が運よくCode Thanks Festivalというオンサイトの大会に参加させていただいた時も、同じ分野で精進している人たちとリアルで対面することができ、とてもいい刺激を受けました。その時のことはブログにまとめてあります。→ Code Thanks Festival 2018に参加してきました
またバーチャルコンテストと呼ばれる、本番を模した時間制限つきのコンテストを定期的に開くコミュニティにも参加させていただきました。このグループには主に同じ大学の修士や博士の先輩方を中心に構成されていて、とてもレベルが高いのでいい刺激になっています。共にコンテストの本戦に進んだらリアルで対面したいですねみたいなシチュエーションもモチベの向上に繋がります。
今後の課題とか
どうしてもマニアックな分野である以上仕方がないのかもしれませんが、コミュニティとしてはとても狭いと感じています。高校生であれば筑駒などの有名校が多く、大学においても東大や京大の理系学生が多くの割合を占めています。AtCoderをはじめとする様々な団体の活動のおかげで前よりはかなり有名になっているような気がしますが(僕が始めたのも周りの学生がだいぶやり始めたから)、もう少し社会にとって身近な存在になれば嬉しいと感じました。
最近は初心者向けのめちゃくちゃ丁寧な解説サイトとかも増え始め、初心者からでも始めやすい環境になっているので、「なんか怖そう」という先入観を払拭して競プロデビューしてくれる人が増えることを願っています。
それでも始めからAtCoderは少しハードルが高いという人はpaizaなどから初めてみるのもいいのではないでしょうか。AtCoderよりさ初心者向けのアプローチを丁寧にした感じで、導入にはもってこいだと思います。ある程度の実力があればすぐに物足りなくなるかもしれないので、そうしたら他のサービスにもチャレンジしてみましょう。
お役立ちリンク集
今回紹介した内容に関連したリンクをまとめておきます。
競プロを始めたての人にはおすすめのコンテストサイトで一番のオススメ。全部日本語です。
海外のコンテストサイトがいい！という方はこちらがオススメです。英語の勉強にもなるかも。
AtCoderの過去問集。実は有志で作られていて公式ではないがかなり作り込まれている。
ある程度レートが上がってきたらここを使うと就職やインターン支援が受けられちゃうというサイト。
drkenさんという人が書いためちゃくちゃわかりやすい競プロ入門のためのQiitaページ。
AtCoderの社長chokudaiさんのツイート。競技プログラミングやらぷよぷよやらその他に関する面白くて有益な情報が流れてくるのでぜひフォローしてみてください。
日本経済新聞社とAtCoderが共催するプログラミングコンテスト「全国統一プログラミング王」の開催が決定！本戦の参加条件は日本在住の上位200人！上位500人までは、トークセッションや懇親会に参加することが可能です！出てね！！！！https://t.co/FDZq0fkP7Q
— chokudai(高橋 直大) (@chokudai) 2018年12月4日
だから慶應は学歴自慢じゃないっつーの。慶應という学歴が俺を高めるんじゃない。俺という存在が慶應という学歴の価値を高めるんだよ。
— chokudai(高橋 直大) (@chokudai) 2015年12月26日
おわりに
もうちょっと書きたかったのですがとりあえず公開日になってしまったのでここまでにしておきます。また書きたい内容が思いついたら追記していくかもしれません。一人でも多くの人が競プロに興味持ってくれたら嬉しいです！