はじめに
皆さんはじめまして、Gifkenです。
取り組んで8か月半にして、つい最近のABC439で入水をしたので、せっかくなのでブログを書き残してみようと思って書いてみました。
スペック
- 東京科学大学1年生
- 技術系サークルに所属
- 数学は(学内で)まあまあできるくらい
- プログラミングに触れたことが高校時代までほとんどない
- タイピングがいまだに遅い
- 高校時代に数オリ予選受けたけど予選敗退している
入茶まで
始めたきっかけは、もともと数学とかに興味があって、そういった競技科学系の活動に興味があったからで、高校時代とかにもうatcoderの存在は知っていたりとかしていたんですが、中々運動部が忙しかったりで手を付けられていませんでした。
大学受験が終わったタイミングで、何か新しいことを始めようと考えた時に、「そうだ、atcoderをやろう!」となりました。
そこで3月末からPCを買ってもらったので、atcoderを始めようとしましたが、なんか血迷って、APG4bじゃなくて、普通のC++の基礎(つまりクラスとかポインタどうこう)からやってしまったのです。今考えれば時間の無駄かもしれません。
そこで情弱の私は4月にやっとAPG4bを見つけてatcoderライフをスタートしました。APG4bを1章やったからといけると思った初コンテスト。結果は2完でパフォーマンス2桁。相当な惨敗ですね。
流石にこの時は難しいなと思っていたんですが、setをちゃんと使えるようになったりとかcharとstringの違いを理解してから変わりました。そして2回目のコンテストでは茶パフォ、そのあともずっといい感じの成績でいって、Dまでアルゴリズムがいらない回では4完することもありつつ6月前のコンテストでは、ベストパフォーマンスを残して茶色になりました。
この時のスキルセットは
- upper_boundと累積和、ソートが分かる
- setが使える(mapよくわからない)
- 型の違いが分かる
- グラフ問題解けない
くらいだと思います。逆に茶色になるくらいならこれぐらいでもゆとりをもってなれると思います。
入緑まで
ここで私は気づきます。「典型のD問題を解けるようにするためには精進が必要では？」と。
atcoder problemsとの出会いはここからです。緑になるためには、茶色の問題を押さえたうえで緑色の問題を解けるようにしないといけないという恐ろしい事実があります。
ここでatcoder problemsから10問〜15問D問題を拾って精進をし始めました。最初は難しかったんですが、少しづつやっていくうちにおおよそ「二分探索、累積和、グラフ探索、貪欲、簡単なDP」のどれかに収まることに気づいて、それをやっていくうちに初見のコンテストでもDを解ける回数が大半になっていきました。
また、グラフ探索を克服する必要があったので
- https://qiita.com/drken/items/996d80bcae64649a6580 (グラフ超入門:けんちょんさんの記事)
を参考にして、グラフに対する苦手意識も克服することができました。
そして、そろそろレートを上げる上で、典型についても整理していく必要があったので、典型90(星5以下)をやったりとか、鉄則本をやったりとかして、ダイクストラやセグメントツリーと言ったデータ構造やアルゴリズム面での典型だけではなく、「逆順からクエリを読む」や「パリティ、mod上での不変量」といったテンプレートも身に着けました。
このようにすることで、D問題を早く解くことによって茶色帯を概ね緑パフォーマンスで通過し、9月ごろのABC424では、水色パフォーマンスをとって入水することができました。
このころのスキルセットとしては、
- 二分探索がちゃんと使える(答えから二分探索できる)
- set/mapを使いこなすことができる
- 基本的なグラフ探索、最短経路ができる
- 簡単なDP(ナップザック、確率)を書くことができる
- 素数上の逆元が分かる
だいぶ灰色→茶色のころよりもレベルが上がった気がしますが、それでも茶色から緑になるだけでしたらここまでやる必要はないと思われます。少なくとも二分探索の応用と基本的なグラフ探索、DPができれば緑色に上がる上で困ることはないと思われます。
入水まで(前編)
ここまで来るとレートが少しづつ上がりにくくなってきます。緑色でしっかりとレートを上げるには水色パフォーマンスを取らなければなりません。基本的に水色パフォーマンスを取るには、よほどの回でない限り、4完早解きか5完が必要になってきます。また、4完でも遅いと緑色下位、場合によっては、茶色パフォーマンスが出ることがあります。
つまり優先するべきことは、
- 4完を安定して高速にできるようにする
につきます。
これに役立つのは、AtCoder Daily Trainingで、過去のコンテストからランダムに選ばれた問題をやることによっていい練習になります。なお、時間制限が60分なので普通のコンテストよりも時間的な圧力が大きく、早く解くための有効な訓練になります。火曜日、水曜日、木曜日の1日に3回開催しているので隙間時間に効率的に精進をすることができます。おそらく緑コーダーになったばかりの人は、「4完はできるけど早く解くのは難しい」みたいなレベル感だと思われるので、ADTの練習は有効なのではないでしょうか。
実際にADTを本格的に始めたのは9月の終わりごろからですが、それを継続することによって、4完早解きを安定させてパフォーマンスを水色に安定させることができました。
ADTは、時間が無くてもできるので、「〇問題まで解けるけどスピードが遅い」という人にお勧めです。1色分パフォーマンスが変わります。マジで。
入水まで(後編)
ADTも成果が出始めてレート1100に早々に到達できて入水も目前だと思い込んでいた11月前半。今思えば、ここからが本当の戦いでした。4完早解きや緑diffEを解いた5完では、大体パフォーマンスが水色前半である以上、レート1100以降では上がりにくくなっていきます。
ここで、今まで順調に上がっていったからこそ自分に「年末までに入水しなければならない」という圧を掛けてしまいました。そして12月の後半には、サークルでハッカソンがあり、その期間中にはコンテストに参加できません。焦りが生じます。
下の画像を見ていくと、やはり圧倒的な勝利ができずに少しずつ上がっていく状況が続き、ハッカソンの直前には1196という何とも呪われたような数字のレートになってしまいました。この時の気持ちは、「もう、本当にやめてくれ。」そのものでした。
そして、精進からいったん離れて、ハッカソンにて本気でゲームを作り終わった次の週、「絶対に入水してやる。」という気持ちになりました。しかし、ハッカソンの疲れと年末の多忙によって、思いだけが強く、精進ができていませんでした。
迎えた今年最後のABC438。「水色パフォを取れば絶対に入水できる。」そう言い聞かせました。
結果はまさかの緑パフォーマンス。惨敗しました。「今年中に入水する」という目標を果たせず軽く絶望しました。焦りからE問題で冷静な思考ができずに散っていきました。
こうして、新年のABCは、もうどうでもいいやという適当な感じでやりました。そしたらなんとなんとFが簡単だったとはいえ6完することができて、あっさりと爆上げして入水することができました。正直こんなにすんなり入るとは思ってなかったので、逆に腰を抜かしました。何はともあれ、入水を果たせました。
この後編の話から伝えたいことは、「メンタルって大事」という話で、メンタルが変わるだけで全然パフォーマンスが変わったりするからリラックスできると良いねという感じです。私も緊張してしまうタイプですが、
- 他人と比較しすぎない
- 順位表は最低限にする
- 逆に問題が解けたからと気を抜かない
を意識すればだいぶ違うのではないでしょうか。
メンタルは本当にAtCoderに限らず大事なので、自分なりの方法を見つけてご自愛ください。
AtCoder Problems
概要
拡張機能で無理やりADTのAC数も表示をしていますがおおよそ600ACくらいですね。
割と精進をしている方ではあると思います。
Difficulty
割と埋めるとかをせずにピンポイントで精進をしていたので、意外と解いている量としては灰色、茶色が多くなくて、緑以降がやや多いんじゃないかなと思います。
スキルセット
今は大体
- グラフの基本に加え、強連結成分分解や木上のDPがある程度わかり組み合わせできる
- 数学は割と深い部分(約数系包除や高速素因数分解など)まで理解し使える
- DPとセグ木の組み合わせもすることができる
- 遅延セグ木は、使えるがまだ応用できるという範囲ではない
くらいだと思います。やっぱり水色くらいのレベルになると、基本的なアルゴリズムを知っているかよりも、適切に組み合わせられるかの方が大事になってくると思います。
個人的な感想
周りと比較をするな!!
これは入水の後編で語った通り、レートを上げる上で一番の障害になりかねません。AtCoderにはとんでもなく優秀な人がいるのも事実で、実際に同じサークルで、灰色なのに数学力でねじ伏せて水色パフォーマンスを取る人とかを見ています。
そういう人と比べて、競争するのはメンタルが強い人なら勝手にどうぞ。という感じですが、メンタルが弱い人はやめておくべきです。なぜなら、私が追おうとして、11月と12月に前述のスランプを引き起こしてしまったからです。「強くなろう!!」よりは「楽しもう!!」の方が全然気持ちも楽だし、結果的により早く強くなることができます。
「自分は自分」このマインド、大事です。
まずは簡単なものから
データ構造は複雑なものの方がより複雑な事象を扱うことができるし、その難しい物を習得しようとしてしまいがちです。しかし、まずは簡単なものからやるべきです。
例えば、「遅延セグ木のみ」または「セグ木＋不変量の考察」で解ける問題があったとします。当然「遅延セグ木だけ」の方が圧倒的に解くのも楽でしょう。「セグ木」を知っている上で「遅延セグ木」を使うのは問題ないですが、逆に「遅延セグ木」だけなぜか知ってる状態(ここでは道具の使い方だけ知ってる状態)でそれを解いても、「不変量の考察」という重要な考察機会を飛ばして、脳死でコンテストを解いてしまうことになります。
AtCoderはライブラリを貼り付けるゲームではなく考察するゲームが本質で、その本質を逃さないことが今後のレーティングを上げていく糧になると思うので、順番にアルゴリズムを学んで、手持ちのカードでどう考えたら解けるんだろうと考えることが実力を上げる近道になると思っています。
終わりに
私は、最終的に最低でも黄色を目指したいなと思っています。
今回水色になれたのはその通過点として、かなりいい経過だと思うので、このままのペースで頑張っていきたいです!
短くて拙い文章ですが、最後までご覧いただきありがとうございました！！