入水記事 #Python

２０代医師のDr_pilotです。２０２２年７月１７日実施のABC260で入水しました、やったね！

入茶、入緑までの過程はこちらの記事をご覧ください。

プログラミングというものを1から勉強し始め、2021年9月時点では「リストの先頭は１ではなくて０からスタートなのかー」「printという関数で出力するんだね」レベルでしたが、そこから１０ヶ月で水色まで来ることが出来ました。今回は、緑→水にレベルアップするために必要だと思うことをメインに記事にさせていただきます。

入緑した時と今の時点で明らかに違うスキル

それぞれのアルゴリズムに対する理解が更に深まった
正直に言って、緑に入った時と比べて新たに使いこなせるようになったアルゴリズムは増えていません。ただ一つ一つのアルゴリズムをより深く、さらには応用を利かせて使いこなせるようになった感はあります。
動的計画法に対する苦手意識がかなり薄れた
最近のABCはC問題あたりで普通にDPが登場します(ABC240C、ABC242C、ABC245C、ABC248C)。「DはDPのD」と言われていた時代は私はまだプログラミングをやってないので知りませんが、どうやら今はもう「CはDPのC(?)」になってしまったようです。
動的計画法の勉強ですが、すぬけさんなどがよくEDPCを薦めてらっしゃいますが、はっきり言って激ムズです。アルゴ式の【基礎編】動的計画法 (DP)と【特集】典型的な動的計画法のパターンを整理～ナップサック DP 編～をオススメします。導入が神がかり的わかりやすさで、動的計画法に対するアレルギーが無くなりました。
計算量の感覚が体に染み付いている
chokudaiさんが各色に対する評価をまとめた有名な記事にも書いてある通り、水色あたりになると頭の中で方針を思いついた時にはすでに「これはオーダー〇〇のアルゴリズムだな」と体感ですぐ分かるようになります。そのおかげで、頑張って実装した挙げ句TLEなどという悲劇はほぼ起こらなくなったと思います。

使いこなせるアルゴリズム

自信あり、本番でも書けた
全探索、bit全探索、順列全探索、二分探索、UnionFind、BFS、DFS、ダイクストラ法、累積和、imos法、エラトステネスの篩、約数列挙、素数判定、クラスカル法、動的計画法(緑diffまでのやつ)、トポロジカルソート

グラフ問題がかなり好きで、それに関連する基本的なアルゴリズムはほぼ理解出来ている。グラフ問題に帰着できる問題はかなり多いと思うので、グラフ得意に出来ると絶対強い。
約数だとか素数関連のアルゴリズムはすべてネットで拾ってきたライブラリ使ってるけど、その中で何が起きているのかまで理解することは絶対必要。

まだ不安、解けたり解けなかったり
動的計画法(水diff以上のレベル)、ワーシャルフロイド法、強連結成分分解

苦手意識なくしたとはいえやっぱりDPは難しい

齧った程度、理解できてない、ちんぷんかんぷん
最小費用流、最大フロー、SegmentTree、BIT、bitDP(いつまでたってもTraveling Salesman Problemが理解できない)、他にもたくさん有るけど多分挙げたらキリがない

何が起きてるのかそもそも分からん。でも青目指すならここらへんも避けて通れないですよね。

ざっとこんな感じだと思います。これだけ見ると緑コーダーでも十分理解できるアルゴリズムしか習得していないことがわかると思います。あとはそれを深く理解して使いこなせるようになるだけの問題だと思います。要は数こなせってことですね。

その他、役に立ったこと

tatyamさんは神
tatyamさんの作られたSortedSetはPython使いに光をもたらしました(詳しくはこちらの記事を参照)。私はこのライブラリには殊の外思い入れがあって、なぜなら「この問題(ABC241D)が解けたら入緑だ!」という局面でこのSoetedMultisetに助けられましたし、「この問題(ABC260D)が解けたら入水だ！！」という局面においても、やっぱり助けてくれたのはSortedSetでした。もしtatyamさんがYoutuberとかしてたら３万円くらい投げ銭してたと思います。それくらい汎用性が高く、あらゆる局面で突破口を開いてくれたものでした。本当にありがとうございます。
yukicoder
AtCoderより難しい問題が多いと思います。yukicoderで★1.5(いちおう茶diffってことらしい)ってなってても、かなり時間を書けて考察しても全然わからなかったりすることが多いです。正直AtCoderとはかなり趣が違う傾向の問題が多いです。オススメの勉強方法は、問題一覧から「解いたユーザーが多い順」に並べて問題を解くことです。そうすれば変に癖のある問題ではなくオーソドックスな問題ばかり解けるので勉強になります。あとは統計のところからアルゴリズムごとにタグ付けされているので、自分の苦手なアルゴリズムをここで鍛えるのがいいと思います。
Qiita
自分が悩んだり躓いたりするようなところは、たいてい既に自分より頭の良い誰かが記事にしてくれています。

今後の目標

「青を目指す」などと大それたことは言えません。とは言うものの、自分が緑になった時には「水色を目指すなんて大それたことは言えない。緑から落ちないように気をつけよう」と思っていたら５ヶ月後には入水していたので、ぼんやりとだけ青色を意識しつつ精進します。
また、入緑記事にも書いた通り、特に何かをしたくてプログラミングを始めたわけではないので(単純に数学の問題を解いているのが好きなだけだった)、このスキルをなにかに活かそうとかはあまり考えていません。しかし水色コーダーのプログラミングスキルは結構高いようなので、せっかくだから何か普段の仕事に活かせたらなと考えています。何かいいアドバイスあればお願いします。