AtCoderで水色になりました

AtCoderを始めてから2年弱が経ちましたが、ようやく水色になれました。緑色になってからは8ヶ月くらいかかってしまいましたが、そこから取り組んだことなどを話していこうと思います。

経歴など？

京都大学理学部数理科学系4回生で、卒業した後は業プロerとして働きます。（3月で卒業なんですが、なんとか目標の卒業までに水色を達成できました。）

学んだアルゴリズム

A: アルゴリズムを証明ありで使え、ある程度の応用ができる。
B: アルゴリズムを知っているが、応用は正しくこなすことができない。
C: アルゴリズムの名前は知っている。
D: 存在を知らなかった。

緑の欄がAであるとは、緑の間にその状態へと持っていったことを示します。

• 探索系

アルゴリズム名	茶	緑
全探索	A	A
bit全探索	B	A
順列全探索	D	A
半分全列挙	C	C
DFS	B	A
BFS	A	A
再帰による探索	D	A
二分探索	B	A
三分探索	D	C
尺取り法	B	A

• グラフ系

アルゴリズム名	茶	緑
Dijkstra法	B	A
Floyd-Warshall法	B	A
Bellman-Ford法	C	B
最長パスを求める	D	A
サイクル判定	D	A
強連結成分分解	D	C
DAG上のトポロジカルソート	C	A
DAG上の二点間の最長距離	D	B
プリム法	D	C
クラスカル法	D	C
木の直径	B	A
最短共通祖先問題	D	A
フロー	D	C

• 文字列アルゴリズム

アルゴリズム名	茶	緑
ランレングス分解	C	A
z-algorithm	D	C
ローリングハッシュ	D	C
suffix-array	D	C

• 数学

アルゴリズム名	茶	緑
modint	C	A
ユークリッドの互除法	A	A
素数判定	A	A
約数列挙	A	A
素因数分解	B	A
エラトステネスの篩	C	A
その他の篩	D	C
高速ゼータ変換	D	C
高速フーリエ変換	D	B
高速メビウス変換	D	C
Mo's algorithm	D	C
Grundy数	C	B

• データ構造

アルゴリズム名	茶	緑
union-find木	B	A
BIT	C	B
segment木	C	A
lazy-segment木	D	B
静的wavelet-matrix	D	B
ポテンシャル付きunion-find木	D	B
slope-trick	D	B

• DP

アルゴリズム名	茶	緑
普通のDP	A	A
bitDP	B	A
木DP	C	B
区間DP	C	A
2乗の木DP	D	C
全方位木DP	D	C
桁DP	C	B

ばーっと書きました。知識が徐々についてきているのがわかりますね。最近は、アルゴリズムの難易度に対するdiffが低くなってきているので、どんどんアップデートしないといけないなと思っています。

意識してたこと

一応数学科出身で、数式にした方が理解しやすいので、求めたいものや最大化したいものを数式で書き表すようにしていました。DPの際も漸化式を書いたりしていたので、漸化式を解くことで解けるような問題（ARC174C）にはある程度強かったかなと思います。

また、問題を解いた後は自分でまとめを作っていました。こんな感じ。
https://scrapbox.io/atcoder-BlueS/

個人的には最も大きな変化だったんですが、PythonからRustへ転向しました。（このせいで緑の期間が長かったのかも？）最初は戸惑ってばっかでしたが、現在はPythonと同じくらいスムーズにコード書けるし、計算量が少し大きくても通るのでとても助かっています。

逆に、練習量などに関しては特段気にしていませんでした。やりたい時にやってるって感じです。

コンテストごとに解くのが、好きです。なんか、似たような難易度の問題を解いていると疲れちゃいます。

最後に

twitter(新X)で、いろんな人に教えてもらったりしました。みんな優しいし、強いし、すごい。ありがとうございました。
とりあえずの目標として、2024年の間に青色なりたいなって思っています。みんな仲良くしてね。

趣味

なんか趣味について書いておきます。「なきごと」っていうバンドが好きで、ライブも何回かいってます。あんまりメジャーではないんですけど、ぜひ聴いてみてください。