競プロ問題コレクション - 今日から始める競プロ日記
最終更新日:2020/01/13
はじめに
復習しやすくするために、解いた問題をジャンルごとにまとめたいと思います。
ちなみにジャンルの分け方は私基準です(つまり雑)。
また、問題が重複している場合もあります。
少しずつ更新していきます。
まとめるコンテスト
- AtCoder
- AIZU ONLINE JUDGE
- yukicoder
- Codeforces
目次
- はじめに
- まとめるコンテスト
- 目次
- 良く参考にする記事
- 全探索する問題
- 数え上げの問題
- modをとる問題
- 二分探索する問題
- 三分探索する問題
- 累積和の問題
- 動的計画法の問題
- 尺取り法の問題
- グラフ(DFS、BFS)の問題
- ソートの問題
- 算数・数学、それに近い問題
- 合同式を使う問題
- 整数値の各位の桁に関する問題
- 2進数を扱う問題
- 2次元グリッドの問題
- インタラクティブな問題
- 文字列を埋める処理(ゼロ埋めなど)をする問題
- 切り上げする問題
- 入力の仕方を工夫したい問題
- ちょっとした工夫をすると楽になる問題
- setを使う問題
- 素因数分解を使う問題
- おわりに
- 今日から始める競プロ日記まとめ
良く参考にする記事
- ライブラリ関係
全探索する問題
普通に全探索
- ABC128 : D - equeue
DFSで全探索
- ABC119 : C - Synthetic Kadomatsu
bit全探索
- ABC147 : C - HonestOrUnkind2
部分的に決め打ちしながら全探索
- ABC123 : D - Cake 123
- 三井住友銀行2019 : D - Lucky PIN
計算量を考えながら全探索
- ABC040 : B - □□□□□
参考記事
数え上げの問題
- ABC087 : B - Coins
- ARC102 : C - Triangular Relationship
modをとる問題
- AOJ NTL_1_B : https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_B
- ABC041 : B - 直方体
- ABC055 : B - Training Camp
- おそらくmodを取る問題の中で一番簡単
- ABC060 : B - Choose Integers
- ABC132 : D - Blue and Red Balls
- ABC145 : D - Knight , 解説記事
- ABC147 : D - Xor Sum 4
- 日経コン2019予選 : B - Counting of Trees , 解説記事
参考記事
「1000000007 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜 - Qiita よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録
二分探索する問題
- ABC123 : D - Cake 123
- ABC146 : C - Buy an Integer -ABC149 : E - Handshake
- No.604 誕生日のお小遣い - yukicoder , 解説記事
参考記事
二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita
三分探索する問題
- ARC054 : B - ムーアの法則 , 解説記事
参考記事
三分探索と黄金分割探索 - naoya_t@hatenablog
累積和の問題
- GigaCode2019 : D - 家の建設
参考記事
動的計画法の問題
- Educational DP Contest / DP まとめコンテスト - AtCoder
- GigaCode2019 : E - 車の乗り継ぎ
参考記事
動的計画法超入門! Educational DP Contest の A ~ E 問題の解説と類題集 - Qiita Educational DP Contest の F ~ J 問題の解説と類題集 - Qiita 典型的な DP (動的計画法) のパターンを整理 Part 1 ~ ナップサック DP 編 ~ - Qiita
尺取り法の問題
- ABC124 : D - Handstand
参考記事
しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ - Qiita
グラフ(DFS、BFS)の問題
隣接行列
- まだ
隣接リスト
- ABC126 : D - Even Relation
参考記事
DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【後編】 - Qiita BFS (幅優先探索) 超入門! 〜 キューを鮮やかに使いこなす 〜 - Qiita
ソートの問題
ソートのアルゴリズム
参考記事
ソートを極める! 〜 なぜソートを学ぶのか 〜 - Qiita
pair, tupleを使うソート
- ABC128 : B - Guidebook
参考記事
算数・数学、それに近い問題
- 三井住友信託銀行2019 : C - 100 to 105
合同式を使う問題
- ARC102 : C - Triangular Relationship
整数値の各位の桁に関する問題
参考記事
2進数を扱う問題
- ABC014 : B - 価格の合計
- ABC147 : D - Xor Sum 4
参考記事
C++ 数値を 2進数 8進数 10進数 16進数 文字列に変換する方法 | MaryCore
2次元グリッドの問題
- ABC035 : B - ドローン
- ABC075 : https://atcoder.jp/contests/abc075/tasks/abc075_b、公式解説PDF
- あるマスの周り8マスを調べる方法が分かりやすかった(コードを参考にしたい)
インタラクティブな問題
文字列を埋める処理(ゼロ埋めなど)をする問題
- ABC113 : C - ID
参考記事
【C++】左詰め/右詰め/ゼロ埋めの方法と注意点【cout/iostream 文字揃え】 | MaryCore
切り上げする問題
- ABC082 : A - Round Up the Mean
入力の仕方を工夫したい問題
- ABC-119 : A - Still TBD
ちょっとした工夫をすると楽になる問題
- (ソートする)ABC117 : C - Streamline
- (set::countを使いたい)ABC022 : B - Bumble Bee
- (グループを自分で定義しておく)ABC062 : A - Grouping
setを使う問題
- CR606(div.2) : Problem - B - Codeforces
素因数分解を使う問題
おわりに
日々、精進したい。