競プロ未経験から3ヶ月でAtCoder茶色になった話。
こんにちは、じっきーです。
僕は競プロの沼にどっぷりと浸かり、始めてから3ヶ月後の2022年11月5日のABC276でついにAtCoderでの茶色レートを達成しました！
入茶しました！！！！記事書きます！！！
— じっきー@競プロ (@Jikky1618) November 5, 2022
343→404 (+61)#AtCoder #ABC276 pic.twitter.com/mMEnjUObRW
茶色になったときは、嬉しい気持ちでいっぱいでした。ただ、この3ヶ月間ひたすら競プロに取り組む上で、苦労した、大変だった点もありました。ですのでこの記事では
これから競プロを始める方、灰色コーダーの方が苦労しないように、競プロを0から初めてどのように茶色コーダーになったのか
を僕自身の経験ですが紹介したいと思います。
また、競プロ界隈の人は色変するとポエムを書くらしい(?)ので、僭越ながら記事にしました。是非、最後までお読みください！
※筆者が記事を書く際に張り切りすぎたため、文字数が約6000字あります。手っ取り早く茶色になるためにしたことを知りたい方は目次から「茶色になるためにしたこと」章まで飛ばしてください。競技プログラミングをあまり知らない方は「そもそも競プロとは？」章からお読みください。
最終更新日: 2024/03/09
そもそも競プロとは？
まず初めに競技プログラミング、AtCoderとはなんぞや？という方もいると思いますので、簡単に説明します。競技プログラミングとは
参加者全員に同一の課題が出題され、より早く与えられた要求を満足するプログラムを正確に記述することを競う。
すなわち、与えられた問題を、プログラミングを使って、制限時間内にできるだけ多く解く競技ということです。AtCoderはそのような競プロのコンテストを開催するサイトで、全世界から約10000人もの方が同時に参加しています。実際のコンテストの雰囲気は、こちらの動画が参考になります。
未経験者のアナタもハマる？競技プログラミング「AtCoder」って何だ？【橋本幸治の理系通信】
AtCoder茶色のレベル感
AtCoderはレート制度があり、1度参加すると灰色になります。またコンテストの結果に応じてレートが変化し、400上がるごとに色が茶・緑・水・青・黄・橙・赤へと変化します。茶色ははじめて色が変わるレートである400なので目標にされている方が多いです。
僕は競プロを始める前、TwitterでAtCoderをしている方の多くが緑や水、青色だったので、「ちょっと頑張ればすぐにそこまで行けるんじゃないか」と認識していましたが、実際は全く異なります。
この図は1600レートまでの累積上位%のヒストグラムです。
小さいですが、よく見ると、茶色の時点で上位24.1%であり、ほとんどのユーザが灰色です。茶色になるのはそう簡単なことではないことが分かると思います。
競プロに出会うまで
僕は高専に通っており、現在2年生です。情報系の学科ですので、以前から競プロの存在は知っていましたが、競プロの勝手なイメージとして、
数学やプログラミングに長けている天才が嗜む競技
なのかなと思っていました。
2022年の7月下旬の頃、パソコン甲子園の存在を知り、そこで全国の高校生、高専生が競プロで競い合っていることを知りました。また、プログラミングに関することを何かしたいなと思っており「ちょっとしてみようかな。」とチャレンジ精神で始めたのがきっかけです。
筆者の初期スペック
競プロを始める前のスペックはこんな感じ。
中学/高校数学は非常に基本的な部分ならなんとか分かる。
プログラミング経験は高専の講義内でのC言語のみで、基本的な知識なら理解してた。(レベルとしてはA問題が解けるくらい。)
アルゴリズムに関するものは全く知らない。
Scratchでのゲーム制作を少しだけしていた。
見ての通りただの一般人です。他の競プロ参加者と比べて、僕は突出して数学やプログラミングができるわけではありません。
ですので、皆さんが茶色を目指す際にどのようなことをすれば良いのかの参考に少しは貢献できると思います。
初コンテスト参加までにしたこと
C++言語の習得
最初の頃は講義でしていたC言語で問題を解いていましたが、最終的にC++を選び、初コンテストまでに習得しました。その理由として
C言語とC++は似ているから習得に時間が掛からなそう。
提出コード、解説など資料のほとんどがC++である。
が挙げられます。
学習をする際にはAtCoderのC++入門教材APG4bがとても参考になりました。第2章までの範囲まで理解していれば、十分太刀打ちできます。
ここでの「理解」の基準は、
その知識を使い、自分で考えてコードが書くことができる
くらいのレベルを指します。
AtCoder Beginners Selectionを解く
C++をある程度習得したら、Qiitaの記事「AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～」を読み、AtCoder Beginners Selectionを解きました。この記事でAtCoderで「どんな問題が出題されるのか」を知り、感覚を養うことができました。
初コンテスト参加
始めてのコンテスト参加はfreee プログラミングコンテスト2022（AtCoder Beginner Contest 264）です。競技中の感覚は今でも覚えており、終始緊張していました。最初のA問題は5分で解けましたが、B問題は当時初めて見たグリッド(マス目)の問題で、80分近く試行錯誤して、鬼のような場合分けをすることでなんとか正解にこぎつけました。
実際に提出したコードがこちら。
今思えば、よくこんなハチャメチャコードで正解できたなと思います笑
結果はA,B問題正解の2完で、順位は6497位。レートは7上がりました。
茶色になるまでにしたこと
初コンテストを終えてから、茶色までにしたことを一言でまとめると、この記事内の「茶色コーダー」で要求される 4 つのこと+過去問演習+αを行っただけです。以下、詳しく説明していきます。
A,B問題を解きまくる
僕は競プロを始めて3週間くらいはB問題に非常に苦戦していました。今だからこそ言えますが、A問題、B問題を解く上で意識するべきことはたった1つだけです。
問題文に書かれていることをそのままコードに落とし込む。
すなわち、A,B問題は実装力のみで正解できる問題ばかりということです。ですので、A問題、B問題の過去問をそれぞれ100問近く解くことで問題に慣れるようにしました。僕自身、実装力が不安があったので問題に慣れるように解きまくったことは結果的に間違ったことではなかったと思います。
B問題までに必要な知識はAPG4bの第2章あたりまでの知識である
入力、出力
変数の概念、四則演算などの計算
条件分岐
繰り返し処理
文字列
浮動小数点
配列
を組み合わせれば確実にB問題を解くことができるようになります。
解法については「答えの可能性があるものを全探索する」「シミュレーションする」の2点を意識すれば8割方の問題は解けるようになります。それぞれの解法について具体的な問題を用いて説明したいと想います。
答えの可能性があるものを全探索する
この問題のキーとなる326-like numberは3桁の正整数であることが前提条件です。3桁の正整数は100から999までの900通りしかないため、3桁の正整数を全てを調べあげることで $${N}$$ 以上である最小の326-like numberを求めることができます。その数が326-like numberかどうかを判定するためにはある程度の実装力を身につけることで自然と書けるようになります。
このように、調べる候補の個数があまり多くない(具体的には $${10^7}$$ 以下程度)とき、候補を繰り返し処理を使って全て調べ上げることで解くことができる問題はB問題でとても頻出です。
シミュレーションする
この問題は $${Q}$$ の制約がそこまで大きくないので、配列 $${A}$$ を用意して、クエリを「そのまま実装する」ことさえできれば、この問題を解くことができます。このように、問題文をそのままプログラムに落とし込むことで解くことができる問題はB問題で頻出です。
稀に数学的思考が問われる問題(ABC249-A, ABC259-B, ABC183-B など)が出題される場合がありますが、そこまで難しくないのでメモを使い考察を書く、調べる等で解くことができます。
C問題にも積極的にトライし、解きまくる
B問題という壁を乗り越えた先に待ち受けているのはC問題の壁です。これがまた非常に難しい。
C問題から実装力に加えて、「計算量」「アルゴリズム」という概念が登場します。B問題に比べて、これらの考察が必要になることで難しくなり、C問題を確実に正解するのにはかなり時間を要します。
ですので、茶色になるためにはC問題を解きまくることが一番大事だと思います。A,B問題をコンテスト中に早く解くことで茶色まで到達することは可能だとは思いますが、その先を目指している方は後々苦労することになります。
コンテスト中はC問題を死ぬ気で通しましょう。
A,Bの早解きよりも、A,B,Cの3完を目指したほうが良いです。
この3ヶ月、茶色達成までにC問題は合計150問解き、ひとまずは慣れたのかなと思ってたりします。
C問題を解く上での心意気として、自分は10分頭で考えたりメモで整理して、わからなければすぐ解説を見るスタンスで進めていました。
基本的にC問題が解けない原因はこの3つがほとんどです。
そもそも解法のアルゴリズムを知らない、定着していない。
考察、思考が不十分で正しい解法にたどり着けなかった。
実装力が足りなかった。
上2つに関しては、考えてもおそらく正解を得ることが難しいので、解説をよく読み、
なぜその解法が思いつくのか。
どのようにして、そのアルゴリズムを利用するのか。
を自分で噛み砕いて、類題が出た際にはすぐ解けるように必ず理解しましょう。YouTubeの解説放送も解法までのプロセスが丁寧に説明されているので、とにかく解法、アルゴリズムの理解をすることが一番大事です。
最後の「実装力が足りなかった。」に関しては解法を見て、正しい解法だと判断したらできるだけ正解コードを見ずに実装して正解させましょう。
ABCには必ず毎週参加する
A,B問題が解けるようになり、C問題の打率が上がったら、コンテスト(特にABC)には毎週参加するようにしたほうが良いです。理由としてはこのTweetの内容にあります。
「AtCoderのレーティングは10回以上参加しないと信用できない」はちょっと嘘で、「10回程度までは低く出てる可能性が高い」という感じ。表示されるレーティングは常に「99%の確率でこのレーティング以上の実力がある」という基準なので、上側はともかく下側は気にしないでいいよ。
— chokudai(高橋 直大)@AtCoder社長 (@chokudai) February 9, 2017
ABCは毎週1回開催されるので10回出場するだけでも3ヶ月かかってしまいます。参考までに、コンテスト参加回数とレーティングの中央値の関係図を見ると、参加すればするほどレートが上昇していることが分かります。
Twitterでこの関係図の反応を見たので追記:
数回で茶や緑色に到達する天才の方もいるため、目安はこの図より低くなると思います。あくまでも参加回数をこなすとレートが増えるということをお伝えしたかったです！
より引用
また、本番はコンテスト時間100分の間、ずっと考えたり、検索したりすることになります。つまり、実力が一番伸びている時間はまさにコンテスト中なのです。どんどんコンテストに参加しましょう。
補足ですが、ARC(AtCoder Regular Contest)に積極的に参加することはモチベーションの観点からオススメはしていません。ARCのA問題はABCのC問題相当以上の難易度で、より数学的思考、考察力が必要です。0完で終わってしまう可能性があるので、こちらには参加していませんでした。
問題のアウトプットを行う
苦戦した問題や解説を見て正解した問題はNotionを使ってメモをしています。後で見返した際「この問題、このジャンルが解けなかったんだな」と確認が素早くできるようにするためです。
また、「もう一度解き直す」ということはしていません。初めの頃はどんどん新しい問題を解く方が重要だと思っています。
学んだアルゴリズムについて
蟻本で挫折
アルゴリズムを勉強し始めたタイミングは競プロを始めて1ヶ月のときです。競プロ内でかなり有名な蟻本を読み勉強しようと思いました。しかし、初級編の動的計画法(DP)で完全に詰まり、灰色コーダーにとって非常に行間が広く何を言ってるのかさっぱりわからない状況で
「え、これ初級編なの。。。（；^ω^）」
と絶望しました。
以降、蟻本を進めることはなく茶色になれたので、灰色から茶色に上がるには必要ありませんでした。蟻本の動的計画法については、他記事で見つけた言及が参考になります。
まずは蟻本(初級編)をやりましょう。
注意点として動的計画法という初心者殺し的なアルゴリズムの存在です。こいつは言ってしまえば、RPGのはじまりの街すぐ近くにいる強いレアモンスターみたいな感じなので、この段階では理解できなくても気落ちせずに次に進んじゃっていいと思う。
二次元の動的計画法がC問題で出題されることが稀にありますが(ABC211-C, ABC242-C, ABC248-C)、それよりも他のアルゴリズムの理解を優先した方が良いと思います。
代わりに鉄則本を始める
蟻本を挫折した以降はアルゴリズムの勉強は敬遠していましたが、2022年の9月、ここぞというタイミングで、鉄則本(競技プログラミングの鉄則)の販売が発表されました。非常に分かりやすい内容でかつ、図が多い！AtCoder上で本にかかれている問題のジャッジも可能なのでアルゴリズムに関しては大体この本+ネットに転がっている記事を見て勉強を行いました。
アルゴリズムの勉強の順番として、まずはじめにB問題で培った全探索の応用版である、Bit全探索、順列全探索から学習することオススメします。僕はかなり時間がかかりましたが理解することができました。
それ以降は以下に書かれている12個のアルゴリズムを鉄則本と合わせて現在も学んでいます。
現時点で学んだアルゴリズム
現時点で学んだアルゴリズムを列挙します。まだ触れていないアルゴリズムは書いていません。以下評価の目安です。
重要度
高: 茶色になる上で必須。
中: 茶色になる上で学習しておいた方が良い。
低: 茶色になる上でそこまで重要ではない。
理解度
A: 一通り理解でき、動作原理や若干の応用も考えられる。
B: 一通り理解した。
C: 勉強している途中、ほとんど理解していない。
見てもらえる通り、茶色に必須なアルゴリズムはそこまで多くはありません。ですので、茶色達成に必要なのはアルゴリズムを使いこなすスキルよりも、実装力、C問題を解く考察力、思考力であると思います。
考察力に関してはある程度典型があるにはありますが、これに関しては問題を多く解き、慣れるしかなさそうです。 こちらの記事はNの制約から解法を考えたり典型的な考察がまとめられているので、過去問を解くときやコンテスト中に参照できるようにしていました。
実績ペタリタイム
おわりに
まだまだ語りたいことが山ほどありますが、ここで語ってしまうと次回の緑色達成記事のネタがなくなるので今回はこの辺で。これを期に競プロに興味を持ってくれた方がいれば非常に嬉しいです。(後半部分は完全に競プロer向けの内容でしたが。)
それでは次回、入緑記事でお会いしましょう。
追記: 入緑しました！！！
この記事が気に入ったらサポートをしてみませんか？