nawaの競プロdiary

競プロのなんかを書いていけたらいいなぁ(展望)

AtCoderで青色になったので回顧する

はじめに

nawaという名前でAtCoderをやっています。

早速ですが、AtCoder Beginner Contest 184にて念願の青色になりました。
f:id:nawawan:20201123154602p:plain

そういえば色変記事書いたことないな〜という気持ちで軽率に色変記事を書きました！(こういう記事書くの初めてなので読みにくいのは許して…)

基本的にやったことをただ書いていくだけですが、誰かのやくにたてたらいいなぁ〜と思います。

(追記: 水色以前のことも回顧しました
ついでに水色以前のことを回顧する - nawaの競プロへのお気持ち表明)

レートの変遷

f:id:nawawan:20201123151920p:plain

水色になったのが7/11で、最初の3ヶ月はあまりレートが伸びずに停滞していたんですがARC105を皮切りにゴリゴリレートが上がり、そのままの勢いで青になれた感じです。水色になってから4ヶ月半で青になれたので、かなり早い方だと思います。

やったこと

解いた問題数はこんな感じ
f:id:nawawan:20201123154321p:plain

これが多いのか少ないのかわかりません…。Streakはあまり気にしない派ですが、一週間何も解かずにコンテストに出ることはしていません。精進は基本的に自分の今の色と一個上の色の問題を解いていく感じなので、解いた問題の内訳は以下のようになっています。

f:id:nawawan:20201123154845p:plain
内訳

問題の解き方

基本的に精進は過去問埋めになると思うんですけど、一問から得られる知識をいかに多くできるかが大切だと思っています。

具体的に言うと以下の二つをやる感じです。

  • 自力ACした問題でも解説を見て解法が異なったら解説解法でもACする
  • 解説に別解があったら、その方法でもACする(これはできたらでいい)


特に一つ目が大事です(基本的に解説の方が綺麗な解法をしているので)。
最近痛感することがあり、ARC108-Bで燃やされました。
f:id:nawawan:20201123161317p:plain
これは似たような問題(AGC5-A)を添え字をガチャガチャして解いたのに、解説を見てなかったのでstack解法を知らなかったからです(それでも再発明するべきだったかも知れませんが…)。


個人的には青diffの問題とかで1時間考えてなにも検討がつかなかったら解説を見てもいいと思います。ただ、解説放送を見て実装を真似するのは良くない気がします(理解した気になるだけになりそうなので)。解説を見て実装方針を理解したら後は自力で実装するべきです。

早解きはいいぞ

早解きはいいぞ(今回のレート上昇の大半も早解きなので)。

今のABCはEに緑diff上位〜水diff下位来ることが多く、Eまでを60分で解けてFが簡単ではなかったら青パフォが出る。しかもEまでを早く解けたらFに割く時間も増えて全完の可能性も上がる。Fが解けなくても水色ならレートが下がることはほとんどない。

いいことづくめですね。

早解きができるようになる方法ですが、自分の色の一個したまでの問題を4問くらい連続で解くことだと思います。実際自分が水色になってから停滞していたのはA問題やB問題で余計なペナを増やしてしまったからで、レートが上がるようになったのも灰diffや茶diffの問題を埋めることでA問題からD問題の間で不要なペナが出なくなったからだと思います。

水色になってから学んだアルゴリズムとデータ構造

学んだし、たまに使うもの

  • セグ木
  • BIT

学んだけどあまり使わないもの

  • 最大流
  • 最小費用流

学んだけど全然使わないもの

  • 遅延セグ木
  • 幾何全般(凸包とか)
  • Suffix Array
  • SCC
  • 2-SAT
  • Grundy数
  • ロリハ
  • Z-algorithm

これらほとんど使ってないです、、、。セグ木はたまに使うんですけど、よく考えたら実は累積hogeで代用できたりsetで代用できる場面が多いですし…。

他はACLが配布されてブラックボックスなものを使うのが嫌だったので蟻本を読んで理解したのが多いです。

まぁ知識として持っておく分にはいいかな〜？という感じです(使いこなせるかどうかは怪しい)。

ただ最大流、最小流はある問題をグラフ問題に帰着して、自分でグラフを構築して使用する場面が多いので、実装方法や考察の仕方などかなり学べることが多かったです。

コンテストに参加する

参加しなければレートは変動しないので、当然です。

AtCoder

基本的に外出の用事がない限り出ています。大学のタスクが山積みな場合でも、たかが1時間40分でできることなんて知れているの精神で出ます。

Codeforces

夏休みから参加し始めました。知らない人のために説明しておくと基本的に日本時間23:35から1:35までの2時間でコンテストを開催するロシアのサイトです。

これもどうせ毎日3時ぐらいまで起きているんだから参加するぞ！の精神なんですが、今のところあまり参加できてません……。過去問埋めをしたりUpsolveをしたりするほど本格的にやっていませんが、AtCoderではなかなかでない実装問題とか典型問題が出てくるのでかなりためになります。

yukicoder

競プロerが作問した問題が解けるサイト。様々な競プロerが作問しただけあって、数え上げやゲーム問題などいろんな種類の問題が充実しています。金曜の21:20から2時間のコンテストが毎週開催されていて、レートもないので気軽に参加できます。典型問題から発展的な問題まであり、ACL2と問題が被るなど、とても質が高い問題が多いです。


自分は今基本的にこの3つのサイトのコンテストに参加しています。
コンテスト中のACが一番価値高い的なことをchokudaiさんも言っていたので、とにかくコンテストに出るのは大切だと思います。

やってないけどためになりそうなこと

複数の垢を運用するほど器用じゃないという理由で競プロ垢作ってないのであまり詳しくないんですけど、ある競プロerがあさかつ、くじかつというものを作ったらしく、AtCoder Problemsで毎日朝7:30から8:30までと夜9:00から10:40までバチャを開いています。実際のコンテストと同じように他の競プロerとリアルタイムで競いつつ問題を解けるので良さそうです。

さらに、Codeforcesのバチャも有志で開いているらしく、上記のあさかつ、くじかつと同様にいつか参加したいな〜と思ってます。

うお！

結局はひたすら問題をといて、一問から得られる経験値をいかに多くするかだと思います。
『かのtouristも「自分は天才ではないから問題を解きまくって成長した」と言った』的なツイートを見かけたのでやっぱ解いた問題数は正義なんやな…ということです。

終わりに

青色になれたということだけでも望外の結果なんですけど、これからも黄色を目指して頑張ろうと思います。
まぁ見ての通りギリギリ青になれた感じなので、とりあえずは水色に落ちないように頑張っていきます。

駄文をここまで読んでくださり、ありがとうございました。