Growth Record of Lettuce Farm

競プロの記録・解説をします

AtCoder 黄色になりました

色変記事 AtCoder

お久しぶりです。れたすです。

今回はこの通り、AtCoder 黄色になったので、そのご報告とか色々をいたします。

前回 (AtCoder 青色・その他) の色変記事

自己紹介とかはこちらをご覧ください。
一言で言うと半年ほどの休止を挟みながらも競プロ歴ちょうど 2 年になる C#er 女子大生らしいです。2 月末～ 3 月頭の 1 ヶ月くらいはずっと引っ越し作業で超多忙でした。

fairy-lettuce.hatenadiary.com

色変報告

早速ですが、黄色達成後更にもっと色変を達成したようなので、更にもっとご報告いたします。

直後に AtCoder 青色になりました！！！！

f:id:fairy_lettuce:20210318012340p:plain

初の下方向への色変です。レート 2002 だったので怖かったのですがやらかしちゃいました。

その後何度か泥沼にハマった後にちゃんと復帰しました。

初の下方向の色変をしたのです、今までとはわけが違うでしょう。黄色下位の維持は大変に思えます。しかし、4 月中に力を付けいわゆる「黄溜まり」から抜け出そうと思います。黄色タッチとか、青黄反復村の住人とは呼ばせません！……たぶん。

AtCoder 黄色になるまでにやったこと

精進記録

2021 年 3 月 29 日、二度目の入黄直後の記録です。

もう青落ちしたくないよ……😭😭😭😭😭😭

f:id:fairy_lettuce:20210329005759p:plain

f:id:fairy_lettuce:20210329005809p:plain

f:id:fairy_lettuce:20210329005814p:plain

f:id:fairy_lettuce:20210329005825p:plain

本人も気付かないうちに橙精進になっていました。え？

まあ精進ゼロでもコンテストに出てれば自然と Rated Point Sum は増えますからね。精進レートなんかよりも高難易度の AC 数を見ましょう (ところで、青になった時から増えた AC 数、ほとんど青・黄 diff ですよね……？？)。

身につけたアルゴリズム・データ構造

前回との差分のみ。

何の迷いもなく書ける・使えるようになった

  • 大体の DP
    正直なところ、DP に強くなったのが黄色になるための実力に一番貢献したと思っています。というか今回の記事それ以外ほとんど無いです。
    青に入った直後に基礎的な DP でやらかしたので、その週に EDPC を 5 つ以外埋めたのですが、そのおかげで DP の勘が非常に冴え渡るようになりました。更に、言語化しにくいのですが、DP を伸ばしたら他の能力も一緒についてきた感覚があります。なんででしょうね。すごい。EDPC は高度典型の基礎が詰まっているのでしょうか？
    とりあえず EDPC 残りと TDPC も埋めなきゃ……。

  • 幾何ライブラリ
    ちゃんと整備しました。幾何ライブラリ無いとたまに幾何問題が刺さる……。
    直線・円のみですがこれだけでも AtCoder だけなら十分だと思います。ICPC だとちょっと心もとない気もしますが、ICPC は C# では出ないので……。Verify は Yakiniku Optimization Problem と Enclose All のみで、AOJ は使っていません1。

  • グラフライブラリ
    最短路問題とか全方位木 DP とか色々ライブラリ化して貼るだけにしました。いわゆるグラフ構造体っていうやつです。みんな大好き AddEdge とかあります。ac-library の最大流・最小費用流のアレみたいな感覚でいろんなグラフアルゴリズムを使えます。すごい。
    まあでも、よく使う Dijkstra とかってちょっとだけコードをいじったものが問われることが多いですし、辺を陽に持たないなら使いづらいのであまり役立ってない感はあります。まあ BFS/DFS とか Dijkstra くらいなら定型文ですし、慣れてれば実装も数分かかる程度ですからね。

調べたら使える・ちょっと苦労するけど書ける程度

  • Trie
    ライブラリ化したけどあまり使ってないです。Binary Trie も作らなきゃ。

  • 燃やす埋めるとかのフロー系アルゴリズム
    理解はしたつもりですがまだまだ修練が足りません。Educational MaxFlow/MinCostFlow Contest が待ち望まれます。

あまり理解していない

たくさん増えました。追いきれてません。

……こう見ると、青の間は DP 以外の典型をそんなに勉強していない気がします。FAKE な気がします。

まあある程度の問題に立ち向かうだけの手段は身についているという自負はあります。教科書の勉強がだいたい終わったから次は高度典型とか思考パターンの反復とかを勉強する、そういう段階に入ったということでしょうか？

実際、「これは解説記事にして忘れないようにしよう！」と思えるようなやらかし方は格段に減りましたし、これからはどんどん貪欲に問題を解いて難しい問題への耐性を付けなければならない気がしています。

青のときから変わったこと

箇条書きです。

  • Streak を気にしないようにした
    今年 1 月中旬を最後に、Streak をつなげるのをやめました。
    f:id:fairy_lettuce:20210329021646p:plain
    確かに毎日競プロに触れることがなくなり、次第に FAKE になっている気がします。ですが結局約半分またはそれ以上の頻度で Streak をつなげるためにやるだけ問題を解いていたため、「とにかくやってモチベを維持する」以外の意義を見出せていないでいました。義務感を感じてしんどくなっていたのもあります。
    あくまで楽しいからやってるのであって、義務感に駆られてする競プロは Rated だけでも十分だと思うようになりました。
    この Streak を気にしない方針は主に evima さんの Twitter やマシュマロ回答に影響されたものです。今後は自明問題で繋ぐ Streak なんかではなく、高難易度の思考力を鍛える精進を重視しようと思います。

  • それ抜きでも FAKE になった
    2 月以降ずっと引っ越しで忙しかったんです……ごめんなさい……。

  • Lockout をたくさんするようになった
    kenkoooo さんなどと Lockout を AtCoder Problems 上のバチャでやるようになりました。特に kenkoooo さんとの Lockout は引っ越しで多忙だった時期以外は週例行事になっています。
    Lockout で身につく実力はほとんどないと言ってもいいのでお楽しみ要素です。しかし私の場合難しい問題をひたすら考える練習をしないといけないと思っているので、かなり良い刺激になっています。特に kenkoooo さんはたくさんの問題を解いていて高難易度力も十分ある方なのでとても手強いです。
    毎週の対戦 (そして Lockout のプラットフォームである AtCoder Problems の提供・開発)、いつもありがとうございます！！！

  • 典型で落とす確率が減った
    ABC でめちゃくちゃ冷えることが滅多になくなりました。青の最初の頃は ARC のほうが温まれていたのですが、ABC で黄パフォ上位～橙パフォがたくさん出るようになって以降 ARC よりも ABC のほうが成績が良いことが増えてきました。
    これは黄色下位の人にとってよく見られる現象な気がしています[要出典]。
    f:id:fairy_lettuce:20210402010343p:plain
    ちなみにこうなりました。青の頃とは大違いで ABC でレートを荒稼ぎです。

  • 高難易度考察時に「何も分からない」が減った
    ここ最近、私の中でパッと見て一瞬で解法が分かる問題と何も分からない問題の二極化が激しいと話題になっています。私はどちらかというと高難易度の問題を解くことよりは早解きでレートを稼ぐ人だったので、これは解ける難易度の上界を引き上げない限り頭打ちになるというしるしでもあります。
    しかし、最近では何も分からないながらもひたすら実験したり考えたりしていくと、いわゆる「重要な観察」が得られる確率が高くなってきた気がしてきました。これは青中上位の頃までは無かった感覚です。
    当然「重要な観察」の一部だけ分かっても AC はできないため、そこから更に答えに近づく必要があるのですが、解法ガチャの当たり率が上がったというのは勘がよくなったということだと思います。
    ここからもうちょっと頑張って高難易度を通す練習をしたら、緑→水のときや水→青・黄のときのような、大きなブレイクスルーが訪れる予感がしています。それがいつ訪れるのかは全く分かりません。もしかすると訪れないかもしれません。しかしそのときまでずっと精進を続けるほかないと考えています。まだまだ私の競技プログラミングはこれからなようです。

ちなみに私が早解き型かどうかは諸説あるようです。ABC で微妙に遅くても全完しているときはたくさん解くタイプと数えられていそう。

おわりに

内容が前回に比べるとかなり薄い気がします2。基本的に「教科書」範囲を終えて、これからは Ad-hoc な問題の非自明な考察の仕方や高度典型を学び始める時期がやってきたのかもしれません。明確な壁が目の前に立ちはだかっているのを感じていると同時に、自分の成長できた理由が「特定のデータ構造やアルゴリズムなどをたくさん勉強した」ではなく「たくさん精進した」に切り替わりつつあるのも感じています。自分が成長できた理由は精一杯言語化したつもりですが、それでも前回の記事より内容が少ないのはこのためかもしれません。

私はどうやら天才型ではなく、問題の考察をたくさん重ねてパターンマッチングする、いわば人力機械学習型であるようです3。なので一度知識が付けばそれ以降はとにかく質の高い (パターンマッチングを増補するような) 精進の量が大切な気がしています。よく考えたら高校生の頃の数学もそんな感じの勉強をしていたような。

さて、前回の青色になりましたの記事で、2021 年上半期の目標は黄色と言い、その後目標を 3 月までに修正しました。結局 3 月に黄色になり、青に落ちたもののまた復帰でき、その目標は果たせました。

短期的な目標はこれで終わりですが、今年中の長期的目標に「AtCoder 橙」というものがあります。

正直、黄色までと違って本当に橙になれるビジョンが見えません。それどころか、2200 になることすらすごく遠く感じます。今まで以上に先が見えず、苦しい戦いになるでしょう。

ある程度の焦りを感じたいので、今回も短期的目標を設定します。次の目標は 2021 年 8 月までに 2200 (AtCoder 二段) になる、とします。時期設定は来年度の ICPC を見据えてのことです。もちろん間に合うならば橙になって参加したいですが……。

現状黄パフォを出せればうれしいという認識でしたが、これからは黄パフォを出すだけで喜んでいては成長になりません。今後は橙コーダーを目指す黄色という自覚をしっかり持って、橙パフォ以外は冷えというくらいの気持ちでコンテスト・普段の精進に臨もうと思っています。

ARC でもきちんと黄 diff を通しあわよくば橙 diff も通す。AGC では手も足も出ない問題にタックルし続ける体力を持つ。このふたつが出来るような立派な黄色コーダーになりたいです4。

ということで、れたす先生の次回作「AtCoder 橙色になりました」にご期待ください！

  1. AOJ の C# バージョンが古代遺跡なので、ICPC 練で C++ 使うとき以外触りたくないのです……。↩

  2. 青に滞在していた時期のほとんどが成長期だったのもありますが……。↩

  3. 言ってて恥ずかしくなってきました。↩

  4. 言ってて恥ずかしくなってきました。決意表明ってこんなもんですけど。↩