はじめに
高校2年生になりました,nasuo_71です。
この間行われたABC412で,ついに悲願の初入茶を果たすことができました！!
言いたいことが 3×10⁵ 個ほどあるので,まずは色変するまでの過程を振り返っていこうと思います。
入茶のためにやったこと
0. APG4b python,AtCoder Beginners Selection
1. 過去問精進
2. 数学の基礎固め
3. アルゴリズムの勉強
0.APG4b python,AtCoder Beginners Selection
APG4b python
AtCoder Beginners Selection
まずはここから。この二つをやりきれば,情報オリンピックの一次予選を突破できるレベルにはなると思います。
1.過去問精進
AtCoder Problems と AtCoder Novisteps。
過去問精進したい時に最新の問題から埋めていきたいならAtCoder Problems,難易度順に埋めていきたいならAtCoder Novistepsがおすすめです。
Novistepsの方には「問題集」というものがあり,単元や難易度でまとまっているので初心者にはおすすめです。
一方でProblemsの方には recommendation という機能があり,自分の実力に近い問題をおすすめしてくれます。ハードですが力はつきます。
また,私は解いた問題の考察を言語化して残しておくために scrapbox というサイトにまとめています。
こんな感じ。
2.数学の基礎固め
C問題は、数学の知識があるとないでは見方が大きく異なりますし、解答に辿り着く時間も大きく変わります。
例えば、累積和を扱う問題一つとっても、数列の知識があるかないかで大きく変わります。
やっていること自体は高尚なことでなく、S_n-S_n-1=an のシンプルな数式一つを隠し味としてコードに加えているだけです。
全探索も数学Aで習う組み合わせ論ですし、二分探索も、結局は二進小数展開とやっていることは同じです。
余談になりますが、log10_2の近似値は二進小数展開で導出できますが、PCを使用して二分探索法で求めるのは誤差が小さくなって楽しいので、ぜひやってみてください。
3.アルゴリズムの勉強
アルゴ式。無料でこんなに質の良い教材があるのか...(Problems,Novistepsもそうだけど)。
アルゴリズムの中級編で行き詰まってから,「茶色になったら戻ってくるね...」と別れを告げました。これからお世話になります。
まとめ
私が考える茶色になるための近道は,
過去問精進 > 数学の基礎固め > アルゴリズムの勉強
です。
茶色になるにはC問題を解く必要がありますが,C問題でアルゴリズムを問う問題はあまり出ません。使ったことがあるアルゴリズムは全探索(bit全探索含む),累積和(imos法含む),二分探索,unionfind,ランレングス圧縮の5つぐらいです。
アルゴリズムを練習するよりかは,setやlistの使い方や計算量の考え方,数学的思考力を身につけた方がC問題は解けるようになると思います。
今灰色でのび悩んでいるという方は、クローゼットの奥底に突っ込んであるであろう数学I,A,II,B,Cの教科書を引っ張り出して、久しぶりにシグマさんやエーエヌさんと再会してみてはいかがでしょうか。
今後の展望
同年代で私よりレートの高い人が200人ぐらいいるので,努力を惜しむつもりはありません。情報オリンピックのセミファイナルステージ(12月)までに入緑したいです。
そのために,先述したアルゴ式,過去問演習,基礎数学の演習などをしていきます。後悔しないように選択していきます。
4,5ヶ月で入緑などの記事を読んで焦ることもありましたが、着実に力をつけていけばいつか問題が自分に味方してくれます。 絶対に。
最後に私の座右の銘である,東進ハイスクール講師の今井宏先生の言葉を引用して締めたいと思います。
「奇跡をおこす必要はない,その代わりどんどん進もう。」
では,また入緑記事でお会いしましょう！