shu8Creamのブログ

競プロブログ。

【AtCoder】入緑しました!!!

こんにちは、shu8Creamです。

先日開催されたARC117にて緑コーダーになりました!!

どんな精進をしてここまで来たのかをできるだけ丁寧に書いていこうと思うので参考になれば幸いです。 茶色になった時にも記事を書いているのでそちらが気になる方は↓から

AtCoderで茶色になった - shu8Creamのブログ

目次

自己紹介

twitter.com

緑の位置確認

僕のAtCoderでの順位は13726位です。現在のアクティブユーザの最下位は76402位なので超単純計算で上位約18%。 アクティブユーザかつコンテスト参加回数10回以上の場合、最下位は64668位で計算すると上位約21%です。 緑よりも上になると更にグッと人数が減っていく感じですね。数字だけ見ると結構上の方っぽい感じがしますね。(Twitter上だと強い人しか見ないんだけどな〜)ちゃんとした数字を取ってきてないのであれですけど、数年前のchokudaiさんの記事だと緑は上位30%って見かけたのでここら辺も変わってきているみたいですね。ちゃんとした割合は誰かが出しているはずなのでそこを見てください。

勉強したこと

競プロの取り組み方

まずは、AtCoder Problemsの記録です。色変直後に魚拓取りました。

言語は基本C++多倍長整数が使いたくなった時にPython使ったりします。

茶色になった時は、AC数が287だったので500問以上増えてますね〜。こんなに解いていたのは自分でも驚きです。 特に緑diffの問題はガッツリ解きました。最近のコンテスト内ACも茶diff上位〜緑diffのAC率が上がってきています。 (なぜか茶diff下位がここ最近通せてません...)

僕の普段の精進の仕方としては、自分のレートよりちょい上ぐらいのをメインに解こうと頑張っていて考察時間かかって辛いよーってなったらちょっと簡単な問題を解いて僕天才!ってなるのを繰り返してます。あと、昔のABCだと平気で水色とか稀に青でも普通に通せたりするので僕天才!ってなりたい方にはおすすめです。ただし、むずくて心が折られることもあります笑

茶埋めとかをする人も多いみたいですけど、AGCとかの茶色はめっちゃむずいと思っていて全然解けないことが多いのであまり手をつけていません。まずは基本のABC、余裕があるならARCを、という優先順位で進めるのが良いと思います。ただ強くなるために、今後の僕の課題だとも思ってます。

Qiitaの精選100問は半分以上やった気がします。僕が特にやってよかったなーと思ったのは、実装が重い系の問題でBFS・DFSあたりは実装が大変でしたが、やってよかったし解いた後の達成感があるのでおすすめです。プログラミングをやってる感がすごくあります。数学嫌いーとかプログラミングしてる感が欲しいとかならやるべきです!!残りの問題もやらなきゃいけないとは思っていますが、DP...。がんばります。

アルゴリズム

次にアルゴリズムについてです。勉強したものと実際にコンテストで使ったかどうかでまとめてみました。 僕個人的に今のレートから2色以上、上のパフォーマンスを出さなきゃその先の伸びが苦しくなると思っていたので、 難しいものも勉強しています。実際初めて水パフォが出た次の次の回で色変しました。緑になるだけだったら重要度が低いと思います。

アルゴリズム 重要度 使った? 僕の気持ち
約数列挙 ライブラリで持ってる便利
素因数分解 × 知らないと無理系のやつ勉強あるのみ
累積和 なんか知らんけど結構使う気がする
いもす法 単純ないもす法は茶diffだった
modpow スニペットですぐ呼び出せるようにしてる
mod int (mint) ACLの使い方は知っときましょう
二項係数 nCkです、mod取るやつとかシンプルなやつとか何種類か書けると安心
拡張ユークリッドの互除法 数学得意なら勉強すべき、苦手なら後回しでOK
bit全探索 実装がなぜそうなるかまで理解しよう
順列全探索 あんまこれ使う問題は出てない気がする
二分探索 応用範囲広すぎてこれもにぶたんなのかー ってなる
しゃくとり法 二分探索でもできたり、最近使ってないから忘れてる
Union-Find マージテクは緑までなら必須じゃないかも
DFS 緑までの実装問題は大部分がこれな気がする
BFS 木とグリッドどちらもできるように(DFSも同じ)
ダイクストラ ライブラリで持ってる
ワーシャルフロイド × これ使う問題は少ないけど知らないと終わる
DP × DP苦手すぎて何も言えることがない
桁DP × これは青ぐらいのレベル
TSP(巡回セールスマン問題) × bitDPです。これもやるだけなら緑レベルです
半分全列挙 × やるだけなら水色みたい
行列基本演算 そんな使わないけどライブラリ作りました
座標圧縮 なんかと組み合わせて座圧する問題多い
BIT(Fenwick tree) × 転倒数と組み合わせて覚える
セグメント木 × ACL使うだけなら緑でも必須っぽい
Zアルゴリズム × なんか勉強したくて勉強したけど使う機会はしばらくなさそう
LCA × これも勉強したかっただけ
ダブリング × 理解はしてるけど実装ができる気がしない
LIS × DP苦手ーーーー

アルゴリズムというか有名問題も混ざってますが気にせずどうぞ。やるだけなら緑レベルという問題多すぎます。 全部手をつけるには時間がかかるので優先度を決めて取り組むと良いと思います。 ACLが登場してからデータ構造を使うだけの問題のdiffが激下りしてるので自前実装はできなくてもデータ構造の概要は知っとくと得します。 (UnionFind, セグ木 etc...) あとACLの中だとmintは使えるようにするのは必須です。逆元周りの話を理解するのは後回しでもいいかもしれませんが、何が行われているかぐらいは知っておくと良いと思います。 ここにあげたものの中で重要度の低いものは知らなくていいというわけではなくて、こういうものがあるんだというのを押さえておくと 出題された時にコンテスト中に調べて解くことができるかもしれません。とりあえず知っておくというのも意外と重要です。 実際いもす法はコンテスト中に勉強してACしました。

読んだ本

いわゆるけんちょん本です。初心者には超おすすめの本です。まだ読みきれていない部分もあるのでこれから履修します。

群論の話などが載っています。勉強の入りとして読むのにとてもいいと思います。ただ好きだからここに書きました。

これは全然読みきれてないです。ちゃんと読み込むというよりも参照する方が多いのでそれを見るためとかわからないことがあれば、辞書を引く感じで利用しています。今後もお世話になります。これにプラスして蟻本に沿った問題を集めているQiitaの記事の問題も解くとよりいいと思います。

伸び悩んだ時に

コンテストに30回以上も参加していると当然レートが下がったり、今まで解けたはずの解けなきゃいけない問題が解けないこともあります。そんな時心が折れてしまったり、辛い気持ちになることもあると思います。色々な人が言っていることですが、一回のコンテストで一喜一憂しすぎないことです。あとはめっちゃ伸びている近いレートの人のことを気にしすぎない。人に興味ないでしょってよく言われる僕が書いても全く説得力がないんですけど、楽しく続ける上で重要です。あと、毎回コンテストに出ることが義務感になっているのならやめたほうがいいです。忙しくて精進できてない時もあるだろうし、体調が良くない時もフラれてメンタルがボロボロの時もあるでしょう。そんな時は潔く参加をやめる。あと、友達との予定を優先させるのも大事ですよー。

あとは、自分の間違えやすい問題(苦手分野)、ミスしやすい忘れがちな事項はどこかにメモっておいてコンテスト中詰まったら見返せるようにしておく、コンテスト後には解けた問題も復習して違う実装方法があれば調べて解いてみる。コンテスト中に考えて解けなかった問題はしっかりupsolveする。(これは解けなかった問題の難易度にもよります)などなど、僕がやっていた方法です。

まとめ

なんか周りにはめっちゃ頑張っている人が多いですが、僕はマイペースに楽しんで続けていきたいと思っています。途中で別のところに興味がいくことも多いですが、フラフラしながら続ける予定です。精進の様子をみて頑張ってるだろと思う方もいるかもしれませんが、好きで気づいたらやってるだけです。もっと精進しろ!と思う方はお手柔らかにお願いします。今までの期間ほとんど卒論書きながらやってたので、これからはもっと競プロを楽しんでマイペースにやっていきます。

とりあえず今年の年始に設定した目標だった緑コーダーは(2週間遅れではありますが)達成できました。今後は、今年中に水コーダーを目標に頑張っていきます。あと、CodeForcesも本格的に始めたいですね。