見出し画像

【入水】半年かけてAtCoder水色になりました！【色変】

霧しゃま

そろそろ新人ではない競プロerの霧しゃまです！
昨年11月からAtCoderにハマって早くも半年が経とうとするところですが、去る2023年4月29日、水色になることができました。
今日は、まだまだ上を目指すために、これまでを振り返ってみたいと思います！
これから水色を目指されるみなさまの参考になれば幸いです！

ざっくりプロフィール

ハンドルネーム：霧しゃま（AtCoderId: Kirishima）
アイコンの鳥さん：ヒシクイ（ガンカモ科の水鳥）
インターネット歴：20年以上、WindowsMe世代
プログラミング歴：本格的に始めたのは2020年初頭から
AtCoder歴：2022年11月から、初RatedはABC276
学歴職歴：詳しくは秘密。いちおう理系の大学は出ている
使用言語：競技プログラミングのために仕込んだC++
その他経験言語：Python、Javaなど
情報系の資格：応用情報技術者試験(AP)など
好きなゲーム：もじぴったん（PS2）、メテオス（DS）など

灰色5回、茶色5回、緑色10回、水色は……？

忙しい人向けのまとめ

・水色達成ありがとう！　青色目指し頑張ります！
・何事にも屈しない強靭な心こそが、最強の武器なのです！
・精進量に自信あり！　ABC緑以下埋めてみた記事もよろしくです！

入緑までのあらすじ

2022年11月にAtCoderで競技プログラミングを始めた霧しゃまは、2023年1月末に緑コーダーになりました。
始めた当時はAtCoder Beginner Contest（以下ABC、全8問）で3完程度の実力でしたが、主に『鉄則本』で基礎的なテクニックを身につけ、5完に手が届くくらいになった頃、入緑しました。
そのときの様子はコチラ！

【２月】水色精進を始めた

  • ABC288：9分で3完（予選仕様）

  • ABC289：28分で4完

  • ABC290：51分で4完、1ペナ（予選仕様）

  • ABC291：50分で5完、1ペナ

緑コーダーになりたての頃です。
コンテストのパフォーマンスで言うと、この頃はギリギリ水色のボーダーである1200前後になることが多く、安定はしていましたが、遠からず停滞するだろうという予感がありました。
緑色レベルの問題（ABC290DやABC291E）は本番で通せるようになりましたが、これは緑色レベルの問題で精進をしていたからであって、水色レベルの問題（ABC289EやABC290E）を前にすると、途端に歯が立たなくなってしまうのでした。
結局、水色レベルの問題を本番で通せるようになるには、ある程度事前に水色レベルの問題に触れておく必要があったのです。
そこで、2月の中旬あたりから、ABCの水色レベルの問題を毎日1～2問以上解くことにしました。これは今でも続けています。5月中には終わらせて、青色レベルの問題にシフトしていきたいです。

【３月】乱調の季節

  • ABC292：私用により不参加（この日、TUPCに潜入して2完だった）

  • ABC293：59分で4完（耐え）

  • ABC294：99分で6完（上振れ）

  • ABC295：14分で3完（冷え）

3月は激動でした。ABCの緑色までの過去問を解き終えたのもこの頃ですが、そのために生活リズムがやや乱れ気味になり、肝心のコンテストで思うようなパフォーマンスを出すことができなかったのです。
特にABC295では、D問題で手が止まりました。そこまで継続していた見かけのレートの単調増加が、ここで途切れたのです。
コンテスト自体も、G問題で高度典型そのままが出てF問題とのAC数逆転現象が起こったり、結果としてEからGまでが黄色レベルの判定になったり、D問題との落差が物議をかもしたりと、やや荒れていた印象です。
一方で、ABC294ではどさくさに紛れて6完することができました。G問題がHL分解だった回です。インターネットでほとんど同じ問題に行き当たり、そのコードを流用する形でACしました。
この上振れはレート上昇に大きく寄与しました（+102）が、ほとんどまぐれだったと思います。実力よりもレートが上がりすぎて、次の回にはプレッシャーが高まることになりました。それもABC295で冷えた一因だったと思います。つまり、揺り戻しです。

【４月】Unrated

  • ABC296：68分で5完、2ペナ

  • ABC297：66分で5完

  • ABC298：74分で5完、1ペナ（Unrated）

  • ABC299：69分で5完、2ペナ（Unrated）

  • ABC300：62分で5完（入水！！）

4月に入ってからは、水色精進の成果が出始めたのか、5完が安定するようになりました。ABC297が終了した段階でレートは1169になり、4月中には水色になる1200に到達できる！と意気込んでいましたが……。
ここで大事件が起こります。界隈を震撼させたDDoS攻撃です。これによりコンテストが2回連続でUnrated（無効試合）になってしまい、絶望的な雰囲気が漂いました。
4月中に入水したかったのは、もともと4月30日に予定されていたAtCoder Grand Contest（以下AGC、上級者向けのコンテスト）のRated参加権を得て記念参加したかったというのが第一です。これもDDoS攻撃の影響で延期になったので、もはやあまり4月中の入水にこだわる必要はなくなっていました。
1169というレートは、1回で入水するとなると1430程度（水色中位）のパフォーマンスが必要になり、緑コーダーにとってはなかなかチャレンジングです。半分は諦めていました。
しかし、残り半分は諦めていませんでした。実際、5完が安定しているので、チャンスは大いにあったのです。あとは、AtCoderのサーバが耐えてくれることを祈るだけでした。
そして迎えたABC300です。水が前だけど背水の陣、何があっても全集中・水の呼吸という意気込みで臨みました。
その結果、無事にノーペナで5完を達成しました。パフォーマンスは、青色レベルの1667です。ABC294以来、初めて実力でつかみ取った青パフォでした。
DDoS攻撃の影響もなく、またいつものABCが戻ってきました。AtCoder運営のみなさま、本当にありがとうございます！

【Q1】入水の決め手となったものは？

ここからは、色変記事特有のインタビューです。
入水の決め手となったものは、やはり水色精進だったと思います。
緑色は、基礎的なテクニックを『鉄則本』などで学んで、ABCで平均4完くらいできれば入ることができます。
しかし、水色に求められるのはテクニックそのままではなく、それらを複数組み合わせたり、応用させたりすることです。それに加えて、新たなテクニックを学ぶ必要もあります（ただし、緑色レベルまでのテクニックを一通り使いこなせることは前提となります）。

今回、直接的な勝因になったのは「確率DP」です。
実はこの4月、ABC298EとABC300Eで2回も確率DPが出題されています。
しかし、『鉄則本』には確率DPが載っていません。確率DPでは大抵の場合、答えをmod998244353で求める必要があるので、慣れていないとどのような操作をすればよいのかわからず、手も足も出なくなってしまいます。確率自体の難しさも相まって、難易度は上がりがちです。
一方で、やるべき操作がわかれば、有理数のmodはそこまで難しくありません。見た目が変な数になること（例えば、$${239578645}$$は$${7/25}$$に対応しますが、見た目ではそうとわかりません）が慣れるまで大変ですが、結局のところ、2に5の逆元を掛ければ$${2/5}$$に対応する値になるように、やっている操作自体は、modを取らないときと本質的には同じなのです。
ただ、見た目でそれが意味する真の値がわかりにくいということは、何かの拍子に誤った操作をしても、どのような誤りなのかがわかりにくいということです。ちょっとでも間違えると全く違う値になったりするので、最初から間違えないように、丁寧に設計・実装をする必要があります。

あとは、「強連結成分分解」も役立った覚えがあります。
有向グラフ上で、互いに行き来するパスが存在する頂点同士の集合を「強連結成分」といい、そのグループ分けをするのが「強連結成分分解」です。SCC（StronglyConnectedComponents）と表記されることもあります。
強連結成分分解は閉路のある有向グラフでトポロジカルソートをするための前準備として紹介されることが多い印象ですが、水色レベルだと、その前段階として「強連結成分」の性質そのものを単体で問う問題が出てきます。
本番だと、ABC296Eで使いました。「競プロ典型90問」の021（★5）が最も単純な練習問題なので、ライブラリ化しておくと便利です。

最後に心構えですが、難しい問題を恐れないこと、そして逃げないことが重要だと思います。
1～2色上の問題は最初、不可能に思えるものだと思いますが、解説ACでも良いのでそのレベルの問題で精進を続けていると、だんだん題意を理解できるようになっていきます。
しかし、ある解けない問題があったとして、それより簡単な問題を全部埋めたからといって、その問題が解けるようになるとは限りません。それまでの知識と次元の違うものが要求されることは、かなり多いのです。
「ABC-Gを解くためにはABC-Gの精進をするしかない」と最近話題になりましたが、実際この通りです。自分より上のレベルの問題に挑み続けることが、伸び続けるための必須条件です。
ただ、闇雲に難しいことをやろうとするよりは、自分より少し上のレベルの問題を中心に取り組んで、地盤を固めていくほうが良いと思います。そうすると、コンテストの成績も安定してきます。

【Q2】得意な分野・苦手な分野は？

精進は満遍なくやってきたので、緑色レベルまでなら概ねどんな分野でも大きくパフォーマンスを落とすことはないと思います。
ただ、相変わらず数学の素養が（相対的に）ないまま来ているので、思わぬところで足元を掬われそうな気がしています。数え上げ問題などで、無理筋の方針に突っ込んでしまうことがよくあります。幾何は超絶苦手です。

DPは見た瞬間に方針を立てられることが多いので、比較的得意だと思います。まあ、ABC285EとかABC291Fあたりのちょっと変則的なDPになると解けなくなるので、精進はまだまだ足りていないのですが。

グラフも最初の頃は苦手意識がありましたが、最近は慣れてきました。
ABC297Eのような、「グラフの見た目をしていない問題をグラフに帰着させてDFSやBFSで解く」タイプにも対応できるようになりました。これはやはり、ひたすら精進して様々なパターンを知っておくしかないと思います。

データ構造系の問題は、ライブラリの準備がものを言うジャンルですが、今のところ普通のセグメント木とSparseTableくらいしか使えません。遅延セグメント木は先延ばしにしてしまっています。ゴールデンウィーク中にはやりたいです。

文字列系は、まだまだ未知のエリアです。RollingHashの問題は何度か出会いましたが、それ以外を使う問題の経験がまだほとんどありません。水色精進でZ-algorithmをやったくらいです。

好き嫌いで言うと、最近のBC問題あたりに出てくる行列やグリッドをあれこれ弄る問題は、実装が重くなりがちなので嫌いです。
特にABC298B（行列を回転させる）は、ライブラリを用意していなかったこともあって実装に手間取り、面倒くさがってゴリ押し的な実装をした挙句にペナを貰うという、最悪の結果になってしまいました。
ABC300も、BCでグリッド問題が連続したのでうんざりしながら解いていましたが、このあたりで問われる基礎体力的なものからは逃れられないので、どうにか対策を練っていきたいと思います。

【Q3】精進や本番でやっている工夫は？

精進はABC042あたりの古い問題から最新に向けて解いていくタイプです。こうすると、同じ色の問題をやっていても徐々に難しくなるので、程よい難易度曲線になると思っています。
本番は、VSCodeで書いてAtCoder Easy Testでテストして提出みたいな、何の変哲もないスタイルです。ただ、AtCoder Easy Testはコンテスト開始後一定時間（10分くらい）は動作がもたつくという弱点があるので、ABC300ではD問題から着手するというチャートを試してみました。このチャートは、D問題が解けずに終わるときのダメージが大きいので、かなりリスキーです。最近はD問題が水色以上になることはほぼないですが、今後長くやっていれば運悪くそれを引かないとも限らないので、次からはやるとしてもC問題からにしたいと思います。
あと、水色精進をしていると、「早解きの感覚」を忘れがちになります。腰を据えてじっくり考えるような精進が多くなるので、簡単な問題をパッと解くような瞬発力が鈍ってしまうのです。
そこで最近は、バーチャルコンテスト（バチャ）を試しています。例えば、本番で手間取ったB問題を10問集めて、30分でどこまで解けるかチャレンジするバチャをやりました（ABC285Bで本番より詰まりました＞＜）。
精進でも1問ずつ時間を計って解いていますが、コンテスト本番では1問ずつのスピードに加えて、頭の切り替えなども問われるので、場数を踏むのは有効かもしれません。

以下、貼るタイミングを逃した精進の記録です。

最近、1500ACを突破しました
灰茶レベルは早く埋めてしまいたいところ……

ちなみに、Streakも継続していて、2023年4月29日時点で178日です。
色別Streakは現在、水色を毎日やっていて、77日くらいです。青色も近いうちに始める予定です。緑色以下は、さすがに全部続けると全く持続可能でなかったので、ABCの緑色以下を埋め終わったのをきっかけに、135日くらいで切りました。精神的にかなり楽になりました。

今後について

ゴールデンウィークは競プロ漬けです！
典型90の★5以降や、EDPCの中盤以降、ARCやAGCなど、やりたいことがたくさんあります！
さすがにここから青まではすんなり行けるとも思っていないので、多少レートが減るとしてもARCに挑戦していきたいと思います。また、5/21に延期になったAGCにもRated参加してみたいです（いずれも日曜日なので、全部に出るのは厳しいですが……）。

そして、5月4日に北海道大学で開催されるHUPCにオンサイト参加予定です！　チーム戦でお役に立てるかはわかりませんが、どうぞよろしくお願いします！

あとは、この半年、競プロに空き時間の大部分を費やしたので、ここからは少しペースを落として、持続可能にしていきたいと思います。まあ、まず当面の目標はABCで6完できるようになることですね。そうすれば、自ずと青色に近づいていくでしょう。半年くらい掛けるつもりで、じっくりやっていきたいと思います。

おわりに

Twitterでは、入水の報告ツイートにたくさんの反響をいただきました。みなさま本当にありがとうございます！　青色目指し頑張ります！
以上、霧しゃまでした！

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