【AtCoder】青色になるまでにやったこととかを水色に落ちる前に書いちゃう

鬼の居ぬ間に洗濯的な．

この記事は Geek-Space Advent Calendar 2020 の13日目の記事として書かれているはずだったのにどうして14日に公開されてるんですか？

13日の記事の公開を期待されていた方へのお詫びを申し上げますとともに，再発防止策を十分に協議して参ります．

お前誰

この記事を読み，参考にされる方のために，私が何者かを記しておきます．

• 高校生

• 組み込み系の企業のバイト

• 算数とパズルは好き

• 数学はよくわからない

  • ただし，特に頻出である二項係数や整数の合同は途中で学んだ

• C, C++ を経て現在は Rust でコンテストに参加している

振り返ってみれば，普段のプログラミングの経験が予想以上に役に立っていました．

レーティング推移

一度青になった時に色変記事を書こうとは思ったのですが，後で食べようと放置したレートは腐ってしまいました．今度はちゃんとレートの青い間に食べてしまおうと思います．

足跡

ここから自分語りが入ります．

「青色になるまで何が必要だったか単刀直入に言え！」という方は，下の方まで飛ばしてください．そこにまとめてあります．

初参加から茶色に至るまで -順調な船出-

「どうもC++は競プロに向いた言語らしいが，私は器用ではないのだから，書きなれたC言語を書こう．」

このような考えのもとに，茶コーダーになるまでの3回のコンテストには，C言語と共に参戦しておりました．この決定は後に簡単に揺るぐこととなるのですが．

プログラミング経験の甲斐もあり，3回連続で4完を果たして茶色コーダーになりました．

また，2回目のコンテストの後，友人の紹介で競プロの Discord コミュニティに参加しました．このコミュニティが，これからの成長の多大なる手助けをしてくださりました．

ここで学んだこと

• Bit全探索

• DP

  この2つは上記のコミュニティで存在を知りました．

茶色から緑色に至るまで -初めての失敗-

ここで，初めてのレート減少に見舞われます．その原因は私が整数の合同に関わる理論を知らなかったこと，競プロに一緒に参加する言語としてCを選択したこと，また当時非常に調子に乗っていたことにあります．

ここでSetなるデータ構造を使えば簡単に解けるC問題が出題されました．しかし，C言語にはそのようなものが標準ライブラリには存在しませんから，書いたことも無いような二分木を15分ほども掛けてこしらえることになります．

その時すでに Python は書けるのですから，臨時的に Python で提出して難を凌げば良いはずです．しかしながら，初参加からの3連続の4完は私を天狗にするには十分でした．

「まあここは時間を掛けてでもC言語で提出してやろう．D問題を解けば，その負債も返されよう．」

何を考えていたのでしょうか．D問題が解けるか解けないかに関わらずここで Python を使うことは絶対的な有利につながったはずです．

結局この後，整数の合同が持つ性質を問うD問題は解くことが出来ず，この回は初の失敗に終わります．この失敗は，私に2つの影響を与えました．

まずそれは私をC++へと駆り立てました．C++ は C の完全なスーパーセットではありませんが，競プロという限られた場面に用いる限りはそのような部分は無視して， C の上位互換と見ることが出来ましょう．

そして，整数の合同(mod)を学ぶきっかけにもなりました．数回に一度は素数で割ったあまりで解を提出させるような問題がありますから，ここで学べたのは大きかったと思いたいです．

共闘する仲間を C++ に変えてからは事は順調に進み，初めての水perfとともに緑色に突入することが出来ました．

ここで学んだこと

• 整数の合同とその性質

• 各種データ構造

• ABCのC問題はたいてい全探索で解ける

  ABC165-C "Many Requirements" の親切心に心から感謝を申し上げますとともに，マジで二度とこのような問題が出題されないことを心より祈っております．

緑色から水色に至るまで -寸止めと超越《トランセンド》-

AGC に初めて参加したのは緑色になってからのことでした．AGC の Rated 対象に緑色が含まれていたのはこの回が最後でしたから，次に Rated な参加者になるのは水色になってからのことです．

私はその AGC で大成功を果たしました．具体的には，今も破られないレート増加幅の最高記録(+220)をここに樹立しました．

調子づいた私はここから追加で水perfを3連続で出し，水レートに王手を掛けます．しかし，ここにきて久しぶりに緑perfを出してしまい，水レートをお預けにされてしまいます．

しかしここで，私にとっての大チャンスが訪れます．最初の5問が簡単で最後の1問が難しい，ある程度未満の実力のプレイヤーにとっては早解きが雌雄を決するようなセットが出題されたのです．

C++ は未だ書きなれない中17分で5完を成し遂げ，ABC における初の青perfと共に水色に至ることと相成りました．

ここで学んだこと

• 二項係数とそれにまつわる諸々の性質

水色から青色に至るまで -年貢の納め時-

「競プロに関係ないプログラミング経験のみで至る限界はせいぜいこれくらいだろう」

水色に到達して最初に漏らした感想がこのようであったのは今でも鮮明に記憶しています．その感想を裏付けるように，ここから一気にレートの増加ペースが落ちてきます．この停滞を機に，各種典型アルゴリズムの学習をはじめました．

共に挑む言語を C++ から Rust へと変更したのもこのタイミングでした．Rust は C++ とおおよそ同時に，普段のプログラミング生活で使用するために学習を始めた言語です．

Rust に十分に慣れたとの判断から Rust を使い始めましたが，私にとってはこれは C++ よりもずっと肌に合う言語でしたので，ここからのパフォーマンス(殊に早解き)に大きく貢献していくことになります．

Rust への乗り換え後は特に順調で，AGC で大成功したり緑perfでそれを無碍にしたりしながら順調にレートを伸ばし，ついには ABC で2回連続の全完を達成します．

青色を達成するきっかけになったコンテストは，AtCoder Library を使用することを想定したACL Beginner Contestでした．典型アルゴリズムへの理解が未だ薄い私にとって不利であることは間違いありませんでしたが，ものは試しと参加することに決めました．

ここで，セグメント木及び遅延セグメント木を使用した問題が出題されます．私のこの時点でのセグメント木の理解はその特徴を小耳に挟んだ程度であり，実際の仕様も実装も何一つ分かりませんでした．

しかし，AtCoder Library 本体とそのドキュメントの助力によりどちらも AC することができ，晴れて青コーダーへの仲間入りを果たしました．

今思えば， Rated のコンテストは1つを除きすべて欠かさず参加したことは，競プロ歴の浅い私には特に効果が高かったのでしょう．青に至るのはしばらく先であると考えていた私にとって，これは最高のサプライズでした．

ここで学んだこと

• 累積和・いもす法

• Union-Find

• 二分探索

• ダイクストラ法等の最短経路を求めるアルゴリズム

• (遅延)セグメント木

青色になるまでにやったことまとめ

• コンテストに欠かさず参加した

  個人的に一番重要だと感じます．

• 以下のアルゴリズム等を学んだ

  bit全探索	動的計画法	整数の合同
  二項係数	累積和・いもす法	Union-Find
  ダイクストラ法	ワーシャル-フロイド法	セグメント木

  私の場合，手札を増やしすぎると頭が回らず却って混乱してしまいそうなので，必要かつ十分なだけ学習しました．

おわりに

黄色を目指してこれからも精進してまいります．黄色になった日には性懲りもなくまたこんな自己満足記事を書きにくることと思います．

メリークリスマス！！