見出し画像

競プロ未経験から1年でAtCoder水色になった話。

じっきー

お久しぶりです！じっきーです！！！メリークリスマスです！


報告遅れましたが、AtCoder水色になりました！！！！！！！！！！

9月中は僕自身も水色になった実感が湧かなくて、、、ﾌﾜﾌﾜしていました。。。。。水色になるまで1年もかかったので、とても、とても嬉しかったです。

その一方で安心もしています。入緑した際に、「8月中に絶対水色になってやる！！！」を宣言していたので、(1ヶ月遅れになりましたが)目標を達成してホッとしました。

そして、この記事を色変後すぐに書いて公開しようと思ったのですが、パソコン甲子園の本選やJOIの二次予選があったりで忙しくなった結果、水色になってから3ヶ月後のクリスマスに、書きかけだったこの記事を急いで書いています笑

世の中には数多くの入水記事がありますが、どこよりも丁寧に、入水するまでに「なにをしたか」を明確にして、特に緑色コーダーの方に向けて水色になるためには、なにを行えば良いのかの指針になるような内容になるようにがんばりました。色変してからしばらくたった今だからこそ、緑色だった頃を思い返しながら思いを綴っていきます。

この記事は競プロ Advent Calendar 2023の24日目の記事です！他の方の記事も非常にためになりますので、ぜひご確認ください！

また、こちらのマガジンには過去の色変記事もあるので、まだ見ていないよ～という方は先にそちらをご覧ください！

非常に長い記事になると思いますが、ぜひ読んでいただけると嬉しいです！
最終更新日: 2024/02/22


最新のAtCoder水色のレベル感

E8さんの記事では水色の相対的な位置は「上位10%」となっていますが、もう3年以上前のデータです。そこで現在のレベル感を調べてみました。

AtCoderの順位ヒストグラムのソースから上位何パーセントかわかる早見グラフをPythonで作ってみた | ごごちとねこの日常 より引用

この図は1600レート未満の累積上位%のヒストグラムです。
3年前の母数と今の母数の変化も気になりますが、水色は上位6.3%。
3年前の青色と同じような立ち位置になっています。
かといって難しくなったのかと言うと早計で、昔と比べて記事や資料が充実していますし、入水の難易度はさほど変わっていない気がします。

筆者の入緑時スペック

入緑したABC292頃の結果を見たほうが早いですね。

入緑時のAtCoder Problems(濃い緑色がコンテスト中にACした問題です)

  • 茶diffは安定し始め、3完はほぼ確実。4完もちょくちょく出だした。

  • 1250問弱を既に解いていた(主にABC-A, B, C, D)。

  • E8さんの記事に載ってある12個のアルゴリズムと3つのデータ構造は一応理解した。(入緑記事)

  • 鉄則本をとりあえず1周した。(入緑記事)

初めた頃はA問題もままならない状態だったので、成長しました；；
ただやっぱり緑diffは本番で解けず、水diffはもはや解けるのか？？？となっていました。(ABC292はたまたま水diffが解けて入緑したって感じです。)

水色になるためにはなにが必要か

いきなり核心ですが、最終的に水色になる方のゴールとしては

  • ABCの4完を8, 9割以上の確率で達成する

  • ABCの5完を3, 4割以上の確率で達成する

ことだと思います。そして、緑の期間で僕自身がとても感じたことは

茶色diff・緑色diffの安定

こそが4完、5完を安定させる為に必須条件であることです。
つまり、水色中位や上位など自分より格上の問題を本番で通すことよりも、「いかに茶色・緑色diffを素早く考察・実装できるか」がレートに直結したと痛感しています。緑色diffをコンテスト中に安定してACできるかが水色になるためには一番大事だと感じています。

水色になるまでにやったこと

緑diffの安定のためにも、僕が半年間に行ったことを列挙します。

ABC緑diff全埋め

まずは敵を知ることから。

というわけで GW の期間に僕が埋めていない緑diffを詰め合わせたバチャを開いて、「埋めないといけない」という環境を無理やり作りました。
自力ACは半分くらいで、残り半分は解説を見て理解しました。これを行ったことにより、ABCでstreakを繋げるには水diff以上じゃないといけなくなり、自分より格上の問題に毎日挑戦できるようになりました。

あと、メンタル的な面でも緑埋めは有効でした。
「ABCの全ての緑diffを解いたことがあるなら、これから出題される緑diffにもきっと正解できる」という強い自信が得られます。実際に緑埋め後のコンテストでは、本番ACの割合はかなり高くなりました。
Bitmask君、、、Modulo MST君、、、。

ABC-Cを全埋めする

非推奨です。
なぜなら埋めることに執着しすぎて、埋めることが目的となってしまっていたからです。青diff試験管があり、あまり理解できないまま根性で通してしまいました。。。良い子のみんなは真似をしない方が良いです。再び復習をしないといけない羽目になります。

ABC201以降のD問題を埋める

先程のABC-C全埋めよりも遥かにオススメです。
けんちょんさん曰く、ABC201～300で一通りの典型要素が詰め込まれている為、この範囲のC, D, Eを埋めていけば、典型要素をある程度拾えると思います。全部埋めるのが面倒な人はここから埋めると良いかもです。

なお初期の6問時代(ABC201～211)のDは難易度が高い問題が多いので、そこの理解はあまりできていません。要復習です。。。
それ以降の8問時代(ABC212～300)に関してはかなり埋める価値はあります。
埋める順番は茶色→緑色→水色と難易度の昇順に解いていきました。

入水までに埋めたC, D問題

入水に必須なアルゴリズムは、ABC-D, E で登場するアルゴリズムを学べば十分だと思います。(さらに言えば、緑色diffに登場するアルゴリズム、データ構造さえ知っておけば、最低限必須なアルゴリズムは揃います。)
なので、めんどくさいとはいわずに過去問を埋めることを薦めます。

青色diffに挑戦した

Etisさんが、「青色diffやるぞ！！」となって青色diffのバチャを立てたことがきっかけです。緑色コーダーが他にも参戦していたので、そこに便乗する形で青色diffの問題に挑戦しました。
ほとんど自力では解けないのですが、全く手の届かない問題でもないことは大きな発見でした。やはり、下位色diffの安定も大事ですが、上位色diffの問題にも触れておくことは今後さらに強くなるためにも大事です！

アルゴリズムのスライドを作成した

これは少し特殊ですが、競プロの部活で教える立場の為、基本的なアルゴリズムに関する説明スライドを作っていました。1度基本に立ち返って、このアルゴリズムはなぜ動作しているのか？というブラックボックスをなるべく排除して説明しようと心がけた結果、「(アルゴリズム名) 記事」で検索すると出てくるネット上の記事はあらかた見尽くしました。

今まで作成したスライド達。各スライド90ページくらいの量があります。ﾋｪｰ

自分が教える立場になるということは、なにを聞かれても即答できるくらいそのアルゴリズムを理解していないといけないということです。
ですので、スライドで作った累積和や二分探索、BFS、DFS等のグラフアルゴリズムは考えなくても脳死で使えるようになりました。

バチャに出る

これ、すごく大事です。
入緑記事では「本番さながらの雰囲気」「C, D問題を早く解く練習」と話しましたが、今は一度解いた過去問を再び復習できる大事な機会と捉えています。
やっぱり人は忘れやすい生き物ですので、過去問を1度解いただけでは、完全に問題を定着しきってないものも多数存在します。
バチャは今まで自分が解いたことのある問題も当然出題されるわけですから、解いたことのある問題を落としたのならとてもラッキーです。再び復習するチャンスが生まれるわけです。いかに自分の引き出しにできるか。これに尽きます。おすすめのバチャは

  • ABCなにか(ABCDの4問)

  • まよコン(灰灰茶緑水青(黄or橙)×2の8問)

こちらの2つです。茶色の方や緑色になりたての方はまずはABCなにかのほうが参加しやすいと思います。CD問題は茶色・緑色diffがほとんどですので練習になります！
まよコンは僕自身、数回出ただけなのですが、どちらかというと水色以上向けのイメージの印象があるのでチャレンジしたい方はぜひ！

追記:
10月17日にAtCoder Daily Trainingという、公式のABCバチャが登場しました。学生向けというのもあり時間は夕方なのですが、めちゃくちゃ重宝しています。自分は水、木のALLに出ているので、一緒にやる方募集中です！

入水までにした方が良かったこと

自分はしていませんでしたが、入水するためにやったおいたほうが良かったことを簡潔にまとめます。

EDPC

僕自身は灰色時代にA~Eまでを埋めたっきりなにもしていませんでした。。
ですが入水後、つなさんのpostをきっかけにP問題まで埋めてみました。
個人的に入水する方は確実に解けるようになって欲しい問題はA,B,C,D,E,Hの6題です。これだけは1度解いておいた方が良いでしょう。(FのDP復元やGのDAG上のDPはたまーにABCで出題されるので解いておいた方が良いと思います。)

典型90問

★5の途中まで解いていましたが、緑色の期間中は全く手をつけていませんでした。正直、初見だと★2でも僕は難しい問題があると思っていますが、ABC埋めをこなしていけば自然と解けるようになっていきます。

正直、典型90問は自力ACするものではなく、新しい典型知識を学ぶための教材なので、分からなければ解説ACを積極的に行ったほうが良い問題だと認識しています。
なので、自分の色より下の難易度(例えば、今のあなたのレートが緑色なら★2～★3の問題)であれば典型要素が身についたかどうかの確認として利用し、自分の色より同程度、または上であればどんどん解説ACをして典型知識を得るために利用するのがベストだと思います。

入水までに費やした時間

はい。667時間です。

入緑(2023/03/04)から入水(2023/09/17)までに競プロに費やした時間

補足として、かなり(計測するのを)サボった時期があったのと、これはPCに向かって精進した時間であることにご注意を。実際は起きてから寝るまでずっと問題のストックが頭にあり、それを考えていたり、記事を見ていたりしています。
入茶→入緑が300時間なので、多分競プロに費やした時間は軽く1000時間を越えていると思います。1000時間の法則という言葉がある通り、人間やれば案外できるものなのです。緑色で伸び悩んでいる人、一回1000時間競プロに時間を当ててみましょう！！！！！

Re: 精進方法

入水時もほとんど入緑記事と同じような精進方法でやっていました。詳しくはそちらを参照してください。
ですが、入緑時と異なる点がいくつかありますのでご紹介します。

「なんとなく」から「証明」まで行う

「なんとなく〇〇を使ったらうまくいきそう」
「なんとなく△△したらうまくいきそう」

これでWAが出て、ｸﾞｵｰｰｰとなっている皆様。

自分もまさにこれでした。「ACしたらいいなぁ」であんまりロジックを詰めずに今まで行っていました。これじゃあだめだなと思い、きちんと「証明」まで考えるようになりました。証明と言ってもガチガチじゃなくて大丈夫です。最適解が導ける論理を頭の中で構築できれば問題ありません。

これが物凄く効いたのは「貪欲…？」の問題です。
貪欲の正当性の証明(swapしても状態が悪化しない議論)がなんとなく分かってくると「貪欲…？」の問題(例1, 例2, 例3)に特攻しなくて済みます。
自分は貪欲と関連のあるマトロイドについては未履修なので、水色の期間中に勉強していきたいです。

ランダムテストを普段の精進に取り入れる

個人的に水色と緑色の差はランダムテストできるか/できないか。みたいな所がある気がします。

愚直解は分かるのに、計算量を落とす解法で何故かWAが出る。。。

というときに非常に役立ちます。自分はABC318で救われました。これを普段から練習しておけば、デバック力爆上がりです。
詳しくはこちらを参照してください。

特にJOIの過去問は部分点に愚直解法が置かれている場合がありますので、ランダムテストを回す練習になってオススメです。

解説を自分なりにまとめる

実は、今まで一度もTwitter等で公言していない精進方法で、一番効果があったものです。自分だけの秘密にしたかったのですが、JOI二次予選も終わったので紹介したいと思います。

これが全てです。

今までに書いた記事

今までに解いたJOIの難易度4からの問題や、バチャで間違えたABCの問題をけんちょんさんの解説記事レベルまで、自分が納得するまでとことん詳しく解説しています。(解説を書いている人はいるけど、流石にここまで詳しくまとめている人はいない気がします。)
勿論、適当に問題を選ぶのではなく、自分が何度も間違えた問題や、いろんな応用ができる典型問題、自分が最近学んだアルゴリズムが出題されている問題、自分が今一番力を入れているJOIの問題など、自分にとって重要度が高い問題だけ選んでまとめています。
また、ただまとめて満足するのではなく、「次同じような問題が出たときにどのように対処すればよいか」をパッと参照できるリファレンス的役割も果たしています。

自分はかなりの完璧主義で、こういう部分で無駄な几帳面さが出てしまって、時間のロスだと思ってはいるのですが、解説でまとめた問題は絶対に次は解けるようになっているので、余裕がある人は記事をつけてみてはいかがでしょうか？？？

もし、解いたことがある問題を落とした場合、普通に解説を見てACするだけではなく、「なにが解くために足りなかったか」を重点的に振り返りした方が良いです。それが低diffであればあるほど、実際のコンテストで致命傷になりかねません。低diffを落としたときこそ記事を書いて、慎重に振り返りをしていました。

新規デ/アの学習方法

これに関して、悩んでいる方も多いと思いますので、自分が行っている方法を紹介します。

とっさに〇〇を学習しよう！と思い立つことはほとんどなく、ABCの精進中や、コンテスト後に知らない(理解していない)アルゴリズムやデータ構造や典型が出てきたりした場合に、自分のレート+1色くらいのdiffであれば学習するといった感じです。
その学習を行うときは、その問題の解説をじっくり読んだり、ネットの記事を複数読み漁ったり、他の方が公開しているライブラリを眺めて理解してみたり、類題を何問か解くことで学習しています。
また、理解した際にはライブラリも作っておくことを強く薦めます。
やっぱり、すぐ使いたいときにパッと使えるのと、自分がちゃんと理解しているかの確認にもなるので。(つい最近だとJOI埋めでRollback可能UnionFindが出てきたので、学習してライブラリ化しました。)

どちらかといえば、水色になるためには二分探索・累積和・グラフ探索あたりの緑色になるために必要なアルゴリズムに関する典型知識、例えば

  • 左右から累積和

  • 最小値の最大化、最大値の最小化などは二分探索

  • 頂点を倍加してBFSやダイクストラ

などなど。。。(列挙したらキリがない！)を習得するのが先な気がします。詳しくはこちらのスライドを参考にすると良いです。この典型知識の理解を優先しつつ、新しいデ/アが登場すれば、その都度学習を進めていく方が自分には合っていました。

ライバル・仲間を見つける

これはかなり、モチベーション維持に繋がりました。
他人と比較しすぎるのはよくないですが、Twitterで精進ツイートをされている方を見ると、だらけている自分に喝が入るというか。「彼らは今も問題を解いているんだな！」となって、自分も問題に向き合えるようになります。
個人的に今、(格上で)ライバル視しているのは、AC2Kさん(アイコンかわいい)、DeltaStructさん(絶対駆け出しではないｗ)、Blueberryさん(心の中でいつもぶるくんと呼ばさせていただいてます)です。彼らの共通点として、

  • 全員異常精進erでコンスタントに問題を解き続けている

  • Twitterで進捗をよくツイートしている

  • 一瞬で自分のレートを抜かされてしまった

であることです。やっぱり、自分より努力していて、ちゃんと結果残している方は本当に凄いなと思うばかりです。彼らだけではありませんが、SNSにいる競プロerと高め合うことで、「ひとりじゃない」と思えることはモチベーションの面で非常に効果を発揮すると感じました。正のモチベーションになる場合であれば、他の方と比較しても良いんじゃないかなと。

実績ペタリタイム

Achievement & AtCoder Pie Charts & Difficulty Pies & Category Pies
Progress Charts
Heatmap
AtCoder Charts

おわりに

実はStreak Sumを見てもらえると、入水にかかった期間は実際には1年じゃなくて1年+1ヶ月みたいです。。。でもキリがいいので1年にさせてください。(切実)

次の入青は宣言もした以上、来年4月までには達成したいと思っています！

現時点でレートが1300なので、無理ではないと思っています。そのときの色変記事は、、、需要がそこまでなさそうな感じがするので、あるとしても今までのように事細かにやったことや精進方法をまとめないかなと思います。

最後までお付き合いいただき、ありがとうございました！良ければ、スキ！をしてくださると励みになります！
あと後日、PCK参加記とJOI参加記を上げる予定なので、またそちらでお会いしましょう！

最後に、公開直前に校正、試し読みを行ってくれたScjpのみんなに感謝を。本当にありがとう。

この記事が気に入ったらサポートをしてみませんか？