はじめに
先日のABCで入緑しました！！（2023/10/14）
ヒューリスティックも緑になりました🟩（2023/10/22）
これから競プロを始めようとしている人や緑を目指している人のためになればと思って書きました。
拙い文章ですが読んでいただけると幸いです。
自己紹介
- 文系学部 B1
- 競プロを始めたのはB1の5月（それまではプログラミングほぼ未経験）
- 使用言語：Python
大学に入ってからプログラミングのサークルに入り、そこで競プロに出会いました。
競プロ始めるまでは、HTML,CSS,JavaScript等をちょっとだけかじってるくらいで、Pythonは使ったことがなかったです。
大学は内部進学だったので高校では勉強しておらず、数学力はほぼありませんでした（logや組み合わせがわからないレベル）。
言語はPythonを使ってます。
緑まではとりあえずPythonでも困らないと思います。1
テンプレート（def il=input().split()みたいな）はレート700くらいの時に作り始めました。結構コード書くのが楽になったのでテンプレートを作っておくのはおすすめです。
ローカルのテストはAtCoder Online Judgeを使っています。
入緑までにしたこと
【精進方法】
初めのうちはとにかく問題を解いていた気がします。
問題を解く → 解説読む → 何人かの提出コードを見る or 他の解説記事を検索する → わからないアルゴリズム等があればその都度調べる を繰り返してました。
ABC-A,Bが解けるようになったくらいの時に「競技プログラミングの鉄則（通称：鉄則本）」をやり始めました。
二分探索など初歩的なアルゴリズムを学ぶきっかけになったとてもいい本です。2
この本は星2〜星5まで難易度が別れていて、入茶までは星3、入緑直前に星4〜5まで埋めていた気がします。
二部マッチングやフローなど難しいところは飛ばしてますが、8割くらいの問題は解きました。
典型90は自力AC or 簡単に解説ACできるところだけ埋めて残りは放置しています。
過去問は入緑までにABC-Cは8割、Dも4割は埋めました。
10分問題を見て、わからないやつはとりあえず解説ACせずに後日に回すようにしてました。
すぐに解説ACすると考察力が落ちそうなのと、後日解いてみたら自力ACできることも多いので、とりあえず後回しにするのはいいと思います。
自力ACの問題でも、他の解法があれば解説を読むようにしていました。
解説がC++で書かれている時は、「AtCoder ABC○○ Python」で調べるといくつか記事がでてくるのでそれを参考にしていました。
参考までにABCの解いた問題数を貼っておきます。(画像は入緑から1ヶ月程経っているので入緑のときは解いた問題は680問くらいでした)
【学んだアルゴリズム】
アルゴリズムはNotionにポイント,注意点,実装例などをまとめて、コンテスト中見返せるようにしていました。
Notionにまとめることで、学んだアルゴリズムを一覧で見返すことができるので個人的におすすめです。
新しいアルゴリズムを学ぶときは、各アルゴリズムの計算量とどんなことができるのかを理解することを意識していました。
特にそのアルゴリズムが適用できる条件を整理しておくことが重要だと感じています。（二分探索なら単調増加、ダイクストラ法なら負の辺NG など）
そうすることで、問題や制約によって適切なアルゴリズムが思いつくようになると思います。
【入緑までに学んだアルゴリズム】
| アルゴリズム | 理解度 | コメント |
|---|---|---|
| 二分探索 | ◎ | めぐる式？についてはわかってない |
| DP | ○ | 復元、状態DP(耳DP)、bitDPも学習しました |
| DFS,BFS | ◎ | 最近は非再帰で書いてます |
| ダイクストラ法 | ○ | 入緑直前くらいに学習しました |
| UnionFind | △ | 仕組みは5割くらいの理解ですが、コンテストで何度かでてきたきがします |
| 最小全域木 | ○ | プリム法で学びました |
| SortedSet,SortedMultiSet | ○ | （アルゴリズムではないですが）Pythonを使うなら必須だと思います |
| セグメント木 | △ | 仕組み8割くらいの理解です |
・その他の学習したアルゴリズム等
bit全探索、メモ化再帰、ランレングス圧縮、座標圧縮、累積和、Decimal
Pythonならリスト、セット等の計算量を把握しておくことは必須だと思います。(Setはin演算子がO(1)、ListのinsertはO(N)など)
余裕があれば整数などの数学問題、トポロジカルソート、二部グラフ、区間DP、転倒数あたりも勉強しておくといい気がします。3
UnionFind、セグメント木などは、ネットからパクったコードを自分が使いやすいように改造・高速化してライブラリを作ってました。
【その他】
コンテストでは、A問題は1分、B問題は3分など問題ごとに目標タイムを決めて参加していました。
だいたい4完か早解き3完で緑パフォなのでこのあたりを目標にしていました。
5分考えて解法が思いつかない問題は飛ばして次の問題を見る、順位表を見てAC数から解けそうか判断するなども結構効果的でした。
僕は数学問題が苦手でグラフ系は得意だったので、問題との相性を見極めて解く順番を決めていました。
入緑までにどのくらいの時間競プロに使っていたかは日によってバラバラでした。
僕は趣味として競プロをしているので、1日10時間以上使う時もあれば全くしない時もありました。
平均して週5〜10時間は競プロしていたかなと思います。
コンテストの参加回数は入茶までに7回、入緑までで20回でした。
ARCはratedでは参加したことがないです。
とりあえず参加できるABCに全部参加すれば、おのずとレートは上がっていくと思います。
モチベーションの維持に関しては、僕は競プロが楽しくてやっているのでモチベが下がることはほとんど無くなんとも言えないです...
もともと向上心が強く、レートが上がっても下がってももっと強くなりたいと思うのでそこは自分の強みだったのかなと思います。
ヒューリスティックについて
ヒューリスティックをやりはじめたのはアルゴのレート700くらいのときでした。
アルゴでPythonを使ってるのでヒューリスティックもPythonで出ています。
入緑までに3回しか参加できておらず、ほぼアルゴの知識だけで解きましたがそれなりにいいパフォーマンスがだせました。
まだまだヒューリスティックはわからないことだらけですが、コンテスト終わったあとにいろんな人の解法をみたり上位の人の解法を実装してみるといいのかなと思ってます。
ヒューリスティックも楽しいのでもっと参加者増えて欲しい！！
プログラミング未経験・文系大学生という目線から
前述の通り、競プロ始めるまでプログラミング未経験(広義)かつ文系大学生だったので、その視点から感じたことを書こうと思います。
僕は競プロを始めるまで「プログラミングは理系のもの」「やっとことないし難しそうで自分にはできない」と思っていました。
しかし入緑したいま、そのような先入観はほぼ間違っていたと感じています。
もちろん、理系的なことが必要なことも0ではないですし、開発系などに比べると競プロは数学など理系要素が求められると思います。
一方で、AtCoder入緑に限って言えば、必要だった理系要素は整数論(合同式、素数)くらいで、1番難しくてフェルマーの小定理くらいでした。(RSA暗号が理解できるレベルで入緑には十分でした)
この程度のレベルなら文系の方でも理解できると思います。
ABCでもたまに数学問題はでますが考えればわかるような問題も多いですし、理系だからといって全員が解けるわけでもないのでそこまで大きな差はつかないと思います。
普通にコードを書く分には理系要素はほとんどありませんし、文系だからというのは関係ないなと思いました。4
また、実際にプログラミング初めてみると案外簡単にできることも多く、書籍やネットの記事も充実してるので、難しくて自分にはできないという考えもなくなりました。5
長くなりましたが、1番伝えたいことはプログラミング未経験だから・文系だからとしりごみするのはもったいないということです。
私は、競プロを始める前と後では見える世界が大きく変わり、競プロを初めてほんとによかったと思っています。
いまもしプログラミング・競プロを始めるか迷っている人がいたら、とりあえず始めてみてほしいです。
全人類競プロをしよう！！！
おわりに
この記事が少しでもためになっていれば嬉しいです！！
ちなみにこの記事を投稿したのは2024年2月で入緑から4ヶ月経っていますが、
レートは Algo：949 (highest:1023)、Heu：1337です。
まだまだ水色まで遠そうですがこれからも頑張りたいと思います！