競技プログラミングを2020年3月頃から始め、3か月ほどが経過したので、
これまでの感想を書いてみようと思う。
競技プログラミングとは?
競技プログラミングは簡単に言うと、プログラミングを使って与えられた問題を解き、獲得した点数を他のユーザと競い合うことである。
個人的にはメガネを掛けたいかにも頭の良さそうな学生たちがひたすらコンピュータに向かってコードを打ち込み、とてつもない難題を解くようなイメージを抱いていたが、実際は(相当レベルの高い人たちだけしか参加できないようなものでなければ)プログラミング初心者でも容易に挑戦できる内容のものもあり、思ったよりも敷居は低いという印象だ。
またこれは他のユーザーを見ていて感じた事だが、10代後半から20代前半のユーザーが多く、学生がメインであることが伺える。
そして偶然かもしれないが、適当に日本人のユーザーを選びプロフィールを見てみると、東大に所属している人に出会う確率が異様に高い。
筆者の実力
私自身は高校時代は理系であったが大学は文系学部に進学し、理系の道からは離れている。
数学はそこそこできるが、大学レベルの内容となると当然ながら手も足も出ない。
プログラミングを勉強した経験は数年ほどあるが、挫折経験もあり実力はそれほど高いとは言えない。
私は競技プログラミングを始めるに当たって、プログラミング言語を基礎から学び始めることにした。
使用したサイト、言語
競技プログラミングができるサイトはいくつかあるが、今回は日本人ユーザーが多い「Atcoder」で行うことにした。
どのように勉強をしたか?
始めはAtcoderにあるチュートリアルを使い、C++を勉強した。
このチュートリアルはとても分かりやすく、すんなりとC++の文法を理解することができた。
チュートリアルには実際にAtcoderでのコンテストで出題された問題も練習問題として掲載されており、競技プログラミングでどんな問題がでるのかを学ぶこともできる。
チュートリアルを一通り終えた後はとりあえず過去問を解くことにした。
初心者でも気軽に参加できるコンテストである"Atcoder Beginner Contest"(通称ABC)はこれまで100回以上開催されており、膨大な数の過去問題が存在している。
解答解説もあり、他の人の回答も見ることができるので、競技プログラミングに慣れるには最適と言える、
実施されるコンテスト
Atcoderでは1,2週間に一度ほどのペースで"Atcoder Beginner Contest"が開催されている。
それだけでなく、企業によるコンテストやBeginner Contestよりもさらに難易度が高い
"Atcoder Grand Contest"も開催されている。
初心者の場合はBeginner Contestだけに集中するのが良いだろう。
"Atcoder Beginner Contest"は土日のどちらか(場合によっては土日両方開催されることもある)の21時ちょうど(日本時間)に開催され、制限時間は100分に設定されている。
問題は全部で6問出題されるが、初心者の場合は始めの3問を解くのがやっとで、後半の3問はほとんど手を付けられないことがほとんどである。
ABCでの手ごたえ
初めてABCに参加した時は最初の1問しか解くことができなかったが、徐々に他の問題も解けるようになり、比較的難易度が高いC問題が解けることもあった。
これまでABCに10回ほど参加したが、パフォーマンスには差があった。
良い解法が思い浮かばずA問題しか解けない時もあればC問題まで解ける時もあり、参加する際の状態や問題との相性(というか、自分がよく理解している事柄に関する問題であれば解きやすくなる)によって大きくパフォーマンスが変わることが分かった。
ABCの各問題の難易度について
ABCでは全部で6つ問題が出題される。
問題にはA~Fまでアルファベットが降られており、Fに近づくにつれて難易度が上がるよう作られている。
私はA,B,C問題しか解けたことがなく、D,E,F問題については具体的な難易度は分からないためここではA,B,C問題だけに着目して問題に対して感じたことを記述する。
A問題
A問題は非常に簡単で、早い時であれば1~2分で解くことができた。
言語の基本的な文法を理解していれば容易に処理することが可能だろう。
B問題
B問題も大半の問題は簡単だが、一部やや踏み込んだ出題もあり何回か解けないこともあった。
回答時間は早い時で3~5分ほどだったが、予想以上に手こずり30分近くかかってしまったこともあった。
文法事項を理解し、ABCの過去問にある程度取り組めば容易に解くことができると思うが、正答率100%を目指すには隅々まで文法を理解することが必要になるだろう。
C問題
C問題については、一見楽に解けそうだがいざコードを書いてみると計算量が多すぎたり、実行時間が長すぎるなどで不正解になってしまうことが多く、手こずらされる問題が多い印象だった。
またDFS(深さ優先探索)やBFS(幅優先探索)、動的計画法といったアルゴリズムに関する知識がなければ解くことが難しい問題もあるため、C問題を安定して解くにはアルゴリズムの手法を学ぶことも必要だろう。
競技プログラミングに対して抱いた感想
Atcoderの問題に数か月間挑戦してみて感じたことは、何となく大学受験の数学に雰囲気が似ているということである。
数学の知識が求められることはあまり多くはないが、問題からどのようなアルゴリズムを構築すべきかを考え、それをコードに起こすという作業は数学の問題を解く作業と類似しているものがあると思う。
プログラミング初心者ではほとんど太刀打ちできないのではないかとも思っていたが、実際のところ基本、標準レベルの問題であれば簡単に解くことができることも分かった。
レート*1は未だ低いまま(100点台)ではあるが、なんとかそこそこの数値にはもっていきたいと思う。
*1:参加したコンテストでのパフォーマンスを基に算出された、自分の実力を示す数値のこと。レートが400以上になると「色」が付くようになる