AtCoderで入青しました！

先日行われたAtCoder Regular Contest 179にて、青色になることが出来ました！(実質)初参加からほぼ1年、ちょうど50回目のコンテストにて達成となりました。せっかくなのでちょっとだけ振り返ってみようと思います。

レート遷移
グラフ均等化拡張機能あり

かなり前に1度だけお試し参加したアカウントを引っ張り出して使っているせいでグラフが大変なことになっています。

自己紹介

  • 名前：yukimy
  • AtCoder歴：実質2023/6～(入青時点でほぼ1年)
  • プログラミング経験：趣味でほんのちょっと触ったことがある程度
  • 数学力：高校数学レベル(IAまではそこそこ、IIB以降はかなり怪しい)
  • 使用言語：Ruby・Crystal
  • 環境：Windows・VSCode
Problems(1)
Problems(2)
Problems(3)

言語選択の理由

4年前に高校の友人の影響でお試し参加した際はC++を使ったのですが、初めてプログラミングに触れるタイミングでC++の難しさと競プロの難しさを同時に味わってしまい、すぐに挫折してしまいました。その後しばらくしてRuby on Railsに触れる機会があり、シンプルな記法でとっつきやすかったので改めてまずはRubyで競プロをやろうという気持ちになりました。その後プログラミングに慣れてきて速い言語を試してみようと調べた際にCrystalの存在を知り、今はRubyとCrystalを併用しています。言語毎の難易度は簡単に比較できるものではありませんが、いくつか触れてみて自分に合ったものが見つけられるといいのかなと思います。

入青するまでにやったこと

今までやってきた精進等についてザックリと振り返っていきます。

ABCの過去問

やっぱりこれがメインです。個人的に同じような難易度を解き続けるのがあまり好きではないので、色埋めではなくバーチャル参加を活用して新しいものから遡る形式でやっています。取り組み方としては、

  • 可能であれば1日1回分。
  • その時解けそうなdiffの上限を決めて、そこまで解く。解説ACした問題はメモしておく。
  • 初見のアルゴリズムに出会ったら勉強して、必要に応じて自前ライブラリを整備する。
  • レベルが上がって解ける範囲が広がったら、飛ばしていた問題に取り組む。
  • 解説ACの問題は時間を空けて再度挑戦し、あっさり解ければメモを消す。引っかかったら残す。

といった感じです。現時点で約200回分の青以下をほぼ埋め終わっています。

典型90

こちらも鉄板ですが、とてもとても有効な教材です。茶色の頃に☆5以下を埋めて、水色になってから☆5以下の2周目を含めて全て解きました。……嘘です。90問目だけ難しすぎて埋められていません。茶色の時に☆5はちょっと背伸びし過ぎな気もしますが、苦労した分結構成長できたと思います。早いうちから段階的に活用するとかなり成長の助けになってくれるので、オススメです！

整備した自前ライブラリ

AtCoderには「AtCoder Library」というとても便利なライブラリが存在するのですが、私は仕組みの勉強もかねて可能な限り自作をしています。自作といいつつ参考文献の移植のような形になってしまっているものも多いですが……。ACLを活用した方が動作や速度は安定すると思うのですが、自由度が高いのはメリットです。以下、自作してよく使っているライブラリを列挙していきます。青色になるために必要ないレベルのものもあります。

  • 抽象化セグメントツリー
  • 抽象化遅延評価セグメントツリー
  • フェニックツリー
  • 優先度付きキュー
  • next_permutation(Crystal標準のpermutationsだとメモリを余計に使うため)
  • 座標圧縮
  • ローリングハッシュ
  • 繰り返し2乗法(pow)
  • FFT(NTT)を利用した畳み込み
  • bitset
  • 拡張ユークリッドの互除法
  • 中国剰余定理
  • 行列積、行列累乗
  • 階乗、階乗の逆元を前計算した組み合わせ計算(その場で実装しても簡単だが、よく使うので時短のため)
  • 素数生成(エラトステネスの篩)、素因数分解、約数列挙
  • UnionFind
  • Dinic法
  • Grid(移動判定の簡易化、1次元配列管理で省メモリ化)
  • 木上の二点間の距離(ダブリングでLCA探索)
  • 強連結成分分解
  • 抽象化全方位木DP

ダイクストラ法、プリム法、クラスカル法なども用意していますが、これらは大幅な改変が必要な事がほとんどで、コピペのメリットはあまりないかな……と思っています。
C++のstd::multisetの代替として平衡二分探索木を使うのですが、実装難易度がかなり高いため現在はこれだけACLに頼らせてもらっています。
また、DFS・BFSは使用頻度が非常に高いため骨組みをスニペットに登録しています。

その他

ARCの過去問については、やらなきゃいけないな～と思いつつあまり解けていません。現状は直近20回の前半数問をちょっと触った程度で、これから本格的にやっていこうと思っています。
習得したアルゴリズムはリストアップすると多すぎるので省略しますが、青diffで要求されるレベルのものは概ね使いこなせてるかな?という感覚です。レート1400くらいまではずっとDPが苦手だったのですが、これは類題をこなすにつれて色相当には解けるようになりました(多分)。DPは特に反復練習がものを言うジャンルだなと感じました。

終わりに

振り返ると特に変わったことはなく、薄味になってしまった気もしますが、とにかく「ABCで勝つにはABCをたくさん解く」が重要だと思います。
ここから黄色を目指すのはさらなる茨の道だと思いますが、高度な問題にも少しずつ手を出しながら地道にレベルアップしていきたいですね！