shu8Creamのブログ

競プロブログ。

AtCoderで水色になりました！

色変記事

こんにちは、shu8Creamです。 先日行われた、LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）にて1754パフォーマンスを出して、水色になることができました！ 現在のレートは1247で、レートが一気に+73されたので大成功回でした。 初めて緑になったのが、2021/4/18らしいので2022/8/6で水色になるまで、1年4ヶ月ほどかかりました。

ちなみにCodeforcesは少し前に青色になりました。
ちなみにちなみに最近AtCoder Heuristic Ratingでも水色になりました。

精進記録

各コンテストサイトのAC数
Solved By shu8Cream
Topcoder: 0
Codeforces: 267
AtCoder: 1505
AOJ: 32
yukicoder: 76
library-checker: 7
Sum: 1887

記録はこのような感じです。 長期間停滞している時期もありましたが、就職など生活環境の変化から精進時間が取りづらいという明確な理由があったので、そこまで気を落とすこともなく継続できました。コンテストに出続けることができたのがモチベーションを保てた理由かなと思います。

ABCはほぼ必ず出ていて、ARCには自分の実力を見て早解きできないときつい配点の時はUnratedで参加したりしてました。 個人的にはABCよりもARCの方がじっくり考えなきゃいけない問題が多いので好きです。（もっと実力がつけばもっと好きになれそう）

基本使用している言語はC++で、多倍長整数でズルしたくなったりした時にPython使ってたりします。（ほぼ出番はない） Rustは絶賛練習中です。

学んだアルゴリズム

以前、緑になった時に書いた記事から増えたものと実際に使用したものを中心に紹介します。

実際に使用した

  • 座標圧縮
  • セグメント木
  • BIT
  • 最小全域木(クラスカル法・プリム法)
  • ランレングス圧縮
  • トポロジカルソート(BFS実装)
  • SCC
  • 遅延評価セグメント木
  • Mo's Algorithm
  • ベルマンフォード
  • Zアルゴリズム(ABCで使用、問題は解けず)
  • LIS(ARC)
  • 最大フロー（Ford-Fulkerson）（ARC）
  • XorShift(主にマラソンで活躍)

勉強したが、コンテストでは未使用

  • BinaryTrie(Codeforcesで出題されたので勉強)
  • LCA(オイラーツアー +RmQ)
  • SparseTable
  • LCS
  • レーベンシュタイン距離
  • ZobristHash(ABCで出題されたので勉強)
  • ミラーラビン素数判定法

今後勉強予定

補足

僕の場合、水色になるためには必須でない知識を色々学んでいます。 もし緑で伸び悩んでいたり、現在茶色で水色を目指しているような方は

これをしっかり身につけることが最重要課題だと思います。僕は、DPとDFSがかなり苦手で結構練習しました。 ここ最近は、シンプルDPなら問題見たらすぐにDPだと気づけるようになりましたし、DPだと気づけなかった頃の気持ちを忘れ始めています（これは良くない気がする）。 DFSは、BFSでも解けるものをDFSで解き直したり、慣れてきたら木DPの問題まで手を伸ばして練習したりしました。

競プロ以外

git

ライブラリ類は、基本gitで管理していてgithub上で見られるようにしています。大学時代にプログラミングの演習で使用を強要されたので使えるようになりました。取っ付きづらいツールですが、かなり便利です。

React

後で更新するかも

ここの章で競プロ以外に面白いと思っていることを色々書きたいと思ってましたが、書き始めてから時間が経ちすぎて忘れてしまいました。 思い出したら更新します。

次の目標

AtCoder青を目指して精進していきますが、距離感的にまずはCodeforces紫を中間ポイントとして地道に頑張ります！

反省

だらだら書いていたら、いつまでも公開できなくなっていたのでとりあえず公開することにしました。 気に入らないところは後で更新します。