祝 入茶
Atcoderのコンテストにはじめて参加したのが、2022/3/19のABC244。
そこから毎週コンテストに参加して、2022/5/14に行われたABC251でやっと入茶できました。
約2ヶ月ほどで入茶できたので、やってきたことをまとめようと思います。
言語はRubyを使用しています。
入茶した時の環境
私の現在の環境ですが、無職です。
なので、あまり参考にならないかもしれませんが、、、。
もともとRubyを学んでいたので、A、B問題は最初から解けましたが、C問題で大きな壁に当たりました。BとC問題の難しさの差は異常です。
下記が私の記録です。
入茶してから時間が立っているので、数値は少し違いますが、600問ほどは解いています。
解けなかった問題は2周しているので、実際はもっと多いです。
最初は灰色と茶色の問題を中心に解いていました。
最近は茶色が自力で解けるようになったので、緑色に手を出しました。
やってきたこと
アルゴリズムの書籍を読む
アルゴリズムについては無知だったので、なんとなく雰囲気を掴むために買いました。
いきなり完璧に理解するのは難しいので、雰囲気を掴んで、あとから読み返すのが私の学習スタイルです。
読んだ本はこちら
問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本
計算量とか専門的なこともこの本で学びました。
典型90問を解く
競プロ典型90問を★１から★３を解きました。
典型問題はとても大切で、完璧に理解するまで何度も解いたほうがいいと思います。
私は典型問題を解いたあと、類題をいくつか解いて理解しました。
いくつかの類題を連続で解くことが理解に繋がると思います。
茶色になるために身につけるべきアルゴリズムは他のサイトでたくさん紹介されているので、検索してみてください。
アルゴ式なんかもおすすめです。
ひたすら過去問を解く
典型９０問が終わったら、あとはひたすらABC過去問を古い順に解いていました。
有志の方が作成したAtCoder Problemsを活用して、難易度が灰色と茶色の問題を解きまくりました。
競プロの問題は前提知識が無いと解けない問題が多いので、私は以下の流れで問題を解いていました。
- ２０分立っても解法の糸口が何一つ思い浮かばないのなら、答えを見る。
そもそも前提知識が無いと解けない問題の可能性が高いので、いくら考えてもわかりません。
さっさと答えをみて、次に活かしましょう - 解法のいくつかの候補があるなら、一番有力な解法を試しに実装してみる。
解法が思いついていても、実装力が無くて正解できないこともたくさんあります。
実装力を身につけるにはとにかくコードを書きまくるのが一番だと思うので、試しに実装してみましょう。 - テストケースが通ったら、提出。結果で判断。
TLE：なにかもう一工夫が必要か、もしくは解法自体が違います。
考えてもわからなければ、答えを見ましょう。
WA：WAの数がテストケースの1/4程度なら、なにか小さいミスをしていることが多いので、
問題や制約などを見返してみましょう。
半分以上WAなら解法が違うことが多いです。
考えてもわからなければ、答えを見ましょう。
AC：すべてACなら正解です。
私の場合、答えをみても理解できないことも多々ありました。
これは知識が足りていないことが多いので、そのような問題は後回しにして、精進してから解き直していました。
また、解けなかった問題は必ず、時間をおいてから解き直しています。
ちなみに難易度が簡単な灰色問題もすべて解いています。
AtCoderProblemsの良いところは成果が目に見えるので、モチベーションにも繋がるし、たまに数学知識が要求されて詰まる問題もあるので、解いておいて損はないと思います。
学習したことをアウトプットする
アウトプットと行ってもNotionアプリを利用して、アルゴリズムや実装方法、解き方の考え方などをノートにまとめるだけです。
見返すことは少ないですが、似たような問題に出会った時や、解き方わかるけど実装方法忘れた！！ってときに役に立ちます。
特に数学の公式・知識はすぐ忘れるので、必ずまとめるようしています。
高校数学
競プロの問題で、倍数、約数、素数、あまり、三角関数、並び替え・組み合わせ、確率など数学知識が要求される問題が茶色問題でも結構出てきます。
私は特にあまり、三角関数、並び替え・組み合わせ、確率が苦手だったので、youtube↓で学びました。
数学は今でも苦手ですが、問題において最初の取っ掛かりがわかるだけでも大きいことだと思います。
計算量を意識する
計算量の詳しい話はしませんが、茶色問題は計算量を意識しないと解けません。
特にRubyはC言語などと比べて実行時間が遅いので、使用するメソッドなども気を使っています。
整数は良いですが、文字列を扱う場合は気をつけたほうが良いです。
Rubyにおける実行時間などTipsをまとめてくれている素晴らしい記事があるので、こちらを何度も目を通すのが良いと思います。
また、リファレンスマニュアルもよく目を通します。
他人のコードを参考にする
これも結構大切です。
Atcoderのコンテストは自分以外の提出もすべて見ることができます。
言語をRubyに絞って、他の人達がどのようなコードを書いているかを見て、自分より鮮麗された素晴らしいコードがあれば積極的に参考にしましょう。
私は問題がACしたあとは必ず他の人のコードを見ています。
自分よりコード量が短い書き方、実行時間が早い書き方など参考にするべき点はとても多いです。
あとはコンテストにひたすら出よう
AtcoderのBeginner Contestは誰でも簡単に参加できるので、A、B問題が解けるようになったら参加してみたほうが良いと思います。
コンテストの数をこなさないと茶色にはなれないので、とりあえず参加して数をこなして慣れるのも大切です。
過去問と違って、時間を気にしないと行けないのでコンテストで得るものも多いです。
解けなかったときはとても悔しいですが、精進して次に活かしましょう。
まとめ
最初の頃は茶色問題が全然解けなくて、何度も挫折しかけましたが、そもそも知識が無いので解けなくて当たり前と気持ちを切り替えて頑張りました。
簡単にまとめましたが、茶色に伸び悩んでいる人にすこしでも参考になれば幸いです。
競プロをやりやすいよう環境構築もしているので、機会があったら紹介します。
転職は後回しで、入緑になるべく精進中です。
ありがとうございました。
コメント