AtCoder水色になりました！

アルゴリズム 競技プログラミング AtCoder

久しぶりです. yapattaです.

今回ABC160で水色になったので変色記事を書きたいと思います. 

1年ぐらい緑で停滞しましたがなんとか水色コーダーになれました. 水色になりたい人の励みになればいいなと思っています. 

すべて鵜呑みにせず, 必要なところだけ参考にしていただければ幸いです.

自己紹介

競プロやっている人の中では初期スペックが化け物みたいで参考にならない人もいるので, 自分のあらすじでも書きます(自分と似た状況の人がいれば幸いです).

情報系の学科の新3年です(2020年4月から). プログラミングは一度高校一年のときにC言語を勉強してみたのですが, ポインタ周りがわからなくて挫折しました. 大学受験後もう一度真面目にプログラミングをやってみたいなあと思って, C言語の入門書とかを大学一年の最初にかじりました. 競技プログラミングについては大学一年の6月あたりに予備校の友人に勧められて大学で週一回やる競プロの活動に行き始めました. 大学一年の11~12月あたりから真面目にAtCoderに参加して螺旋本を読むようになった気がします.

大体こんな感じです.

では次に実際勉強したこと, 精進内容について書きたいと思います.

勉強したこと

勉強したアルゴリズムとか

  • GCD, LCM
  • DFS, BFS
  • しゃくとり法
  • 二分探索
  • IMOS法
  • 素数列挙(エラトステネスの篩とか)
  • 二項係数(フェルマーの小定理, 逆元など)
  • UnionFind木
  • 最小全域木(Prim法, クラスカル法)
  • DAG(トポロジカルソート, 閉路検知とか)
  • ダイクストラ, ワーシャルフロイト, ベルマンフォード
  • DP(普通のDP, 桁DP, BitDPとか)
  • LCP(Suffix Array, ローリングハッシュ, Z Algorithm)
  • 拡張ユークリッド
  • セグメント木, 遅延伝搬セグメント木(とりあえずどう動くかわかるぐらい, 群の話は自信ない)
  • BIT
  • 最大流(Ford Fulkerson法)(これも理解した程度)

こんな感じな気がします(たぶんもっと細かく言えばきりがないかも).

精進について

精進グラフ, 精進量はこんな感じです(詳しくは僕のID: ziroppeで検索してください).

f:id:ziroppe:20200329005436j:plain

f:id:ziroppe:20200329011558j:plain

f:id:ziroppe:20200329011630j:plain

自分の勉強方法

最近1ヶ月は主にABCの水色diff(たまに青diff)を1日一問ほど埋めていました.

自分のレートより少し上の問題を無理のない程度に解くと自分の実力アップに良い気がします.

問題の解き方としては,

一時間ほど考えて実装する → WAだが思いつきそうならもう少し考える, 疲れたか諦めたかACしたなら答えを見る

みたいな感じです. 問題を解く時間が長すぎると集中力もモチベも続かないため, 今の実力で解けるか解けないかぐらいの問題を選ぶといい気がします. あと何時間もじっくり考えるというよりは, 空いている時間に解法を考えるとかのほうが個人的に良い気がしました.

あと解説を見るときに, その問題の解法を複数見て理解するように(できれば実装)する(例えば, ABC141Eの解法ではDP, Z Algorithm, ローリングハッシュなど複数解き方がある), などが実力アップに良さそうです. 絶対解きっぱなしにしちゃいけない気がします(全く手に負えない問題なら放置するのもありです).

個人的な精神論のお話

これは人によると思いますが, 僕はある特定期間に熱烈精進するよりは, 生活にバランスを取って精神が辛くならない程度に毎日少しづつ精進するようにしたら競プロが楽しくなって, パフォーマンスも高く出るようになった気がします.

個人的に精神の安定は最も大事な気がします. 周りのレートがどんどん上がっていく中, 自分のレートが停滞したり下がったりすると焦りますし, 自信もなくなると思います. 実際それで苦しめられた時期がありました(去年の秋頃). そういう中でもマイペースに自分のレベルに合った問題に取り組み, 競プロの時間をコンスタントに持つことで少しずついい方向に進んでいく気がします.

もしくは競プロが辛くなったら思い切って休むのも手な気がします. 僕は2ヶ月ほど休んだら気が楽になって競プロが楽しくなってきました.

まあともかく楽しんで取り組むのが一番だと思います！

最後に

これからも楽しく競プロに取り組みたいですね. 実際, 競技プログラミングをやっていることでたくさんの出会いがありましたし普通じゃできない体験もできたと思います. 競プロと出会って本当によかったです. 今年もICPCの本戦に出れるように頑張りたいですね.