見出し画像

【入青】AtCoder青色になりました！【色変】

霧しゃま

ようこそここへ！　競プロerの霧しゃまです！
昨年11月からAtCoderにハマってそろそろ一年が経とうとするところですが、去る2023年8月26日、青色になることができました。
というわけで恒例の振り返り記事です！
これから青色を目指されるみなさまの参考になれば幸いです！

ざっくりプロフィール

ハンドルネーム：霧しゃま（AtCoderId: Kirishima）
アイコンの鳥さん：ヒシクイ（ガンカモ科の水鳥）
インターネット歴：20年以上、WindowsMe世代
プログラミング歴：本格的に始めたのは2020年初頭から
AtCoder歴：2022年11月から、初RatedはABC276
学歴職歴：実は旧帝卒（非情報の理系）であり、業プロer
使用言語：なんだかんだ手に馴染んで乗り換えられないC++
その他経験言語：Python、Javaなど
入門書を積んでいる言語：Rust、Haskell、Erlang、CommonLispなど
好きなゲーム：海腹川背、風来のシレンなど

忙しい人向けのまとめ

・青色達成ありがとう！　黄色も目指し頑張ります！
・安定性に自信あり！　地道にレートを積み重ねました！
・実は中の人は、俳句を嗜む元馬の骨です！

入水までのあらすじ

2022年11月にAtCoderで競技プログラミングを始めた霧しゃまは、2023年4月末に水コーダーになりました。
緑コーダーになったときはAtCoder Beginner Contest（以下ABC、全8問）でやっと5完に手が届く程度でしたが、過去問演習を積み重ねて5完を安定させた頃に入水しました。
そのときの様子はコチラ！

今回はまず、2023年5月からの動きを振り返ってみます。

【５月】飛躍のために

  • ABC301：96分で5完、4ペナ

  • ABC302：95分で7完（自己ベスト更新）

  • AGC062：41分で1完（記念rated）

  • ABC303：68分で5完

色変した直後は転落するということもあり得るわけで、非常にプレッシャーを感じていました。しかし、ゴールデンウィークで遅延セグメント木や全方位木DPなど大物を手懐け、オンサイトデビューを果たした霧しゃまの勢いは止まりません。ABC302では制限時間ギリギリで7完を決め、過去最高の高揚感を味わいました。パフォーマンスは黄色に近い1979で、これも当時の最高記録でした。
念願だったAGCのrated参加はほぼレート変動のない退屈な結果に終わってしまいましたが、後のリベンジを誓いました。
ABCの水色レベルの問題を埋め終わったのもこの頃です。後半は解説ACも多くなり、単純に時間が掛かることもあって1日に2問程度が関の山でしたが、それでも毎日続けている効果は確かにあったと思っています。

【６月】Unrated、再び

  • ABC304：35分で5完（ジャッジ詰まりによりUnrated）

  • ABC305：82分で5完、4ペナ（冷え）

  • AHC020：4.426億点で325位（ヒューリスティック入茶）

  • ABC306：81分で6完、2ペナ（Unrated）

  • ABC307：66分で4完（C落とし、耐え）

6月は、初めて月間レートがマイナスとなった月でした。入水前の3月もかなり乱れていましたが、6月は実際、リアルも忙しかった時期であり、コンディションも良くなかったと思います。少し自信を失いかけましたが、やはりというか強靭な心こそが最強の武器なので、メンタルは崩さないように自分を鼓舞しました。
一番何が厳しかったかと言えば、Unratedです。これで良かった回が2回潰れているので、レート的には最悪でした。しかし、ここで比較的良い成績を出せていたからこそ、自信を失わずに済んだとも言えるでしょう。
この頃、ABCの青色レベルの問題を埋め始めました。新たなテクニックを習得するというより、既存のテクニックの組み合わせや応用で解く問題が多く、毎日学ぶことが多いです。
AHCにも出てみました。まだ2回目には参加できていませんが、気が向いたらまた参加したいと思います。
そのときの様子はコチラ！

【７月】一歩ずつ、前へ

  • ABC308：50分で6完、1ペナ

  • ABC309：80分で6完、2ペナ

  • ABC310：57分で5完

  • ABC311：54分で5完

  • ABC312：94分で6完、4ペナ（A~F）

7月になってからは、毎回6完が出せるかどうかが焦点でした。制限時間が100分あって、だいたい50分くらいで5完できるので、そこから50分でF問題に挑戦するという流れです。
しかしF問題は大抵青色レベル、場合によっては黄色レベルにもなる難問揃いです。何度も解けそうで解けない思いをしました。結局、青色にはなりましたが、F問題は相変わらず難しいので、まだまだ伸びしろがあると思っています。
ただ、パフォーマンスは毎回青色レベルが出ていて、レートは1550を超えました。このまま近いうちに入青するという楽観もありましたが……。

【８月】滑落、そして入青

  • ABC313：16分で3完、1ペナ（予選仕様、冷え）

  • ABC314：28分で4完、1ペナ（冷え）

  • AGC064：158分で2完、8ペナ（やや回復）

  • ABC315：85分で6完、2ペナ（王手）

  • ABC317：84分で6完（黄パフォで入青！）

8月の初旬に体調を崩し、その影響は2週間にも及びました。コンテストでは水色パフォーマンスを保ったものの2連敗し、入青が遠のきます。
AGC064はそんな中で、捨て鉢になって出場しました。しかしここは幸いにもB問題を通すことができ（この上なく泥臭い方法でしたが）、レートを少し回復することになりました。
その次のABC315では、難しかったと噂されるD問題を落ち着いて通し、F問題も通して6完を達成したことで、ABC302に次ぐパフォーマンスを出すことができました。レートは1584となり、入青が手の届く範囲まで近づきます。
そしてABC317（316は欠番）です。やや忙しい日でしたが、なんとしても今月中に入青したいという思いで突撃しました。その結果は、複雑な桁DPであるF問題を通して大成功、自己ベストの黄色レベルのパフォーマンスを出し、文句なしの入青を果たしたのでした。

【Q1】どんなハードウェアを使っている？

ここからは、色変記事特有のインタビューです。
競技に取り組む姿勢は入水したときとあまり変わらないので、前回までの記事もぜひどうぞ。今回はむしろ、中の人の内側に迫っていきたいと思います。

まずは、こだわりを持っている方も多いと思われるハードウェアの話から。霧しゃまが使っているPCは、HP製の「Victus 16 (AMD) アドバンスモデルG2」です。スペックは次のような感じです。

  • CPU：AMD Ryzen 7 6800H with Radeon Graphics(3.20 GHz)

  • RAM：16.0 GB

  • GPU：GeForce RTX 3050（Ti, Laptop GPU）

比較的新しいモデルの、カジュアルなゲーミングPCです。キーボードを光らせる機能などがあります。Officeやマウスなども付けて16万円くらいで買えたので、非常にコスパの良い買い物でした。競プロ用途としてもスペックはやや過剰なくらいあるので、とても捗っています。
キーボードは内臓のものです。ディスプレイを外付けして、2 画面でやっています。
唯一問題があるとすれば、自宅のインターネット回線が弱いことです。そこにはお金を掛けていないので……。

それにしてもデスクが広くないので、PC本体とディスプレイを置いたら、もう考察用のノートを開いたり、本を置いたりするスペースがありません。これは、考察をPC上のExcelなどで行うことで対応しています。また、どうしても図を手書きしたいときのために、メモ用紙を手元に用意しています。

【Q2】精進量はどのくらい？

自分の強みは不調時にも極端にパフォーマンスを落とすことがない「安定性」にあると考えています。その秘訣として考えられるものはいくつかありますが、とりあえず最初に挙げるべきは「精進量」だと思います。現時点での精進の記録を示します。

2000ACを突破したその日でした（入水からは約500問）
このほか、典型90の★5や、JOIの難易度5以下などを埋めています

ずっと下の色から順番に埋めるスタイルでやってきました。そのほうが、確実に理解の範囲を広げることができると考えているからです。確かに、難しい問題に挑戦して格闘して、場合によっては解けたりするような体験があったほうが良いという意見も理解しますが、実際には1色上くらいでも、選り好みせず埋めるようにすれば普通にチャレンジングな問題に出会えるので、必ずしもそれより難しい問題に挑戦する必要はないと思っています。

そもそも青色レベルを初見で1問通すために平均して1時間程度は掛かってしまうので、最近は1日1問ペースになっています。ただ、これだといつまでも出会えない知識が出てくるので、コンテストで見かけたアルゴリズムなどはメモしておいて、時間のあるときに適宜学ぶようにしています。

入水～入青の期間で習得した技術を列挙してみます。やった順です。

  • 遅延セグメント木

  • 全方位木DP

  • ベルマンフォード法

  • 幾何（線分交差判定、線分と点の位置関係など）

  • 約数系包除原理とメビウス関数

  • 凸包

  • Mo's Algorithm

  • 中国剰余定理

  • 行列累乗

  • 2-SAT

この中では遅延セグメント木を使う場面が多かったと思います。そのほかは基本的に昔の過去問を解くためか、最新のコンテストで出題されてからの後追いで習得しているので、まだあまり本番で役立ったことがありません。

あと、これらとは別にModint構造体を導入しました。使いどころが多いため導入には慎重になっていましたが、いざ使ってみると、もう以前には戻れないと思うほどコーディングが楽になりました。
そもそもModint構造体は、単に便利というだけでなく、いくつかのライブラリを使うときに必須級の寄与をします。具体的にはセグメント木や行列累乗などです。C++ではテンプレートの機能を使えば、普通の整数型を持たせる場合と変わらない使用感でmodに対応できます。とても楽です。

とりあえず、どんな分野も選り好みすることなく、地道に一つずつ理解していけば、パフォーマンスも安定してくると思います。解いた問題のことは、そのエッセンスだけでも覚えておきましょう。本番で「似たような問題を解いたことがある」と思えたら、しめたものです。感覚的な話ではありますが、これが「典型」を意識することなのだと思います。

それにしても、青になってからは「得意分野」を意識する頃だと思います。青以上の方々を観察すると、それぞれ何かしらの得意なもの、特別に準備しているものがあって、セットとの嚙み合わせ次第でレートより大幅に高いパフォーマンスを叩き出しているように見えます。
より具体的に言えば、ABCのカンストである2400パフォーマンスを出すための武器が必要になるというわけです。それは、F問題までの早解きかもしれませんし、G～Ex問題を倒して7完以上を得るための幅広い知識・情報源と深い理解かもしれません。
これまでは「守り」を重視してきましたが、今後は「攻め」の強みを得る必要があります。入青の決め手になった桁DPも、得意というか好きなアルゴリズムの一つです（一時期、桁DPに見える問題を何でも桁DPにして慣れ親しみました）が、実装はかなり時間が掛かってしまうので、もっと速度を意識していく必要があるでしょう。

これまでの比でない、厳しい戦いになるとは思いますが、まずは引き続き、地道に精進を続けていきたいと思います。

【Q3】ARCやAGCには出ないの？

今は、仕事との両立を考えると土曜・日曜に両方コンテストに出るのは大変なので（特に日曜の夜が厳しいです）、ABCに大半のリソースを投入しています。ARCの序盤の問題はたまの暇つぶしに取り組んでいますが、本格的な対策は全くしていません。
というか、ここまで来たらまずはABCメインで黄色になってしまって、それから考えようかと思っています。他の趣味や人生のことなどもありますが、黄色まではやってみるつもりでいます。

【Q4】水鳥→青い鳥と来たら、次は？

これはX(Twitter)のプロフィールの話ですが、霧しゃまは水色になってから「水鳥」を、青色になってからは「青い鳥」を名乗っています。
そして次はキイロイトリ……と考えましたが、だんだん小型化しているような気がします。色のグレードは上がっているのに、鳥はどんどんかわいらしくなる……なんだかへんな感じです。
しかも、橙以降がネタ切れしています。いっそ黄色が「ひよこ」で、橙以上は「カラーひよこ」になろうかとも思います。これなら何色にでもなれますし、暖色に入って「新たなステージ」という感じも出ます。
……が、実際のところは、ほとんど未定です。そして、アイコンはずっとヒシクイさんのままだと思います。

【Q5】競プロ以外の趣味とは？

中の人は昔、短歌や俳句などを嗜む程度にやっていました。ABC309のぞいツイートとして詠んだ俳句がこれです。

（ABC309、目標５完早解き）
「ぞい！」　吠える短夜　指に汗

霧しゃま

季重なりしていますね（短夜、汗）。あと、競プロに臨むところだという感じが伝わらないので、ちょっと直してみます。

（ABC309、目標５完早解き）
「ぞい！」　キーに置く指　玉の汗

霧しゃま

まあこんな感じでしょうか。ちなみに「ぞい！」はこれで上五です（字足らず）。三音分を贅沢に使った「ぞい！」の残響を聴いてください。

毎回、「ぞい！」ツイートのために何らかのネタを考えるのが日々の楽しみになっています。一番反響のあった「ぞい！」は、ABC301のこれです。

ぞーーーーい！お茶

なんだか既出のような気がしますが、あまり気にしていません。というか、毎回何らかのパロディネタの寄せ集めのような感じです。

さて、冷えから数え二週間
相変わらずの不安だが
我は進化の度合い二歩と半分
もっと賢く、解かせていただく
「ぞい！」
（ABC307、目標６完）

これとか、平沢進『コヨーテ』の改変です（なお、この回は冷えたもよう）。中の人は馬の骨だったのです（『時空の水』から『救済の技法』あたりの時期が好きで、髪が白くなったあたりからはほぼ知らない）。

今後について

9月にあるWorld Tour Finals(Open)は、2日目だけでもRated参加してみたいと思います。青から転落しないように、来週のABCでもちゃんとレートを上げておきたいところです。
正直なところ、まだ黄色になれる気は全然していませんが、これまでもそうだったように、精進を続けていればいつか道が開けると信じています。
精進はABCの青色問題がまだ残っているので、少しペースを上げて埋めに掛かりたいと思います。黄色の精進はそれからです。あとは、典型90の★6やEDPCの残り5問、TDPCやJOI、PASTなどにも適宜手を出していければと思います。
技術面では、そろそろフロー系や、多項式系のFFTやFPSなどのアルゴリズムをまともに習得する頃だと思っています。まあ、この辺りは長い休みに集中してやるか、精進で出た順に拾っていくかになるでしょう。
ちなみに、Streakも継続していて、2023年8月26日時点で297日です。
色別では青色が82日です。10月くらいには黄色に入っていく予定です。

継続は力なり！

あっ、それからすっかり放置しているもじぴったんの件も……これはAHCの範囲だと思うので、少しずつでも勉強していければと思います。

おわりに

最後の色変にはならないつもりです！　黄色も目指し頑張ります！
以上、霧しゃまでした！

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