入水しました！

はじめに

11月20日のABCで無事入水できたので、いつか誰かの役に立てばいいなと思い入水記事を書かせていただきます。

緑色になった時のスキル

一応緑色なった時点でのスキルは

  • BFS，DFS：時間をかければ書ける
  • UnionFind：知っているけど、コンテストで使ったことはない
  • 簡単なDP(ナップザックまで)：時間を書ければ書ける
  • 難しめのDP(ナップザック以上)：解説を見ても理解することが難しい
  • 累積和：スムーズではないけど書ける
  • ダイクストラ：知っているけど使ったことがない
  • ワ―シャルフロイド：書ける
  • modint : 持ってて、使うことができる
  • 二分探索：よくバグらせるけど、時間をかければ書ける

くらいであったことを書いておきます。

緑色から水色になるために効果的だったもの

勉強法

灰~水diff埋め

一番記憶に残っているのは、Ratedコンテストの灰~水diffを全て埋めたことですね。ある色を全埋めするという目標を立てると、苦手な問題にも取り組む必要がでてくるので個人的にはおすすめです(ある人の受け売り言葉ですが)。

ゆきこの算数タグ埋め

特殊な例かもしれませんが、ゆきこの算数タグを埋めたのは力になった気がしています。僕は算数問題に割と苦手意識があって、例えばABCのA問題でたまにO(1)で解ける問題を解くときに、繰り返し処理を書いちゃうようなタイプです。緑コーダになった後でも、たまに算数問題で引っかかって大きくレートを落とすことがあったのですが、最近は前よりも減った気がしています。ゆきこの算数タグにはARCのAに出てくるような算数問であったりとか、ABC-Cででそうな問題が多々あるのでお勧めです。

EDPC埋め

DPに対する苦手意識がかなり軽減されたのが大きな貢献だと思っています。

登場するアルゴリズムを全て身に付けられたかどうかには、僕の精進不足もありかなり疑問符がつきます。けれど、これまでにナップサック問題にも割と苦手意識があった僕にとっては苦手意識を減らすという意味でものすごく良い経験になりました。埋める際に分からない問題があっても、フレンズさんの解説記事があったり、最近では競プロyoutuberのかつっぱさんが解説動画を公開されていたはずなので、EDPC埋めをしやすい環境が整っているかと思います。

www.youtube.com

アルゴリズム

セグメント木、遅延セグメント木

緑色から水色になるまでに覚えたアルゴリズムで、コンテストで使用したのはこの2つだけだと思います。この2つのおかげでABC-D問題あたりで想定解じゃない解法で通すことができました。色々な問題に使えたりするので、覚えておくとどこかで役に立つ機会がきっとあると思います。

解説を見るタイミング

基本的には灰~水diff埋めをしていた時は30~40分考えて何もわからなければ解説を見ていました。ちなみに現在青diff埋めをしている際は、1時間考えて分からなければ解説を見るようにしています。

印象に残っている問題

印象に残っている問題はたくさんあり、なかなか一つに絞ることは難しいのですが、一つ上げるならPondです。コンテスト中に通した最高diff(1622)で時間ぎりぎりにACできたので印象に残っています！

atcoder.jp

最後に

最後まで読んでいただき、ありがとうございました！