AtCoder青になりました

初めまして。ゆかりです。たくさんのいいねとリプライありがとうございます。ちょうどいい機会なので自己紹介と振り返りをしようと思います。有益なことはおそらく書いてありません。

自己紹介

・大学一年生です。理系ですがどういう学部に行くかはまだ決めてないです。早くお酒が飲めるようになりたいですね。

・プログラミングの経験は高校の授業でfizzbuzz問題をやらされただけで全くと言っていいほどないです。AtCoderは周囲にやっている人がいたので始めました。

・数学は強くないです。OMC(?)をやっている人たちは凄いと思います。

・競プロ以外の趣味だと音ゲーがあるでしょうか。何とは言いませんが最近レートが16.75になりました。つまみを回すタイプの音ゲーには興味があります。誰か教えてください。

振り返り

f:id:lev635:20211220004248j:plain

f:id:lev635:20211220011619j:plain

1. コンテストに参加するまで

先述した通り私はプログラミングの経験がなかったので当然ですがまずはそこから始めました。AtCoderのトップページにAPG4bなるものがあったのでそれを使いました。最後の問題が異常に難しくて困ってました。

APG4bを終わらせた後はABCの過去問を少しやって初めてのコンテストに臨みました。結果は4完緑perfでした。Dが累乗を求める問題だったのですが、当時の私は繰り返し二乗法を知らなかったので二乗と四乗を予め計算して何とか間に合わせていました。

当時の提出（かわいい）：

atcoder.jp

2. 灰から茶まで

この時期はABC-Cあたりをやってたと思ってましたが記録を見ると結構難しい問題もやってますね。ABC-Cが想像以上に難しくて絶望していた記憶があります。ただこの頃はレートは順調に上がってくれて、ABC203で青perfを出して緑色になりました。正直この時期のことはあまり覚えてないです。

3. 緑

緑色になった直後は謎解きをしていたので競プロをあまりやっていませんでした。これ本当に面白かったのでやってみてください。この感動を共有したい。

0414.works

謎解きが終わってレートを見てみると見事に停滞していてこれはまずいと思い真面目に勉強を始めました。具体的には水diffの問題を解けそうな問題から埋めていきました。結果としてレートは順調に上がり、水色になりました。

4. 水前半

ちょうどこの頃夏休みに入り、まとまった時間ができたのでひたすら水diff以上の問題を解いていました。最初はレートもそれに応じて増えていきましたが徐々に雲行きが怪しくなり、ARCで負けてレートが61減ったこともあって結局夏休みで100程度しかレートが増えませんでした。夏休みを利用して青になろうと思っていただけにこれは残念な結果でした。

夏休みが終わると大学が幅を利かせはじめ、急に忙しくなりました。当時の私はこれに耐えられなかったらしく（？）軽く病んでいました。病んでいる人が良い成績を取れるほど競プロは甘くありません。今度はABCで負けてレートが55も減りました。ちなみにこの負けた二回(ARCとABC)のパフォーマンスは初参加の時より悪いです。

5. 水後半

2か月以上もの間レートが増えなくて最悪でしたが、ABCで負けた頃には私も大学をいなせるようになっていて、（主に精神面で）競プロにリソースを割く余裕が出来てきました。そのおかげかあれだけ伸びなかったレートが急に伸び始めて今に至ります。

いろいろ

解いた問題

f:id:lev635:20211220014723p:plain

f:id:lev635:20211220134026p:plain

解いている方だと思います。Streakは惰性で伸ばしているだけです。これを公開する頃には切れているかもしれません。

ライブラリ

他の記事では知っているアルゴリズムを紹介していることが多いですが「知っているアルゴリズム」という言葉が曖昧で私はあまり好きではないので代わりにライブラリのうち主要なものを紹介します。全てVSCodeのスニペットに保管してあります。

定数

・円周率

・よく使われる素数（後述のmodint構造体と一緒にしています）

mod関連

・modint構造体

・二項係数

・累乗（0^0と指数が負になっていたらREを出すようにしています）

・逆元（ユークリッドの互除法）

・離散対数（ABC-Gを解くためにインターネットから拾ってきたもの）

数学

・有理数（大小比較のみ）

・行列

・エラトステネスの篩（O(NloglogN)）

・拡張ユークリッドの互除法

・CRT

データ構造

・UnionFind（union by size）

・セグメントツリー（抽象化）

・遅延評価セグメントツリー（これも抽象化していますが使い方を忘れました）

その他

・全方位木dp（これも使い方を忘れました）

・Z-algorithm（添え字の動きなど細部までは理解していません）

・閉路検出 / トポロジカルソート（実装が面倒なので）

・座標圧縮（1次元）

・配列などの中身を見られるようにするマクロ（強い人の提出から拾ってきました）

知っているアルゴリズムについて少しだけコメントしておくと、普通の水色の人が持っていると予想される知識ぐらいしか持っていないと思います。

感想など

・水色から青になるのに約五か月かかったので黄色になるのは一年以上かかるでしょうか。早くunratedでABCに参加したいですね。

・何故ここに来てレートが増え始めたのか自分でもよく分かりません。多分ここ数回のコンテストに出た問題が得意だったからだと思います。

・これは多くの人が言っていることですが、最近になってようやく「問題が解ける」ことと「コンテスト中に解けること」の違いを認識し始めました。前者の力を伸ばす勉強と後者の力を伸ばす勉強は違う性質のものだという言説も少しわかる気がします。強い人たちがバーチャルコンテストを勧めるのもそういうことなのでしょうか。

・精神状態が良好ではない間は競プロから離れた方が良いと思います。これは競プロ以外にも当てはまりますが。

・これは私が水色になった時もそうだったのですが、ABCに青diffの問題があまり残ってないので困っています。6問ABCの問題のうち残っている青diffはこれを書いている時点で2問しかありません。

・ただそれでも一色上の問題を解くのは（今のところは）間違っていなかったと思います。どうせ色が変わったら一色上の問題も解けなきゃいけなくなるので。

・そろそろARCと戦わなきゃいけない時期になってそうですがそれでもARCから逃げたいです。Aや簡単めのBで事故ってそれ以降が解けなくなるのが怖くて参加できません。

・一方でARCの問題は考えていたらそのうち解けることが多いので楽しいですね。これとか。この「そのうち」が120分に収まるようになったら参加しようと思います。

・ABCの問題は解説ACした方が良いと色々な人が言っていて私もそう思うのですが、解説を読んでみたらただの考察不足だった、というのが怖くてなかなか解説を見られずにいます。これ多分成長を妨げています。

・はてなブログのエディタが狭くて使いにくかったです。誰か使い方を教えてください。

・青くなったのでヘッダーも青くしようと画像を漁っていたのですが、分かりやすく青い画像が自分のBB素材しかなくて困りました。

・学業が崩壊しかけています。助けて。