#AtCoder水色になりました
こんにちは。Pkodamaです。今回はABC153にてAtCoderのレートが1200以上になり水色コーダーになったので他の水色を目指している方にも参考になればと思い記事を書くことにしました。ターゲットは緑→水色で苦戦している人向けですが、多くのレート帯の方の参考になるように一応心がけて記事を書きました。
#1.水色コーダーになった感想
AtCoder始めた頃の目標で水色になるというのがあり、無事達成できたのでやっぱり嬉しいです。
上の写真は緑になって以降のコンテストの成績表です。基本的にRatedのコンテストには参加するようにしています。ただ1月はJMO予選やRCJ九州大会など時間がうまく取れずあんまり参加できていませんでした。
前回前々回と順位的には青色パフォーマンスでしたが、残念ながらUnratedになり2回連続で水色入りを逃すということをしていました。ただ、この2回で自分には水色の実力があるなと確信し、このままコンテストで続けたら水色なるやろという気持ちでした。そして今回のABCに出てみると、また大成功してまた青色パフォを叩き出し水色になることができました。
#2.灰色→茶色
自分は始めた時点でプログラミングの経験があったのですが、最初の方は思うようにレートが伸びませんでした。ただ今思えば競技プログラミングというものに慣れていなかったのかなと思います。コンテストに数回でて慣れてきたらそれなりにレートも伸びてきました。
ここのレート帯で伸び悩んでいる方で、プログラミングにまだ慣れていないのならAtCoder Programming Guide for beginners (APG4b)がオススメです。
プログラミングに慣れてきたならdrkenさんのAtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～がいいと思います。
#3.茶色→緑色
私は数学が結構得意でプログラミングの経験があったというのもありここは時間はかかっているもののそんなに苦労はしていなかった気がします。
上の表を見てもらったらわかりますが、水パフォを3回とっており、それらは全てAGC,ARCです。初心者にARC・AGCは苦しいと言われますが、僕は寧ろ茶色の方にとっては美味しいと思います。ここらへんのコンテストでは差がつくのは結局１、２問ですのでまぐれでも早く解ければ一気にレートが上がります。逆に緑、水色の人にとってはAGC,ARCはABCに比べかなり厳しい気がします。
だいたいABCの300点問題(最近は400も(?))を安定して通せるように慣れば緑になれるのかなという印象です。
ここらへんのレート帯で伸び悩んでいる方はABC300点問題を埋めてみるといいかもしれません。少し難しいですが、AtCoder 版！蟻本 (初級編)をやってみるといいのかもしれません。
#4.緑色→水色
私はここが結構苦労しました。実は確か緑色になった当初はBFS/DFSなどの基本的なことも知らなかった気がするするので同レート帯の方と比べて圧倒的な知識不足でした。体感としては最近のABC400が安定して解けて、ABC500が解けるかなくらいになると水色になれる印象です。水色になるまでにやったことはメインディッシュなので次の章で書いてきます。
#5.水色になるまでにやったこと
いわゆる一般的に水色に必要な基本的アルゴリズム、データ構造は抑えてるつもりです。drkenさんのAtCoder 版！蟻本 (初級編)はオススメです。埋めたら結構実力つくと思います。私はAtCoder 版！蟻本 (中級編)のフロー手前までやってました。
また、Chokudai SpeedRunは捻りのないTHE典型問題を集めている感じなので教育的でお勧めです。Chokudai SpeedRun 001、Chokudai SpeedRun 002、
###STLの機能
まずは基本的なSTLの機能を使えるようになりました。この辺はABC300くらいで問われる印象です。
・set・multiset
setは重複なしの集合を管理します。要素の挿入、探索がO(logN)で出来て結構便利でよく使います。multisetは存在はsetの重複を許す版です。
・map
連想配列というやつです。辞書みたいなやつで、うまく言えませんがわかんなかったらこの記事を参考にしてみたらいいと思ういます。
・vector
便利な配列です。めちゃくちゃよく使います。
・stack/queue
BFS/DFSをするときによく使います。逆にそれ以外では今の所あまり使ってないかな？
・priority_queue
優先度付きキューですというやつ。任意の要素を取得しようとするとO(N)かかりますが、最も値の大きな要素の取得と値の挿入がO(logN)で出来ます。ABC141-D_Powerful Discount Ticketsがコンテスト中に優先度付きキューを知らずに解けなかったのをよく覚えています。
List、dequeなんかは知ってはいますが使ったことはないです。
###・全探索(bit全列挙/再帰関数)
基本的なこと(迷路探索)などは出来ますが、私は結構苦手です。再帰関数は最初はよくわかりませんでしたが、気がついたらできるようになってました。漸化式のイメージです。全探索はやるだけと言えばやるだけなのでABC400点にはならずABC300点になり、全体としても通常よりは解ける人が少なくなる印象です。
例題:ABC151D_Maze Master、ABC119C_ Synthetic Kadomatsu、ABC128C_Switches
###・二分探索
lower_bound,upper_boundなんかはある程度使えると思います。
値の探索だけではなく条件を満たすような最小値を探す決めうち二分探索も必要でした。
例題:ABC149E_Handshake、ARC037C_億マス計算、AGC041B_Voting Judges
###・UnionFind木
集合を管理するデータ構造です。
例題:ABC062A_Grouping
またこういう問題(パ研杯2019E_大きなクリスマスプレゼント)もUnionFindで解けるらしく衝撃を受けました(結構難しかったです)
###・典型DP
JOIはDP大好きなのである程度はできるようになりました。DPコンは勉強になってオススメです。私はIまで埋めてました。
例題:15thJOI本戦A_オレンジの出荷、ABC153E_Crested Ibis vs Monster
###・Dijkstra/Warshall-Floyd/Bellman-Ford
基本的なグラフのアルゴリズムです。一見グラフの問題っぽくないのをグラフ化してDijkstraに乗せて解くみたいなのをよく見かけますが私は出来ないです。
例題:7thJOI予選F_船旅、ABC061D_ScoreAttack
###・imos法/累積和
範囲に対して操作をするならimos法が怪しかったりします。(雑)
・ABC125C_GCD on Blackboard、JOI2018予選E_イルミネーション
###・数学
私は高校数学を終わらせているので水色になるのには苦労はしませんでしたが中学生とかだとキツイ気がしなくもないです。大学数学は線形代数すらわかりませんがなんとかはなりました。
水色に必要な知識はGCD、LCM、約数列挙、素因数分解、互除法による一次不定方程式の解の導出、エラトステネスの篩くらいな気がします。
例題:ABC144D_Water Bottle、三井住友信託銀行プログラミングコンテスト2019F_IntervalRunning、diverta2019B_DivRem Number、ABC024D_動的計画法
###・数え上げ
私は謎に得意です。modint(mod上でのint)は便利なので使うとをお勧めします。よくある話ですが小さいケースを手元の紙でやってみるのはかなり効果的なのでお勧めです。
例題:ARC077D_11、ABC150E_Change a Little Bit
###・構築
無理です。どうするんですか？私が教えて欲しいです。ただ400くらいなら流石に解ける気がします。
例題:ABC131E_Friendships
###その他
蟻本はフロー手前まではざっと読みました(やったとは言ってない)。結構いろいろ載っててお勧めです。これを読んで知識をつけてdrkenさんの蟻本記事をやると効率的に実力がつく気がします。
また、SegmentTree、BITなどの水色では一般に要求されない高度なデータ構造、アルゴリズムにも触れました。もちろん使いこなせはしませんが、たとえ実装はできなくてもそのようなことが実現できると知っているだけでも結構違うと思います。例えば今回のABC153F_Silver Fox vs Monsterではコンテスト中に初めて遅延伝搬評価付きセグメント木を使いACしました。私は遅延セグ木を実装したことなどありませんでしたが、どういうことが実現できるかは知っていたためこの発想を得ることができ、他の方のライブラリを拝借してACできました。高度なこととは言えまぁどうせいつかはやるので早く知っておいて損はないと思います。
#6.精進について
これはAtCoderScoresでの点数ごとの解いた問題の確認した画像です。900点より高い点数の問題は1問解いてないのです。こうみると少ないですが、考察だけした問題もちょくちょくあります。
水色になるのにABC200点以下はあんまり解いても意味がない気がします。私は主にAtCoderの公式のバチャ機能で過去のABCのバチャをしたり、適当な400-600くらいの問題を解いたり、AtCoder Virtual Contestでバチャをやったりしてました。バチャはコンテスト本番と同じような緊張感でできるのでお勧めです。
逆に、私はどうしても難易度の先入観を持って問題を解くのが苦手なのでdifficultyを参考に問題を解いていくのはあんまりオススメしないです。
#7.その他
・Twitterは活用しよう！
どうしてもわかんないことがあったらTwitterにコードや質問を投げましょう！強い人が答えてくれたりします。別に質問して減るものはないので損はないのです。ただし、自力で何も考えず質問ばかりして自己解決できる能力がつかなくなるということは避けましょう。
・AtCoder解説放送はいいよ！
AtCoder解説放送は結構いいと思います。純粋に解説を聞くのが理解を深めるだけでなく、りんごさんというRedCoderの方が実際にコーディングしてる様子を見てるのは多くのものを得られます。一般にレートが高い方は綺麗な実装をします。こんな実装あったのか！！みたいなことに気付けるかもしれません。私はvectorを確か解説放送で知りました。
・実力がつけばレートは勝手についてくる！
青色までだとほぼ毎週のようにRatedコンテストがあります。私はコンテストは結構得意不得意の運要素は強いと思っていて、1,2回振るわないのは仕方のないことなのかなと思います。大切なのは悪くても良くても極端に一喜一憂しないことだと思います。ただ黄色以上になるとRatedが少なくて辛くなるかも...(その時はCodeForcesに逃げます)。
・海外コンテストについて
私は一応CodeForcesのアカウントを持っていて、英語が読めないやらAtCoderと仕様が色々違うやら開催時間がキツイやらでサボりがちですが数回コンテストには出たことがあります。現状だと私はやってないことでデメリットは感じませんでした。
#8.最後に
今回、こうして水色になれたのも多くの方の記事、ブログを参考にしてきました。なので少しでも還元しようとこの記事を書きました。参考になれば幸いです。私はこれからもまだまだ体力はあるので青色コーダーを目指していきたいです。
追記
2019/1/27 数学のところに例題「ABC024D_動的計画法」を追加。