Growth Record of Lettuce Farm

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

AtCoder 青 / Codeforces 紫 / Topcoder 黄 になりました

色変記事 AtCoder Codeforces Topcoder

この記事は、色変記事 Advent Calendar 2020 の12月9日公開の記事です。

色変記事アドベントカレンダー、なるものの募集を見ました。

この恐ろしいアドベントカレンダーを見てしまった私。そういえば、AtCoder 青も Codeforces 紫も、近かったような……あれ、Topcoder も黄になれるんじゃ？

f:id:fairy_lettuce:20201105125829p:plain:w320f:id:fairy_lettuce:20201105125840p:plain:w320f:id:fairy_lettuce:20201105125850p:plain:w320

ということで、参加してみました。完全にノリですが、Topcoder はともかく AtCoder と Codeforces はずっと色変しないまま膠着していたので、これを期に色変してやろうと考えました。

(達成できたら)恐らく前代未聞の、3 コンテストサイト同時の色変記事になります。

前回 (AtCoder 水色) の色変記事

自己紹介とかはこちらをご覧ください。
一言で言うと昨年 3 月に競プロを始め、昨年 10 月～今年 3 月までの休止を経て今まで競プロをしています。C# 使い。女子大生らしい。

fairy-lettuce.hatenadiary.com

色変報告

早速ですが、色変を達成できたのかご報告いたします。

AtCoder 青に……

なりました！！！！！！！！！！！！！！

Codeforces 紫に……

なりました！！！！！！！！！

Topcoder 黄に……

なれませんでした！！！！！

いや、めっちゃダサいですけど、ひとつだけ言い訳させてください……。ここ 1 ヶ月の SRM かなり踏んだり蹴ったりでした。

  • Rookie SRM
    問題が最悪クラスの難読、それで下らない場合分けミスで Hard システス落ちし -164。
  • SRM 794 だったもの
    まさかの延期。ただでさえ前回冷えたのに残り Rated が 1 回のみになってしまい……。
  • SRM 794 (ほんもの)
    青～黄色下位にとってはちょっと実装が重い Easy の早解き回でしたが普通に早解きミスって -58。

助けて。というか冷えた回はまあ単純に自分が悪いと言えば済む話ですけれど Rated 消失はどうしようもなくないですか……。

ということで、Topcoder 黄はじっくり再チャレンジします。1 月までに黄色になるのをとりあえず目標にします。

AtCoder 青になるまでにやったこと

AtCoder 水になったときにやったので、青になるまでにやったこともやります。

今回はまあ 3 コンテストサイトの色変記事ということで画像がたくさんあります。

精進記録

2020 年 12 月 06 日、入青直後の記録です。

AtCoder

f:id:fairy_lettuce:20201206130424p:plain:h500 f:id:fairy_lettuce:20201206130452p:plain f:id:fairy_lettuce:20201206130542p:plain f:id:fairy_lettuce:20201206130501p:plain:h700

適正難易度付近の埋め具合が少ないです。精進が足りないですね……。

Codeforces

f:id:fairy_lettuce:20201206130603p:plain f:id:fairy_lettuce:20201206130613p:plain:h700

こどふぉは冷えても爆発すればきちんと温まるので好きです。
薄橙になれなかったのは悔しい……。

Topcoder

f:id:fairy_lettuce:20201206130623p:plain

Topcoder、何？

yukicoder

f:id:fairy_lettuce:20201206132142p:plain

Streak 切らしたのは悲しい事件でした。それと、簡単な問題ばかりやっているので、中～高難易度を埋めないといけないです。

yukicoder の問題は悪く言えば当たり外れが結構大きいのですが、誰でも Writer / Tester の経験をできること、「ゆるふわ」に問題を解いていても怒られないことや、Rated の枠に囚われない問題を出題できること、Unrated なのでコンテストの動き方の研究ができることなどが魅力だと思います。なので出たい時に出られる Unrated コンテストを開催していて、(全埋めを目的とするよりも) 面白そうな問題をピックして解く問題集としても使えるコンテストサイト、と捉えたほうがいいかもしれません。

ちなみに、今日 12 月 9 日出題の yukicoder Advent Calendar Contest の問題は私の出題ですので、皆さん是非解いてみて下さい！
問題リンク→ https://yukicoder.me/problems/no/1312

その他

f:id:fairy_lettuce:20201206131244p:plain

JOI 埋めはまだまだこれからです。

おまけ (Online Math Contest)

f:id:fairy_lettuce:20201206131335p:plain

Topcoder 黄 の代わりに OMC 緑になりました！で 3 コンテストサイトの色変を主張しても良かったのですが、OMC のレートはまだ収束していないし、どう考えても競プロではなく数学なのでおまけで言及する程度にしておきます。

ちなみに、全てのコンテストサイトでなんと下方向の色変を未経験です。これだけパフォが上下しているのに……。
これからも早解きできる難易度帯を増やし、安定感を身につけ下方向の色変を経験しないようにしていきたいです。

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

データ構造やアルゴリズムなどで水色になりたてのときから学んだものを列挙していきます。

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

  • Deque
    • リングバッファによるランダムアクセス O(1) のものを実装しました。これ実装とても簡単ですね。
  • Bellman-Ford 法 / Kruskal 法 / Warshall-Floyd 法
    • 最近書いてない気がするけど、まあ出たら流石に書けるでしょう……。
  • Union-Find
    • 今ならゼロからコードを書けます。この前の SRM 794 で書きました。
  • 半分全列挙
    • たくさん勉強しました。
  • (一次元) 座圧
    • LINQ で簡潔に書く座圧が好きです。二次元座圧はあまり書いたこと無いので勉強したいです。
  • Segment Tree
    • 抽象化してライブラリにしました。Lazy Segment Tree は ac-library-cs のものを借りて使っています(そのうち自分で実装したいです)。
  • Nim / Grundy 数
    • ゲーム系の問題は苦手なので集中して勉強しました。今ではゲーム系の問題も実力相応の問題程度ならちゃんと通せると思います。
  • SWAG (Sliding Window Aggregation)
    • 財宝を高速化する際にスライド最小値と一緒に勉強しました。実装も楽だし、とても頭のいいデータ構造だと思います。
  • 答えを決め打ちする二分探索
    • これが見えるようになればひとつ上の難易度を解けるようになる気がします。
  • 高速素因数分解 (Miller-Rabin 法および Pollard's ρ 法)
    • yosupo judge でライブラリ整備しました。たまに貼って殴っています。
  • CRT (中国人剰余定理)
  • 平衡二分探索木
    • AVL 木で実装しました。爆速です。
  • OEIS / WolframAlpha
    • 賛否両論あると思いますが、私は使えるコンテストなら使っていいと思います。これらのツールを使う力も競プロ力の一種だと思っています。
  • ランダムチェッカー
    • どうしても WA の原因が分からない場合で、愚直解が簡単に書けるときに非常に役立ちます。特定のアルゴリズム・データ構造というわけではありませんが、ランダムチェッカーは一定以上の高難易度を攻略するのには必須の技術だと思います。

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

  • ダブリング・LCA
    • 多分書けるとは思いますが、あれ以来書くタイミングが無かったので勉強できていません。まずいですね
  • 桁 DP
    • 苦手なままです。頭混乱する……。
  • フロー (最大流・最小費用流)
    • ACL のおかげで勉強しました。使いこなせてはいませんが、出たらフローを疑うことができるくらいにはなりました。
  • 幾何ライブラリ全般
    • ABC157-F Yakiniku Optimization Problem を通した際、幾何ライブラリが全く育っていないことに気づきました。このときはフルスクラッチで書いてなんとか (バチャの時間内では無理でしたが) 通しました。しかし、幾何は ICPC 頻出です。普段の主戦力である C# はもちろん ICPC で出る用に C++ でもライブラリを整備したいです。
  • 強連結成分分解
    • DAG が肝な問題に出くわせば発想として出てくる程度にはなりました。いつも ac-library-cs の実装を貼っています。
  • 2-SAT
    • いつも ac-library-cs の実装を(略)
  • 文字列アルゴリズム全般
    • 最近の AtCoder の傾向的にあまり勉強しなくても青色までは食らいつける感じがします。複雑な文字列アルゴリズムを要求する問題、最近の寒色 diff 問題であまり見ていない気がします。勉強しないといけませんね。
  • 形式的冪級数 (FPS)
    • これを言うのは二度目ですが maspy さんの解説 が非常に分かりやすかったです。考察の一助としての FPS の考え方を綺麗に理解できます。

あまり理解していない

  • HL 分解
    • 何をしたいかは理解しているので、適当に問題解いて実装したいです。
  • Mo's Algorithm
  • Convex Hull Trick
  • 高速ゼータ変換・高速アダマール変換
    • この前 yukicoder に高速アダマール変換が出題され、何も分かりませんでした。反省。
  • Wavelet Matrix
  • Sparse Table

全部列挙するのは難しいし、抜けは多いと思います。まあなんとなくで覚えている典型も水色の時からすると増えたので。
典型力は青コーダー平均程度だと思いますが、暖色に必要な水準には達していないと思うので、暖色になるまでにたくさん覚えて引き出しを増やしたいです。

その他にやったこと

バチャ

これはまあ、いつの時代も変わらないですね。
11 月は正直 Rated が異様に多かった月でしたし、アドカレ参加表明以降に不参加だった 3 大コンテストの Rated も 3 回のみ (ABC182・CF Round #688 (Div. 2)・CGR 12) だったので、バチャはあまりしていませんでしたが……。
水色の間にしたバチャ (AtCoder で出れなかった回を翌日に追ったバチャ以外) は ABC のバチャが 8 回 (ABC151～158) とこどふぉバチャが 3 回です。バチャの回数だけ見るとド FAKE ですね……。

参考に、Codeforces Anytime の記録も貼っておきます。バチャレートが本家レートよりも低いのなかなか珍しいかもしれません。

f:id:fairy_lettuce:20201206133447p:plain

Upsolve をするようにした

今まで解き直しというものをあまり熱心にはしていませんでしたが、きちんとするようにしました。今までがやらなさすぎだったのですが、Google Keep に問題を記録していくことで管理するようにしてきちんと消化するようにしました。
適正難易度の問題数が非常に多いので、正直寒色のうちは問題を解く上での吸収効率を最大化することはあまり意識しなくてもいいかもしれません。しかし、レートを短期的に上げる観点からも、長期的に成長する観点からも、Upsolve によって吸収効率を寒色のうちに上げておくことは大切だと思います。

解説記事執筆

解説記事を書くことにしました。およそ 1 か月続いています。いまのところ、解説を書く対象は

  • 難しい問題が解けたとき
  • 本番やバチャでしてはならない失敗をしたとき (反省文・備忘録として)

です。

一度やったことを忘れずに最大限吸収する、という目的で解説記事を書いているため、今は時間をかけて書いています (一記事あたり簡単なものは 30 分、難しいものだと約 1～2 時間程度かかっています)。そのため、難しい問題であっても解説記事にすることで得られるものが少ないと判断した場合は書かないことが多いです。逆に失敗をしたときの反省を兼ねた解説記事は可能な限り書くようにしています。
とりあえず、最低でも暖色になるまでは解説記事の執筆は続ける予定です。ゆくゆくは分かりやすく簡潔な解説記事をさらっと書けるようになりたいです。

なお、時間がかかるのでその間に別の問題を解いて精進すればいいのではないかと思うこともあるのですが、反省文としての問題解説記事は非常に効果的に Upsolve をする手段であると思います。後から見返すこともできますからね。

本を買った

蟻本とけんちょん本を買いました。

たまに読んだり、分からないデータ構造やアルゴリズムがあったときの辞書としたりして使っています。そろそろ全部の内容をまとめて勉強しないといけない気もします。

その他競プロをする上で意識したこと

競プロの戦い方

まあ寒色コーダーで戦い方なんて考えてる暇があればとにかくコンテストに出たほうが近道だと思いますが……。

ありとあらゆる先人の競プロerが仰っている通り、競プロ力には 2 種類あります。

  • 簡単めな問題を早く的確に解く、早解き力
  • 難しめな問題をじっくり詰める、高難易度力

前者はパフォの下限を、後者はパフォの上限をそれぞれ引き上げてくれる力であることはたくさんの競プロerも言及していることであり、疑いようもない事実だと思います。

私は自分自身、自分のレートから相対的に見て低～中難易度ほど (およそ緑～水下位 diff 相当の問題) の早解きが強みだと思っています。たまーに水 diff でもやっちゃいけない類の変なやらかしをするのは内緒ですが、自分のレートより 1 色以上下 (緑パフォ以下) を出す頻度は非常に少ないです。
しかし、以前より高難易度を本番で通す体力があまり無かったので、今回は高難易度力を重点的に強くしようと思いました。難しい問題でもめげずにじっくりと考察する機会が以前よりも増えたのではないでしょうか。

結果、高難易度力はそこそこ上がりました。1 か月前は青 diff・黄 diff を通せる確率は体感でそれぞれ 4 割・0.5 割程度でしたが、今なら 7 割・2 割程度の確率で通せると思います。自分でもどうして高難易度耐性が付いたのかは分かりませんが、この 1 か月で急激に高難易度を通せるようになりました。びっくり。

高難易度力が上がったおかげかどうかは分かりませんが、最近の水 diff 早解きしないと高パフォーマンスが出ない ABC よりも青～黄 diff で決着が付きがちな ARC の方が得意になりました。ちょっと前までは ABC の 5 完早解きで青パフォが出ていたので、昔は ABC の方が青パフォを出せる割合が高かったのですが……。
今では簡単枠がある程度あって、難易度がそこそこの問題もあるコンテストが一番安定して戦えます。ARC や CF Div. 2 などです。

ABC も当然あれば出ますけど、ABC よりたくさん ARC を下さい！！

メンタルの持ち方

前回も似たようなことを書いた気がしますが、今回も書きます。

アドカレに参加表明してからこどふぉに出る頻度がとても多くなって、その瞬間にこどふぉは伸びるようになったのであまり気になりませんでした。しかし、AtCoder はそう上手くいきませんでした。ABC バチャでは橙パフォを出すなど調子も良く、同時期にこどふぉでは濃橙相当のパフォを何度も取って爆発的に伸びていたにもかかわらず本番では失敗することも多かったので、メンタル的にはあまり良くない状況が続きました。緑上位の頃は実力もレートも伸び悩んでいたので、それとは違った種類の苦しさでした。

今回は別に伸び悩んでいるわけでもないので、悪いパフォが出てもあまり気にしないように意識しました。むしろこどふぉが上手くいきすぎていたので、こどふぉで上手くいくんだから今たくさん競プロをすれば絶対に伸びるはずだと考えもしました。結果 AtCoder でも黄パフォを連発できるようになって実力相応のレートに近付いていると感じます。
実力が伸びていると感じるときはメンタルなんて気にせずとにかく精進すればレートはそのうち付いてくる、と考えることは大切です。

アドベントカレンダーに参加しての感想

色変直前だし、どうせならということで参加しちゃいました。当初は 12/05 に出す予定でしたが、Topcoder SRM が同日深夜 1 時からあるということでちょっとずらし、12/09 に変更しました。結局そのおかげで AtCoder の色変が間に合った (Topcoder は Rated に全部出た上で無理だったのですが……) のですが……。サクッと色変を決めちゃいたかったのに、思った以上に時間がかかってしまいました。

今回色変記事を実現するために、きちんと色変を 1 か月以内に達成しようと意識し、可能な限りコンテストやバチャから吸収することを心がけました。ちゃんと精進している方には FAKE と思われる程度しか精進していませんが、1 か月の間はずっと競プロのことを考えていましたし、今までの競プロ生活の中で最も真摯に競プロそのものに向き合った 1 か月になりました。色変達成以上に、真剣に取り組むきっかけを与えてくれた色変記事アドカレ、および企画者であるどきんさんには本当に感謝しても感謝しきれないです。

おわりに

結局 Topcoder は青のままなので、AtCoder 青・Codeforces 紫・Topcoder 青という 3 大コンテストサイトにおける暖色一歩手前を制覇した形になります。ですが始めた頃は青色なんて遠い存在だと思っていたし、周りの水コーダーがみんな青になっていたことに焦りを抱いて競プロ休止期間から復帰したので、感慨深いです。
それと、水色になるには 16 か月 (休止期間を除き 10 か月) かかりましたが、青になるには 5 か月程度しかかかりませんでした。成長の速度が目に見えて上がっています。いいことですね。

しかし、水色になりました記事では橙・赤くらいになりたいという目標を掲げていて、青色はその目先の目標としていました。当然ここで歩みを止めることはないです。目先の目標が青色から黄色に変わっただけです。まだまだ頑張ります。

2021 年上半期の目標は AtCoder 黄色です！更に ICPC もチーム全員で黄色になって国内予選突破を目指したいです。

上位層への道は非常に遠いですが、ARC なら黄パフォを半分程度の確率で出せるようになっているので黄色は案外手に届く距離にあるのではないかと思い始めました。こうなれば、青コーダーにはなりたてではありますが、もはや青パフォは成功とはいえないと思い始めています。黄パフォを当然のように出すことはもちろんとして、橙パフォを出せるようになりたいです。

それでは今回はこの辺りで筆を置くことにします。ありがとうございました。「AtCoder 黄色になりました」にご期待ください。