色変記事 AtCoder緑色の教材まとめ
はじめに
緑色になったので色変記事というものを書いてみようと思いましたが、検索すればたくさん出てくるので、ここでは勉強のために利用してきた教材に特化してまとめておきます。
教材一覧
- ABC 過去問
- 競プロ典型 90 問
- DP まとめコンテスト
- AtCoder 版！蟻本 (初級編)
- 競技プログラミングの鉄則 演習問題集
ABC 過去問
以下リンクは解いていない問題を素早く見つけられるサービスです
この教材で勉強する目的
一番の目的は問題文に慣れることです。AtCoderの問題文は独特なものが多く、初見では理解するのに時間がかかったり、誤解する場合があります。
また、緑色を目指すうえで解かなければならないC~D問題で、問題文通りの実装ではTLEするという点が課題点になります。
これをクリアするためには問題文に書かれていることだけでなく、計算量のボトルネックをを把握する必要があります。
問題文や計算量のボトルネックにはある一定のパターンがあり、過去問を解くことで慣れることができます。
パターンに関してはいかが参考になります。
この教材のメリット
ABC043以降は解説放送を見ることができます。
解説放送では解法を知ることができる以上に、どのようにしてその解法を思いつくことができるかという思考法に触れることができます。
YouTubeのvideoIDが不正です
この思考法によって、問題文に対する読解アプローチを鍛えることができるため、問題文に慣れるという目的に対して適切です。
競プロ典型 90 問
この教材で勉強する目的
競プロで必要とされる前提知識を得ることです。
この教材のメリット
この教材は、過去問に比べて網羅性で優位にあります。
なぜなら、過去問では一回に様々なテーマを含めるというよりも一回ごとにあるテーマを深めるよう場合が多く、典型的な知識を得るため以上に問題を解く必要が出てくるからです。
DP まとめコンテスト
この教材で勉強する目的
DPを理解することです。
DPはそのシンプルさと拡張性から多くの問題で想定解法となっていますが、それゆえに理解することが難しくなっています。
解説放送でもいきなり「DPをします」になるパターンがよくみられ、DPに対する基本的な理解が前提として求められます。
基本的な理解を得るために問題を解くとこは有効です。なぜなら、自分で実装をすることで、わかっていない部分や間違っている部分を見つけやすくなるからです。
しかしそれでもDPの実装はシンプルになりやすく、自分で実装といっても写経になってしまい理解できないこともあるかと思います。
そこで、DPに対する基本的理解を簡潔に書き残します。
「DPの基本は状態遷移」
これは解説文で遷移式として表現されるものです。
「計算量が減るのは状態が独立しているから」
ここでの状態は、DP配列の1要素といえます。
独立というのは、どのような遷移で値が決まったのか（遷移の順番）が値に影響しないということです。
この教材のメリット
AtCoderにはあまり見られない、ひねりのない問題文で書かれている点です。
そのため、DPというテーマのみに集中することができます。
AtCoder 版！蟻本 (初級編)
この教材で勉強する目的
蟻本は今となっては古い教材ですが、AtCoderの問題作成者さんは読み込んでいる方が多いと思います。
そのため、問題のもととなった考え方から理解するためのステップとして有効です。
この教材のメリット
蟻本の例題を解くにはやや課題点があり、AtCoder版が作成されています。
競技プログラミングの鉄則 演習問題集
この教材で勉強する目的
競プロで必要とされる前提知識を得ることです。
この教材のメリット
AtCoderのジャッジシステムを介して、豊富な練習問題を解くことができる点です。
この点は、競プロ典型 90 問も同じですが、こちらはテクニックというより概念を理解するための解説が充実しています
おわりに
ここまで読んでいただきありがとうございます。
書いてみて思いましたが、緑になるための前提知識はそこまで多くないのですが、それを問題ごとに使いこなすことが難しく、そこが水色との差になっています。
chokudaiさんの色評価には、昔よりも難易度が１段階程度上がっている（緑の基準なら水色の基準が要求されている）といった話を聞いたり、自分でもそうだとおもっいましたが、知っていることと使いこなせることには開きがあり、実際に自分に解ける問題の範囲を考えるとこの評価は適切だと思うようになりました。
記事を書くということも、自分の頭の中にある考えを文章としてある意味実装することのように感じます。
この色変記事は緑になったうれしさの反動で書いた部分もありますが、水色を目指すうえで課題点をはっきりさせることができ有用だったと思います。
この記事の冒頭で書いた通り、色変記事はすでに多く公開されていますが、それを自分で書くということは別問題で、読んでくださったみなさんにもおすすめです。
以上です。
Discussion