AtCoder で入茶するまでにしたこと

0. はじめに

2023年の5月から、友人から勧められて本格的に競技プログラミングをやろう！となり無事入茶することができたので、未来の自分へと、これから始めて入茶を目指す方々に参考になればということで色変記事を書きました。

1. 自己紹介

情報学部に通っている大学2年生です。
趣味はプログラミングとゲームを遊んだり作ることですが、数学はあまり強くありません。
競プロはPythonでやっていますが、実はそれまでにPythonに触れたことがなく、競プロで初めて触れました。競プロを始める前に少しゲーム開発みたいなことを高校生のうちにしていたので、少しだけ実装経験がありました。

2. 何をしたか

最初に、dr.ken さんの記事を参考に、AtCoder Beginners Selection を解き、どんな形式で入力が与えられるか、どんな問題を解くものなかを体験しながら解き進めました。下2個のC問題は当時ではやや難しく感じたので、それに関してどうしたかは以下の「雑多なこと」で詳しく述べます。

次に、最初のコンテスト ABC301 に出たのですが、結果は2完でした。今思えばよくBまで解けたと思いましたが、CとDが解けなかったのが悔しくて、コンテストを受けてその後に解説をみて「あと少しで通せたのに！」と思った問題を実装するということを ABC で繰り返しました。こうすることで、新しいアルゴリズムを習得(例えば二分探索とか)すると同時に、「こういう時は○○で計算量を削減できるのか」or「○○で実装できるのか」 と自然にアルゴリズムを習得できたので、後で述べる早解きにつながったと思います。

3. コンテストの出方

参加回数が少ないうちはレートが低く出るらしいので(出典)、取り敢えず何も考えずに全て出てました。¹
ABC では、しばらく2完が続きましたが、ABC305 で初めて3完ができるようになりました。ただ、3完して気づいたのが、時間がかかって3完するのと素早い2完ではパフォーマンスに大差ないことに気付きました。そこで、AtCoder Problems を使い、知識の穴を埋める役割も兼ねてA, B問題を解き、速く解くことを意識しました。また、速く2完することで、C以降に使える時間が増えるので、3完、4完²を取りやすくなったと実感しています。

初3完した ABC305 ではAを1:02、Bを4:34で解き終わりそれ以降順調にパフォーマンスを伸ばせました。

4. 雑多なこと

1. 楽しめる範囲で、無理をしないこと

自分は「レート」のような数字が上がっていくのと、解ける問題が増えていくことに楽しみを感じていましたが、これだけだとスランプにはまったとき恐らくやめてしまいます。なので、「解ける問題が増えた」や、「○○を使いこなせるようになった」など自分の成長をしっかりと感じてあげる(?)と、モチベが維持しやすいと感じました。あとは、Twitterなどでも競プロerがたくさんいて、みんなとても優しくて、コンテスト後に解法を呟いてたりするので競プロ用にTwitterをしてみるといいと思います。

また、自分が勧めたのもあって同時期に、AtCoderを始めてくれる人がいました。なんと同じレベル帯だったので、問題の解法を共有したり、コンテスト後に雑談したりと楽しくできました。
このように、Discordのスレッド機能を活用して、よさげな問題を探して解き合ってました。
ほんとにありがとう

2. なぜPythonなのか

実は最初、Javaで競プロをしていました。ですが、毎回main()を宣言しないといけなかったり、ファイル名の制約が個人的にストレスで、あまり多く書かなくていい Python を使うことにしました。そうすることで、速く解ける他に、Python では多くの競プロ記事があって、参考にできたので良い選択肢だったと思います。C++ と比べると確かに処理は遅い³ですが、前述したように書くコードの量が少なく済むので、バグらせにくかったり実装が楽になると思います。

Python環境ですが、自分は PyCharm を愛用しています。

3. 入茶するまでに触れたアルゴリズム/データ型

恐らく以下の全てのアルゴリズムやデータ型の知識は必要ではありません。早解き2完で500パフォはコンテストによっては狙えるので、必要ではないですが、パフォが高い方がより早く入茶できるので参考程度に載せておきます。

• 全探索⁴
• 二分探索⁵
• (貪欲)⁶
• DP
• DFS/BFS
• キュー/スタック (deque)

4. 解いた問題とか

「あれこれもしかしていける..?」と感じた問題や、Diff 300 - 800 ほどの問題を割と解きました。当然難しいので、移動中とかふと空いた時間に解法をぼんやりと考えてたりしました。
今思えば単純に次の色を目指す場合、自分の色の問題を早く解けるようなればいいと思いました。

AtCoder Problems の Streak (連続何日で新規ACをしたか) も精進のモチベになっていましたが、切らしてしましました。

5. おすすめ拡張機能

AtCoder Easy Test

最強です。サンプルを提出前に簡単にテストできます。
ただ一部非対応(AC判定ではあるが、完全一致しないのでWAとなる問題)なので、そこだけ注意が必要です。

Comfortable AtCoder

問題のところにマウスを合わせると問題の一覧が見れます。地味に便利です。

5. 終わりに

初投稿で、長い記事となってしまいましたが参考になると幸いです。初めての色変ですが、思ったより大変だったものの、始めたときより大きく成長したと感じて、非常に嬉しいです。競技プログラミングという素晴らしいコンテンツを提供してくださってる方々には本当に感謝しきれません、本当にありがとうございます。

先ほど述べたように初投稿ということもあり、誤った情報を載せていたら指摘してくれるとありがたいです。

追記 - C問題に関して

他の人の記事でも触れているかもしれませんが、C問題は規則性を見出すか、辞書型などの適切なデータ型で計算量を減らすなど工夫の必要である意味、手強い問題が多いとも感じました。
個人的な経験上、PythonであればDict(辞書)やSet(集合型)が刺さる問題が多かった気がします。特にSetであれば、要素が含まれているか (x in s) が $O(1)$ とlistより高速で行えるので参考になれば幸いです。

1. 最初のARCはA問題が水diffだったこともあり、0完となった上に、解説を見ても理解できそうになかったので潔く諦めました。 ↩

2. 初めての4完は推定1057パフォのUnratedとなりました・・ ↩

3. C, D問題以降は高速化のためにPyPy3を使って提出していますが、文字列結合や再帰関数などPyPyにも苦手なものはあるので、どのような処理が遅くて速いかは調べたほうがよいと思います。 ↩

4. 最重要です。自分も舐めて最初は適当にしていましたが、順列全探索など、制約上どのようにして全探索するかすぐわかると解ける問題が増えると思います。詳しくは: https://qiita.com/e869120/items/25cb52ba47be0fd418d6 ↩

5. Pythonだとbisectライブラリで簡単に使えるのでおすすめです。ハマれば $O(N^2)$ を $O(N \log N)$ まで落とせます。噓解法というかゴリ押しでスタックの問題をこれで通せたことがあります。 ↩

6. 無意識にしているアルゴリズムの一種かもしれませんが、意識することで解法がより鮮明になったりします。 ↩