はじめに
水色になりました！
12月に緑になってから半年くらいかかりました
やったこと
問題を解く
- ABCの緑~水diffの過去問題を解く
- 苦手な問題も何問か解くと少し慣れますね
-
EDPCを進める
- DPはよく出るので、少しやるだけでもABCで役立ちます
-
競プロ典型90問の★4〜5問題をやる
- ★4は全て埋まりました、とても学びが多いです
読んだ本
-
アルゴリズム的思考力が身につく！ プログラミングコンテストAtCoder入門
- 主に緑になるまでに読んでいました
- プログラミング初心者でも本当にわかりやすく読めます
-
競技プログラミングの鉄則
- フルカラーで解説もとてもわかりやすいです
-
プログラミングコンテストチャレンジブック
- 途中までしか読めて無いです、ちゃんと読みたい
主に学んだこと
思いつくものを書いていきます
それに関する問題もいくつか付けました
整数
フェルマーの小定理+繰り返し2乗法
- mod上での割り算に使います
- ACLのmodintを使えばこれを知らなくてもなんとかなるみたいです
- ABC145 D - Knight
エラトステネスの篩
- 言わずと知れた素数を求めるアルゴリズム
- その数を割った最小の素数を記録しておくと素因数分解がO(logN)で出来ます
DP
ダブリング
- 2^n移動した時にどこにいるかをDPで求めます
- ABC167 D - Teleporter
- ABC179 E - Sequence Sum
確率DP / 期待値DP
- ある状態からある状態に変わる確率や期待値をそれぞれ求めていきます
- ABC298 E - Unfair Sugoroku
- ABC280 E - Critical Hit
桁DP
- それ以下であることが確定しているかを確認ながら遷移します
- ABC117 D - XXOR
- ABC154 E - Almost Everywhere Zero
二分探索 / 三分探索
二分探索
- 出来ると出来ないの狭間を二分探索
三分探索
- 凹んでるところを三分探索
- yukicoderで三分探索しようとすると誤差でダメな問題に出会って泣きました
木構造
ヒープ
- 最小値か最大値をO(logN)で求めます
- priority_queueがこれですね
セグ木
- 区間の最大値、最小値、和などをO(logN)で求められます
- ACLに頼って自作をまだしていないです、今度ちゃんと作って理解を深めたい
- ABC185 F - Range Xor Query
Union-Find木
- Union-Findは併合は出来ても分割が出来ないことが弱点です
- 逆からシミュレーションするとグループの分割を併合として扱えます
- ABC229 E - Graph Destruction
- ABC264 E - Blackout
グラフ
DFS
- 再帰関数を使って探索します
- ABC213 D - Takahashi Tour
BFS
- queueを使って探索します
- DFSよりBFSの方が使う場面が多い気がします、最短距離で使いがちなので
- ABC211 D - Number of Shortest paths
- ABC224 D - 8. Puzzle on Graph
Dijkstra法
- 重みのある辺がある時に使います
- 昇順に取り出すpriority_queueを使うので↓を書いておくと便利です
template<class T>
using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;
01-BFS
- 辺の重みが0か1の時に、dequeを使って探索します
- logは取れますが、Dijkstraでも間に合います
- ARC005 C - 器物損壊！高橋君
ワーシャルフロイド法
- 全ての頂点間の距離をO(N^3)で求められます
- ABC208 D - Shortest Path Queries 2
トポロジカルソート
- uからvに向かう辺がある時、uがvより先に来るようソートします
- サイクルの検出にも使えます
- ABC216 D - Pair of Balls
お役立ち情報
atcoder-cli
テストケースの実行と提出がコマンドライン上で簡単に行えてめちゃめちゃ便利です
AtCoder Library
いろんなアルゴリズムをAtCoder側でライブラリとして提供してくれています
yukicoderでも使えるみたいです
拡張機能
-
AtCoder Easy Test v2
- コードの提出の前に簡単にテストを実行できます
-
AtCoderLanguageButtons
- 提出言語を簡単に切り替えられるボタンを追加します
- 自分は基本C++ですがたまにPythonも使うので助かります
-
atcoder-difficulty-display
- 問題のdifficultyをAtCoderのページで表示してくれます
-
ac-predictor
- コンテスト中にパフォーマンスを予測してくれます
-
AtCoderStandingsAnalysis
- 順位表のページに問題ごとに通した人の数やペナ率などを集計した表を追加してくれます
-
Time Limit Emphasizer
- 実行時間制限が2秒じゃない時に赤文字で強調してくれます
-
ac-rating-icon
- レーティングに対応したアイコンを付けてくれます
便利なサイトなど
-
AtCoder Problems
- 神
-
AtCoder Companions
- 自分と同じテストケースで落とされた人がどう修正してACしたのかを調べてくれます
-
AtCoder Rating Simulator
- どのくらいのパフォーマンスでどのくらいレーティングが上がるのかを可視化してくれます
-
GRAPH × GRAPH
- グラフ問題の入力例を可視化してくれます
おわりに
次回のABCで緑に戻ってしまう気しかしませんが、AtCoder Junior Leagueもあるので頑張ります
追記
青になりました → 入青記事