いわゆる色変記事というやつです。
大学入学時からAtCoderを始めて約一年半、ABC322で無事に水色になることが出来ました!
自己紹介
- 文芸理系の大学2年生
- プログラミング歴3年とちょっと
- 競プロ歴は1年半
- 普段はWeb系とかをやってる
- 数弱(共テ4割)
- ツイッターもといXを始めたのでコチラも是非……@yu7400ki
水色になるまで
過去
今まで色変記事を書いてこなかったので、ここでザックリと書いておきます。
黒時代
コンテンストに参加する前の段階です。この頃はAtCoder Beginners Selectionなどで競プロの雰囲気を掴んだりしてました。
最終的にC問題くらいまでは解けるように準備してたと思います。
その甲斐もあり、初回のコンテストは4完で緑パフォを取ることが出来ました!
灰時代
この頃は初回のパフォーマンスを超えることが出来ず悩んでいた記憶があります。焦りからARCに参加してみるも、0完 -34レートを叩き出し筆者に深いトラウマを植え付けました。これ以降RatedでARCに参加することはありません。
とは言え黒時代の貯金で割とすぐに茶色に行くことが出来ました。
茶時代
パフォーマンスが1000を超える回が度々あったぽいです。このあたりあまり記憶が無いので書くことがありません……
緑時代
この時期が現状一番長く1年近くあります。そのうちの3ヶ月はサボってましたが。なんか学祭の準備を言い訳にサボってた記憶があります。なにやってるんでしょうねホントに……
灰や茶の時のように楽々レートが上がるということは無く、このままではマズいと思いAtCoder Problemsなどのサービスを触り始めました。
使った言語
- Python(PyPy)
- Rust
主にPythonを使って解いてます。練習だったりUnratedで参加する時にはRustでゆるりと解いてたりします。
RustはPythonに比べて早かったり、Pythonに無いデータ構造が使えたりします。そしてなにより書いていて気持ちが良いです。ですが、あまり早解き向きでは無いので実戦投入する機会はなかなかありません……
意識していたこと
コンテスト中はA~Cの早解きなんかを意識していました。A~Cが早く解ければ必然とD,Eに余裕が生まれます。
特にA,Bでは「難しく考えすぎない」を意識していました。A,Bは制約がゆるく賢いアルゴリズムを考える時間がロスにつながると考えています。脳を溶かしてひたすら指を動かしましょう。
早解きに関しては便利な関数・メソッドを知っているかが鍵となることもあります。競プロ以外でもコードを書くことは大切だと感じました。
勉強したデータ構造とアルゴリズム
データ構造
- スタック
- キュー
- 両端キュー
- 優先度付きキュー
- ハッシュセット
- ハッシュマップ
- グラフ
- UnionFind
アルゴリズム
- 全探索
- 二分探索
- ビット全探索
- 累積和
- いもす法
- 貪欲法
- 動的計画法
- BitDP
- メモ化再帰
- 幅優先探索
- 深さ優先探索
- トポロジカルソート
- ワーシャルフロイド
- フロイドの循環検出法
思い出せる範囲で書き出して見ました。使ったけど書かれてないものだったり、実戦では使ったことの無いものもあるかもしれません。(半分ネタで入れたフロイドの循環検出法は一回だけ使いました)
何を使って勉強したか
- けんちょんの競プロ精進記録
- 競プロ典型 90 問
- Educational DP Contest
- AtCoder Problems
- アルゴ式
- アルゴリズム的思考力が身につく! プログラミングコンテストAtCoder入門 - Amazon(途中まで)
- 問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本 - Amazon(途中まで)
よくお世話になったブログやウェブ、コンテスト、本をまとめてみました。本に関しては積読のような状態ですが……
どれくらい解いたか
AtCoder ProblemsのTrainingはEasyとMediumはすべて埋め終わり、Hardの70%は埋まっているという状況です。
その他の統計は以下のような感じです。
水色diffの問題は9個しかACしてないらしいです。よくこんなので水色になれましたね。先が思いやられます。
これから
- 水色diffの問題を埋める
- 使えるデータ構造とアルゴリズムを増やす
- 新しい言語を覚える
- インターンとか行きたい
水色になったとは言え現状は「水色の中でも最弱」といった状態です。ひとまずは過去の水色diffの問題を積極的に埋めていきたいです。
また、新しく使えるデータ構造やアルゴリズムを増やして行きたいです。特にAC Libraryに含まれているセグメント木なんかはマスターしたいですね。
これは半分趣味みたいなものですが、言語アップデートでzigが使えるようになったので、使えるようになってみたいです。zigはBunなどで使われており前々から気になっていました。
最後は競プロと関係ないんですが、インターンとか行ってみたいです。つよつよな人たちいっぱい経験積んでいて羨ましい……
おわりに
自分の中でなんとなく水色は一つの節目だと考えていたので、始めて色変記事というものを書いてみました。色変記事がどのような層に読まれているのか分かりませんが、少なくとも自分は「こんな人が競プロやってるのか~」と読むのが好きです。この記事がどこかのだれかの参考になっていれば幸いです。それでは皆さん、青色になった時またお会いしましょう👋
yu7400ki | AtCoder | X(Twitter)