こんにちは。リユナと申します。今日は前の記事から続いて、競プロの勉強法についてちょっとだけ話そうとします！
0. 初めに
こんなことを書く前に、私の履歴を先に少し紹介してこそ説得力が生まれると思います。
ーICPC Seoul Regional 2019 13位、2022 7位、2023 4位
ーKOI 2017本選 銅賞
ーBOJほぼ2000問題
ーsolved.ac ダイヤモンド１。全体219位
ーCodeforces max 2224(薄橙)今は滑れちゃってまだ青
ーAtCoderはまだ水
「自慢できるほどすごい実力者！ 」こういうわけではありませんが、それでもそれなりに頑張ってきましたし、自分の考えを書いてみようと思います。Atcoderアルゴリズム黄以上の方々は笑いながら見逃しても構いませんよ。
1. 私は競プロを始めました！
ようこそ！競プロの世界へ！
実はですね。「競プロは初めて！」っていう方々の中でもかなり実力差があると思います。例えばプログラミング自体が初めての方ともうプログラミングには慣れてますが競プロが初めての人はスタートラインが同じだと考えるのは難しいですね。
始める時に意外と引っかかる部分が入出力だと思います。 もちろんプログラミングを学ぶときに一番最初に学ぶ部分ですが、意外と競プロで使われる入力はいろいろあります。 おそらくすでに慣れている方々は、この部分を大きく考えていないので、さらにアドバイスを受けにくい部分でもあると思います。もしこれでなんか問題ができたら、ぜひ！ここからじゃんとして始めましょう！
その次は時間複雑度/空間複雑度の概念についてある程度理解することだと思います。 言語によって、どの言語はどの動作をするのに何秒かかるのか、どのようにコードが制限を超えないのか、そのような感覚がちょっとでも取れていることが重要です。
例えばですね。Nの大きさによってアルゴリズムの時間複雑度はほぼここまでができます。(絶対的なことではないです！)
<10 : O(N!)(全探索などできます。)
<25 : O(2^N)
<100 : O(N^3)
<5,000 : O(N^2)
<500,000 : O(NlogN)、たまにO(NsqrtN)まで
<5,000,000 : O(N)
<10^12 : O(sqrtN)
<10^18 : O(logN)
大体こんな感じです。
あと、言語はC+＋がおすすめです！私はPythonを中心にしていますが、長所と同じくらい様々な短所(速度など)を持つ言語なので、Pythonを通じて競技プログラミングをするなら、様々な最適化技法や時間をできるだけ減らす方法などについての理解が必須です。
2. 何をすればいいんですか？
自分の意見ですが、競プロに必要な能力は大きく二つだと思います。
1. 実装
2. (アルゴリズムなどの)知識
その二つのバランスを取りながら進むことが大切な部分だと思います。ちなみに、私は実装が弱点です。知識さえも特定の分野に重点を置いていますが、皆さんは私のように偏食しないでください。その為には知識として学んだアルゴリズムや資料構造は、一回でもできる限り自分の力で実装してみる練習をすることが大事だと思います。
2.1. まずは興味があることから！
何をするにせよ、最も重要なことは情熱と興味を失わないことですよ！モチベーションが死んでしまったら競プロをやる理由もなくなるなと思います。(あくまで私自身の意見です。)それをためには、まずは好きなことから始めることをお勧めします！
「あれ？そうやってもいい？偏食じゃない？」って思うかもしれませんが、偏食してもずっとやり続けるのが何もやらないのよりはもっといいです。多くの人は「やってみましょうか」で考えが止まり「やる！」につながることがよくありません。 スタートでもするなら、もう既に上位20%だと思います！
好きなスタイルの問題をたくさん解いてみて、悩んでいるうちに他の要素が混ざっている問題も発見できるようになります！たとえば、私は数学が大好きですが、数学的要素がありますが、他の資料構造（セグ木など）を使って時間の複雑さを減らさなければならない問題に接し、セグ木なども勉強し始めました。 そして漸化式を立てて解く問題は本質的に動的計画法の一種だということを後で知り、その部分も勉強し始めました。
2.2. 良問を解いてみましょう！
AOJやBOJなどのOJサイトではあらゆる問題に触れることができます。もちろん、すべての問題を解くことができればいいのですが、単純に多量の問題を解くよりも、考えさせ、良いチップを与える問題に接することが重要だと思います！
私のおすすめはこんなことたちがあります！
ーAtCoderの過去問
この文をお読みの方なら、おそらく高い確率でAtCoderでのレーティングを狙われると思います。 個人的な考えですが、韓国国内や海外の様々なプログラミング大会などをさまよっていましたが、アトコーダーは中でも確かに問題の質が保障される良いプラットフォームだと思いました。
でも大会は週に一回じゃないですか？ では、1週間に1回だけ競プロの練習ができるでしょうか？ もちろん違います。 過去の問題を解いてみると本当に役に立つと思います。私はAtCoder Problemsのようなところを愛用しています。
ーUSACO/KOI/JOI/COCIのような色んな国家の情報オリンピックの過去問
このような大会の基本的な特徴としては、少ない数の問題を与え、一人一人が長い間悩みながら解かなければならない問題だということです。自然に出題される問題は単純に難しいだけでなく、色々な方法で考える能力を育てる方だと思います。
また、このような有名大会の問題はインターネットに解説が着実に掲載されていることが多いです。 解説を見ながらどんなテクニックがあるのか、確実に自分のものにすることが大切だと思います。
KOIは韓国の情報オリンピックです。「負うた子より抱いた子」っていうでしょう。私が韓国人なのでKOIを推薦せざるを得ませんでした(笑)もちろん私もJOIの問題もたくさん解きましたから、どうか許してください。
COCIはクロアチアの大会ですが、かなりいいです。こちらの問題も練習に使えばいいなと思います。
ーcodeforcesはどんな感じか試してみる！
世界的に最も多く利用されている競プロサイトはおそらくcodeforcesの方です。 開催時期も不規則で、(韓国/日本標準時基準)夜11時35分という曖昧な時間に大会が開かれ、問題や文章のクオリティもギザギザしていますが、それでも良い問題もたくさんあります。しかし、全部英問ですので、英語の実力がちょっと要ります。もしかしてロシア語が上手いならそっちで説いても構いませんが、多分みんなそれでも英語の方が易いと思います。普通第1外国語が英語ですからね。
(あれ？私は確かに第1外国語が英語で第2外国語が日本語だったのに、なんでAtCoderの問題を全部英語じゃなくて日本語にして解いてる？)
ちなみに、AtCoderとcodeforcesは問題が若干スタイルが違います。 うーん、言葉で説明するのは難しいですが、どちらも何回か参加してみれば、何を言っているのか理解できることだと思います。（無責任すぎる）
AtCoderとCodeforcesの難易度を比べたら大体
Div 3<ABC<Div2<ARC=<Div1<<AGC
のような感じです。
2.3. 分からない場合には解説を！
「ええ？それじゃ実力に役に立つの？」って思うかもしれません。ある程度はその通りです。 しかし、これは「知っている範囲で解ける問題」の時の話であり、「全く知らない資料構造やアルゴリズム、テクニックが必要な問題」なら悩むのは時間の無駄に過ごすことです。
もちろん、10秒で答え見る天才競プロer！とかになろうという意味ではありません。 あなたは多分、知らない場合にも「あ、これどうにかすれば解けると思うが、時間の複雑さの制限にかかる。 これを最適化するにはどうすればいいの？」のような状況であることが多いと思います。 こんな考えに達したのであれば、これの方法を少し考えてみるのもいいでしょう。 実際、多くの場合、そこから出発して時間を徐々に減らしていくことが実際に解釈が正しいからです。
ある程度悩みが終わりました。 あるいは「最初から知らない概念の問題のようだ」と感じたら解説を探してみましょう。そして、何よりもそれを自分の手で実装してみて、自分のものにじゃんと習得すれば最高のシナリオですね。
2.4. 錯覚すんな！あなたはまだ理解してない！
どんな概念がどのように作動するのか知り、それを通じて簡単な問題を少し解いてから「わぁ！ 私はもうこれを理解しました！ これが出てくる問題はすべて解けるだろう！」と勘違いすることがよくあります。
全然違います。あなたはまだ理解してない、または原理は理解したが実戦で使いにくい状態である確率が高いです。なぜなら意外と簡単な理由です。 皆さんが別々に勉強する時とは違って、実際の大会で問題を解く時は「どのようなアルゴリズムで解かなければならないのか」教えてくれないからです。セグ木を例にとってみましょう。
1. セグ木の概念をどこかで読む。うーん、分かった！
2. どこで使うのかを勉強する。うーん、なるほどね？
3. 実装してみて何個の易いセグ木の問題を解いてみる。うーん。行ける行ける！
4. よっしゃ！もう私はセグ木を理解した！楽しい！
5. 実際の大会にこんな問題が出てくる。あれ？
6. 何もできず沈没.。
7. あとで誰かに「あれセグ木をめちゃくちゃおにゃららしたら解ける！」って聞く。
8. おかしいな。私は確かにセグ木の勉強をしてたのになぜ？
お気づきかと思いますが、実は私の実話を脚色したものです。(笑)多分私じゃなくてもみんな一回はこんな経験があると思います。それは先ほども言ったように当然まずは「それがセグ木を利用する問題だ！」と大会では教えてくれないからです。
しかし、それだけではありません。多分セグ木を初めて習って「あれはセグ木の問題ですよ」って言われてもそれをどう使うのかは一気に理解しにくいです。しかし、もしあなたがこんな問題を(*韓国語です)悩んでみたことがあるなら、もっと答えに接近しやすいとおもいます。簡単にネタばれをすると、セグ木のノードに1つだけ保存するのではなく、各区間の様々な要素(が何かは自分で考えてください。)を保存して、アップデートの時に次の段階に進んでも最大限問題が発生しないようにすることが核心です。
どうですか？応用することはできるでしょうか？
実はですね、私もセグ木のこと、大嫌いです。もし私がお母さんになったら、私の子供には「セグ木のような悪い子とは遊ばないで！」と教育します。(笑)それはなぜかと言ったら実装の難しさもありますが、応用の膨大さがもう一つの大きな原因でしょう。おそらく赤コーダーだとしても、競プロで使われるすべてのセグ木の応用を知っているとは思いません。
あなたが1、2回解いてみた問題、1、2回実装した資料構造だからといって、あなたがすべてを理解するわけではありません。 この点に気をつけながら、いつも初めて学ぶ気持ちで新しい問題を悩んで学べば、はるかに良い成果を得られると思います。
2.5. 数学もはっきり！
結局ですね、競プロにして数学の要素も大きい部分です。動的計画法の漸化式やグラフ理論、幾何や整数論などがあるでしょうね。これらの勉強もせめて競プロで使われるほどは勉強して置いたら役に立ちます。
もちろん、いくら私が数学が好きだとしても、競プロに数学が事実上すべてである問題が出るのがそんなに良いとは思いません。 それならAtCoderではなくOMCに出なければなりません。そして実際の大会でそれほどの問題が出ることもほとんどありません。 しかし、数学的な概念をある程度知っていれば、はるかに簡単に接近ができる問題や時間を減らしたりするなどの問題がかなりあり、これを簡単に解くためには数学の勉強も必須だと思います。例えばこれは私の好きな問題です。(英問です。)数学的な知識と二分探索という競プロのアルゴリズムが合わせて解ける問題です。 数学が必要ですが、プログラミングの存在も一役している問題だと言えますね。 しかし、基礎的な平面幾何学を知らなければ、最初から始めるのが難しいので、結局数学能力もたくさん必要です。
もちろん、この記事の本論はあくまでは競プロですから、数学だけの勉強に夢中するのもあまり良いことではないと思います。 そうするうちに私のようになりますし、数学科に行ってしまう悲劇(?)が起こるかもしれません。
2.6. 達人たちに聞いてみて、ライバルと一緒に成長しよう！
競プロのコミュニティには数多くの達人たちがいらっしゃいます。おそらくその中にはこの文を書いている私よりずっと実力者の方も多いと思います。そんな方々がどのように勉強してきたのか、どんな問題を解いたのかをそばで見守るのも勉強に大きく役立ちます。 また、本当にわからないことがあったら聞いていただければ、快く答えてくれると思います。 何よりもその「解けた！」の楽しさを共有したい人が多いですから。
もちろん、相手は無償で好意を寄せていることは覚えておくべきです。 手伝うことが絶対義務ではないですし、助けてもらったなら感謝の挨拶もしっかりした方がいいと思います。
そして、自分がどんな実力であれ、似たような実力の人々にも出会うことができます。 善意の競争をするライバルがいれば、自分と相手の両方がシナジー効果によって大きな成長を収めることができます。 もちろん勝負に執着しすぎるのは自重しなければなりませんが。（そうでなければ私のように大学卒業さえ延々と先送りする競プロ悪鬼になります。）
3. 終えて
あなたが競プロをしようとする理由はさまざまでしょう。私のように単純に興味や競争心のためかもしれませんし、就活の準備やプログラミングの実力を伸ばすためにもするかもしれません。しかし、その理由がどうであれ、長く悩んでいた問題をやっと解いた時の「解けた！」という喜びは同じだとと思います。
まあ、「競プロ無用論」や「早くやめとくほうがいいな」っていうことも、前にも言ったように両国のコミュニティでたくさん聞ける言葉ですが、結果がどうであれ、あなたが一歩ずつ前に進むために悩んだ時間は嘘ではないと思います。そのように情熱を注いだ経験がこれからの競プロや、じゃなければ他のどの分野でも、少しでも役に立つのではないかと私は思います！その道の上に立っているみんなを心から応援します！
読んでくださってありがとうございます！
