競プロ備忘録

競プロerの備忘録

ブログ開設＋色変しました

プロフィール

  • 昨年4月にAtCoderで競プロとプログラミングを始めた。
  • 書ける言語はC++。Java、JavaScript、Cもほんの少しだけ書く。
  • 数学知識は高校でストップしている。なぜか文系に進みましたが、数学は好きです。
  • 社会人。

ブログ開設の動機

  • AtCoderで色変したら記事を書く人をよく見かけて、自分もやってみたくなった。
  • 入緑のときはTwitterを始めたから、入水のときも何か始めたくなった。

本題：色変しました（水色）

昨日のABC206にて、順位496位、perf1815で、入水を達成しました。入緑したのが昨年11月上旬なので、半年以上ぶりの色変になります。
完全に舞い上がっちゃっているわけですが、今くらいはいいだろうということで、備忘録的にここまで学んだことを記します。

競プロを始めてから今までやったこと

  • C++の文法の勉強
    • プログラミング初心者だったので、参考書が多く、競プロ人口も多いC++を選択。
    • APG4bを一通りやって、後は必要になったときにリファレンスを参照している。
  • データ構造・アルゴリズムの勉強
    • 計算量の概念に始まり、グラフ理論や数学、各種データ構造など。
    • 本を購入。
      • オーム社の「Cによるアルゴリズムとデータ構造」。数弱の自分には難しかったが、学習の方針が見えた。
      • 蟻本。自分には少々難易度が高く、未だに放置気味。今後進めていく予定。
      • けんちょん本。非常にわかりやすく、おすすめ。入門の一冊はこれしかないと思った。バイブル。
  • AtCoder以外のコンテスト参加
  • 精進
    • AtCoder Problemsで、Boot Camp for Beginnersをすべて埋めた。その後はRecommendationをひたすら埋めている。
      • 現在までに1168AC。最高Streakは176。
    • 典型90問。新しいデータ構造・アルゴリズムや考察テクニックが手に入る。
  • コンテスト参加
    • 最も重要。記憶にある限り、競プロを始めてからのRatedコンテストは1回を除いてすべて参加している。
    • NoSubは絶対にしない。正々堂々競うほうが経験として記憶に残る。レートの差分の絶対値＝経験値と信じている。0完太陽も経験（）

これまでに学んだデータ構造・アルゴリズム

データ構造

  • STLのコンテナ
    • vector、set、map、queue、deque、priority_queueは必須。stackは知識としては必須だが、使用機会は少ない。array、listは使わない。
    • priority_queueは小さい方から取り出せるようにして、heapという名前でtypedefしている。
  • 隣接リスト、隣接行列
    • 隣接リストは必須。グラフの表現方法として頻繁に使う。
    • 隣接行列は、メモリ効率の悪さも相まってあまり使わないが、実現は簡単。
  • Union Find
    • 必須。同じ集合に属するかどうかを管理できる。使用機会はそれなりに多い。
  • セグメント木
    • あると便利。累積和やいもす法などで代わりが効くことが多い。ただ、ないと困ることもたまにある。
    • 遅延セグ木も最近知ったが、自分のレベルでは実戦で使ったことはない。

アルゴリズム

  • 累積和
    • 必須。使用機会はかなり多く、応用の幅も広く、奥が深い。
    • 関連でいもす法も必須。
    • 二次元累積和は、使用機会は少ないが、使えなくて非常に困ったことがある。
  • ソート
    • 必須だが、STL関数で提供されているので、知識として大雑把に知っている程度。
  • 二分探索・三分探索
    • 必須。伝家の宝刀。
    • 二分探索のときはSTLのlower_boundやupper_boundを使う機会も増えたが、自力でも書けたほうが良い。
  • DFS・BFS
    • 必須。記述の単純さと応用の効きやすさから、自分はBFSを愛用している。
    • AtCoderのコンテンツとして、BFSとDFSの学習を目的とした問題があったと思うので、初心者はそれをやるといいと思う。
  • ダイクストラ法
    • 必須。一点からその他のすべての点との最短距離を求める。
    • priority_queueをヒープとして使うことで、ほとんどBFSと同じ書き方ができる。
  • ヮーシャルフロイド法
    • あまり使う機会はない。ただ、非常に簡素に書けるアルゴリズム。
  • ベルマンフォード法
    • 使ったことはない。経験のある多くのグラフ問題は負の重みの辺を持たないので、ダイクストラのほうをよく使う。
  • bit全探索
    • 必須。制約が20以下のときに真っ先に疑う。茶色のときくらいに覚えた。
    • 扱いに慣れていると、bitDPが結構すんなり頭に入る気がした。
  • DP
    • 非常に曲者。必須だが、完全には理解できていない。EDPCを埋めたい。
    • 自分は漸化式に非対応なので、メモ化で感覚を掴んだ。
  • 数学系アルゴリズム
    • gcd、lcmの扱い、約数列挙、素数列挙、高速素因数分解...etc
    • 数弱の自分には最大の難所。今まで2回経験している0完太陽は、数弱に起因する。

今後の目標とやること

  • ポジティブには入青、ネガティブには逆色変回避。
  • 数弱の克服。
  • 典型90問の完遂。
  • EDPCを埋める。
  • 水diff埋める。
  • 蟻本を読み進める。

まとめ的な

  • 水色コーダーになるのはここ半年間の最大の目標だったので、飛び上がるほど嬉しかったです。
  • すぐに逆色変しちゃうかもしれないし、結構順調に行っちゃうかもわかりませんが、色は精進の結果なので、今後も常に精進し、恐れることなく積極的にコンテストに出ていきます。
  • せっかくブログ開設したので、面白かった問題や理解の進んだデータ構造・アルゴリズムについて、備忘録的に記録していくこともできたらなと思っています。