nawaの競プロdiary

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

ついでに水色以前のことを回顧する

はじめに

こんにちは、nawaという名前でAtCoderやってます。
nawa - AtCoder

今回青になることができ、色変記事も書きました。
AtCoderで青色になったので回顧する - nawaの競プロへのお気持ち表明

調子に乗ってこのまま水色になるまでを振り返ろうと思います。
この記事はどんなアルゴリズムを学んだとかそういうのはなく、ただ単に振り返っただけとなっています。

だいぶ雑に書いてキモい文章となっていますが、ご了承ください。

競プロとの馴れ初め

そもそもAtCoderを始めたきっかけは大学でアルゴリズム入門という講義をとり、なんか周りの人が競プロなるものを始めているのでワイもやるか〜ぐらいの気持ちでした。アルゴ入門もそこまで成績がいいわけでもなかったのに。

灰色時代

たまにAPG4b(https://atcoder.jp/contests/APG4b)を読んでc++の文法を勉強するだけで、後は何も考えずにコンテストに出ていました。大学の周りの人々がレートを上げていくので、まぁワイも†地頭†だけですぐ上がるやろ！と思っていたし、モチベもあまりなかったので気が向いたらやる、程度のものでした。

茶色時代

始めてから4ヶ月後ぐらいで茶色になったんですが、当然精進は何もせず_____。それでも単調増加していたので結構調子に乗ってました。

この辺りで学科が始まって、周りにも競プロやってる人が結構いたので参加回数が増えていきました。
が、しかし

とうとう頭打ちが来てしまい、学科がめちゃくちゃ忙しかったのもあってモチベが霧散しました。

f:id:nawawan:20201123175138p:plain
オワリ

春休みに入って、AtCoderに登録して複数回のコンテスト(もしかしたら初回だったかも)で緑になった人と出会い、やっぱガチの天才っておるねんな…と思うとともに(というよりその人はしっかりアルゴリズムを勉強していたのだと今となっては思いますが)、『お前は天才じゃないんだから黙ってアルゴリズムの本を読んで精進しろ！！』という気持ちになってようやく蟻本を読み進めることにしました。

春休み中にプリム法あたりまで読んでいざコンテストで爆上げしてやるぜ！となったんですが、まぁ知っての通りABCでただ単にダイクストラ やるだけみたいな問題は出ない(さらには最小全域木が絡む問題なんて見つける方が難しい)ので、あまり結果が出ずに結構苦しみました。

f:id:nawawan:20201123180225p:plain
ｳｵｵ

ただ、蟻本読んで問題を解いて…ということをしていくうちに、「問題をとく」ということに慣れてきたのか、解くのが早くなって4月に緑になれました。

緑色時代

コロナ関係で暇が増えたこと、アルゴリズムの授業があったことで学科内で結構競プロerが増え、学科民と精選100問(レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita)を解くという企画があって、これのおかげでかなりアルゴリズム力がついたと思います。

(この精選100問、ガチ有能で、ある程度プログラミングに慣れている人ならこれやるだけですぐに緑色中位にはなれると思います)

この頃からようやくAtCoder Problemで過去問埋めを始めて、順調にレートを上げて水色になることができました。
f:id:nawawan:20201123180957p:plain

お前は天才じゃないんだから黙ってアルゴリズムの本を読んで精進しろ！！

レートのグラフを見てわかると思いますけど、本格的に精進を始めてからレートが伸びています。

灰色時代にアルゴリズムの知識が全くないのにレートが上がると思っていたの、末代までの恥です。カス。

最後にProgress Chartの一部を載せておきます。

f:id:nawawan:20201123181243p:plain
頑張った自分、えらい！！！！

まぁやはり問題を解きまくったらレートが上がるってことなんですかね？知らんけど。
精選はガチ有能です。本当に。

最後に

今も「お前は天才じゃないんだから問題をたくさん解いて精進しろ！！！」の精神で競プロをやってます。

ここまで誰得かわからない駄文を読んでくださり、ありがとうございました。

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も「自分は天才ではないから問題を解きまくって成長した」と言った』的なツイートを見かけたのでやっぱ解いた問題数は正義なんやな…ということです。

終わりに

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

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