初めてのQitta記事になる. 簡単な自己紹介をする.
* 名前:Kazun
* 大学4年生 大学では数学を勉強してる.
今回はコロナ渦の影響により以前から存在を知っていた競技プログラミングにおいて, AtCoder で青色になったので, 青色になるまでの簡単な経歴と習得した事柄をまとめてみた.
競技プログラミングの歴史
競技プログラミングとの出会い
競技プログラミングという存在を知ったのは大学1年生で, 大学の掲示板に競技プログラミングへの案内があった(サークルとは別物). 当時は「こんなものがあるんだ程度であった.」
意識していなかった準備
大学のアルゴリズムの講義で計算量におけるオーダー記法の定義から, 動的計画法, グラフの最短距離, 部分和問題などといった多くのことを学んだ. 当時は興味からとった講義だが, 今見てみるとこれによって全くの初心者から半年で青色になった大きな要因の一つではないかと思う.
競技プログラミングの世界へ
競技プログラミングの世界に踏み入ることになったのは, 2020年5月17日である. この日に開催された AtCoder Beginner Contest 168 の C問題 :(Colon) において, 余弦定理がTwitterのトレンド入りし, それを見て, 問題に興味を持ち, 競技プログラミングの世界に入ることになった.
いざ,初参戦
競技プログラミングの世界へ入ることを決めた翌週から早速コンテストに参戦することになった. しかし, ABCとAGCの違いすらわかっていなかった当時のデビューコンテストは AtCoder Grand Contest 044 であり, A問題 から(変更後の)Diff 1828 という超難問回である. その結果当然成すすべなく, 0完 Performance 540 でRating 28 という残念な結果になってしまった.1
いざ,初参戦2
あまりに残念すぎるデビュー戦の次もやや適正ではない AtCoder Regular Contest 級の NOMURA プログラミングコンテスト 2020 であった. この回は奇跡的にC問題 を正解することができ, Performance 1341 で Rating 299 にジャンプアップした. (この後の2回のコンテストでRatingは299→729→1087と変化した.)
青色への挑戦
水色を達成し, 次は青色へ挑戦することにした. とりあえずAtCoder ProblemsのRecommendationのうち, Easyを中心に解いていった. というのも, Diff $X$ であることの定義がRating $X$ の人が半分解けるという意味なので, 半々で解けるか解けないかの問題よりも, もっと確実に取らなくてはいけない問題を確実にした方がいいのではないかという考えがあったためである. 実際, AtCoder Problemsによる推測で80%を超えるような問題でもわからないということがあり,2 もし本番だとPerformanceが悲しいことになっていたので, この考え方にしてよかったのではないかと思う.
青色の達成
2020年10月から2年ぶりに復活したAtCoder Regular Contestが自分にあっているらしく, 開幕5連続でRatingが上昇した結果, 青色リーチに手を付ける事ができた. そんな中迎えた AtCoder Beginner Contest 184でF問題 が非常に簡単な回であったこともあり, 悲願の初パーフェクトを達成し, Performance 1956 (個人的ベスト2)でRating 1617となり,青色になることができた.
習得済みの事柄
以下で自分がある程度は習得したと思われる事柄を列挙する. ただし, 自分の興味によって習得したものもあるので, 必ずしもここに書かれているものが青色になるために必要なことではない. また, ★があるものはライブラリー化した.
アルゴリズム, テクニック
- 全探索 ★
- 素数判定 ★
- 素因数分解 ($O(\sqrt{N})$ バージョン) ★
- 剰余環 (加減乗除, 累乗, 平方根, 原始根)★
- 行列 ★
- グラフ(グラフの有向性,辺の重みの有無それぞれ計4通り) ★
- 二部探索 ★
- Imos法 ★, 累積和
- Doubling
- 尺取法
- Flow ★, 最小費用流 ★
- Grundy数
- 畳み込み ★
- 2-SAT ★
- 形式的ベキ級数
- 動的計画法
データ構造
- Union Find ★
- (Lazy) Segment Tree ★
- Binary Indexed Tree ★
解いた問題数
- AtCoder:661問
- yukicoder:310問
- AOI:数問(Verify専用)
- Library Checker:(Verify専用)
これから
せっかく青色になったのだから, 次の目標としては AtCode Beginner Contest 卒業となる黄色 (Rating 2000)である. これまで以上に厳しい戦いになると思うが, マイペースに着実に Rate を稼いでいきたいと思う.
-
実際, この難しさの影響か, 次のAtCoder Grand Contest 045 から1200-Ratedになった(この回のA問題が更に難しかったのだが...). ↩
-
100%でないのだから当たり前だと言われてしまったらそれまでだが... ↩