精進したAtCoderの問題を分類する(rating~1200)

## はじめに

 <font color=43E0DF>水</font>コーダーになることを目標として精進の過程で苦手なパターンを洗い出し、まとめることでパフォを安定させることを目的としてこの記事を書いています。筆者はPythonと精進限定でC++で問題を解いています。解いた問題は随時本記事に追加していきます。

「どのジャンルの問題をどれくらい解いたか」を参考にしていただければと思います。
  
<font color="3EAF3E">緑</font>コーダーになるまでにまとめた問題集↓

[精進したAtCoderの問題を分類する(〜rating800)](https://qiita.com/dakkenkd425/items/66cc406fa1904c201c00)

__(2023/04/01)入水しました！！！__

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1311765/2a12a276-b369-7c54-b5fc-c8100a732b61.png)


AtCoder ProblemsのDifficulty Pies
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1311765/a5b1b937-ebb5-f1b5-50a2-e87a2f5ecd5c.png)


--------------------

## 二分探索
- [キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227) D - Project Planning](https://atcoder.jp/contests/abc227/tasks/abc227_d)
 青diffです 

- [AtCoder Beginner Contest 144 E - Gluttony](https://atcoder.jp/contests/abc144/tasks/abc144_e)
 少しエスパーが必要ですが、二分探索の良い練習になります。

- [AtCoder Regular Contest 050 B - 花束](https://atcoder.jp/contests/arc050/tasks/arc050_b)
判定問題をどう考えるか

- [AtCoder Beginner Contest 194 E - Mex Min](https://atcoder.jp/contests/abc194/tasks/abc194_e)
やはり判定問題を考えるのが難しいです…

- [AtCoder Beginner Contest 216 E - Amusement Park](https://atcoder.jp/contests/abc216/tasks/abc216_e)
 どのような判定問題に落とし込むかが難しい…
 「少なくともこれ以上はこれができる」みたいなイメージ？

- [AtCoder Beginner Contest 124 D - Handstand](https://atcoder.jp/contests/abc124/tasks/abc124_d) 
考察実装ともに数分で解けたのでOK

- [AtCoder Beginner Contest 146 C - Buy an Integer](https://atcoder.jp/contests/abc146/tasks/abc146_c)
判定に関してはO(1)でできるので、二分探索で解けます。

- [NECプログラミングコンテスト2021(AtCoder Beginner Contest 229) D - Longest X](https://atcoder.jp/contests/abc229/tasks/abc229_d)
尺取り法でも解けますが、二分探索でも解けます。
累積和を使った二分探索

- [AtCoder Beginner Contest 246 D - 2-variable Function](https://atcoder.jp/contests/abc246/tasks/abc246_d)
コンテスト中にACしました。尺取りでも解けるらしいです。尺取りで解けるものは決め打ち二分探索でも解けるのかも？

- [AtCoder Beginner Contest 203（Sponsored by Panasonic）D - Pond](https://atcoder.jp/contests/abc203/tasks/abc203_d)
「中央値をlimit以下にできるかどうか」というO(N)の判定問題で二分探索

- [日鉄ソリューションズプログラミングコンテスト2022（AtCoder Beginner Contest 257） D - Jumping Takahashi 2](https://atcoder.jp/contests/abc257/tasks/abc257_d)
「必要なジャンプ力の最小値」を求める問題。

- [AtCoder Regular Contest 144 B - Gift Tax](https://atcoder.jp/contests/arc144/tasks/arc144_b)
ARCの問題ですがかなり典型的な問題です。

- [UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269) E - Last Rook](https://atcoder.jp/contests/abc269/tasks/abc269_e)
インタラクティブ問題での二分探索

- [AtCoder Beginner Contest 296 D - M<=ab](https://atcoder.jp/contests/abc296/tasks/abc296_d)
246Dの類似問題。実家のような安心感。
積を取る問題がでたらまず絶対に片方を固定して探索範囲を絞れないか確認する!!!


### 三分探索

- [トヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279) D - Freefall](https://atcoder.jp/contests/abc279/tasks/abc279_d)
二分探索でも解けますが三分探索を理解するのにいい問題です

- [AtCoder Beginner Contest 240 F - Sum Sum Max](https://atcoder.jp/contests/abc240/tasks/abc240_f)
一般項を求めるのが難しい…

## DP
- [AtCoder Beginner Contest 224 E - Integers on Grid](https://atcoder.jp/contests/abc224/tasks/abc224_e)
（解説AC）青diffのDP。実装方法がためになる。

- [サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219） D - Strange Lunchbox](https://atcoder.jp/contests/abc219/tasks/abc219_d)
基本的なDPです。数をオーバーする時の扱いが勉強になりました。

- [EDPC F - LCS](https://atcoder.jp/contests/dp/tasks/dp_f)
（解説AC）Longest Common Substringです。かつっぱさんの動画を見ながら解説ACしました。

- [EDPC G - Longest Path](https://atcoder.jp/contests/dp/tasks/dp_g)
グラフのDPです

- [EDPC H - Grid 1](https://atcoder.jp/contests/dp/tasks/dp_h)
BFSでDP

- [EDPC P - Independent Set](https://atcoder.jp/contests/dp/tasks/dp_p)
DFSでDP(DFSしなくてもできるけど)

- [競プロ典型 90 問 042 - Multiple of 9（★4）](https://atcoder.jp/contests/typical90/tasks/typical90_ap)
桁の最後に1~9の数を使ったときに総和がk-i(i=1,…,9)の通り数が求まっていればk-i+iとなる通り数が分かる

- [EDPC I - Coins](https://atcoder.jp/contests/dp/tasks/dp_i)
確率です

- [競プロ典型 90 問 035 - Preserve Connectivity（★7）](https://atcoder.jp/contests/typical90/tasks/typical90_ai)
かつっぱさんの動画を参考にしました
LCAを使ってDPをしていきます

- [M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232) E - Rook Path](https://atcoder.jp/contests/abc232/tasks/abc232_e)
こういった問題を本番で解けるようになりたい

- [AtCoder Beginner Contest 242 E - (∀x∀)](https://atcoder.jp/contests/abc242/tasks/abc242_e)
桁でなんとかする。最後の場合分が謎

- [AtCoder Beginner Contest 244 E - King Bombee](https://atcoder.jp/contests/abc244/tasks/abc244_e)
コンテスト中にACしました。最初の思いついた方針があってたっぽいけど遷移を考えるときにミスったっぽい。

- [AtCoder Beginner Contest 212 E - Safety Journey](https://atcoder.jp/contests/abc212/tasks/abc212_e)
制約に注目。ある程度エスパーして考察するのもいいかもしれない。

- [AtCoder Beginner Contest 178 D - Redistribution](https://atcoder.jp/contests/abc178/tasks/abc178_d)
次のDPの遷移を考えるときに必要な値をメモしてO(1)で求められるようにしておく。（メモ化のきもちが少しわかったかも）

- [AtCoder Beginner Contest 207 E - Mod i](https://atcoder.jp/contests/abc207/tasks/abc207_e)
累積和と余りを利用して、メモ化しながらDPをしていきます。難しいです。解説を理解するだけでかなり時間がかかりましたが、このような問題を解いてレートを爆上げしたい。

- [AtCoder Beginner Contest 247 F - Cards](https://atcoder.jp/contests/abc247/tasks/abc247_f)
隣り合うものどちらかの辺を選ばないといけないという制約のもと、その通り数を数えていく。

- [AtCoder Beginner Contest 183 E - Queen on Grid](https://atcoder.jp/contests/abc183/tasks/abc183_e)
grid上をDPしていく問題。累積和を縦横斜めそれぞれ別の二次元配列で管理するところがポイント。
最初BFSと考えたが、累積和と気付いてそこからDPを考えた。ある点の値が確定する瞬間に検討をつけて遷移を考える。

- [AtCoder Beginner Contest 153 E - Crested Ibis vs Monster](https://atcoder.jp/contests/abc153/tasks/abc153_e)
制約をしっかりみると基本的なDPであることがわかります。ナップザックDPっぽい雰囲気を感じ取ってACしました。

- [AtCoder Beginner Contest 234 F - Reordering](https://atcoder.jp/contests/abc234/tasks/abc234_f)
遷移は自力で思いついたのでOK。combinationをメモ化で求めておく方法が参考になった。

- [ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248） F - Keep Connect](https://atcoder.jp/contests/abc248/tasks/abc248_f)
連結状態を持つDP。答えを見てみると非常にシンプルだがかなり難しかった…

- [AtCoder Beginner Contest 145 E - All-you-can-eat](https://atcoder.jp/contests/abc145/tasks/abc145_e)
基本的なDP。今なら緑diffだろうなあ…

- [京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200） D - Happy Birthday! 2](https://atcoder.jp/contests/abc200/tasks/abc200_d)
部分和問題

- [AtCoder Beginner Contest 135 D - Digits Parade](https://atcoder.jp/contests/abc135/tasks/abc135_d)
Mod i を理解していれば簡単です。

- [NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253） E - Distance Sequence](https://atcoder.jp/contests/abc253/tasks/abc253_e)
緑上位diffのDPです。高速化の方法をすぐ思いつけたので本番ACできました。

- [AtCoder Beginner Contest 261 D - Flipping and Bonus](https://atcoder.jp/contests/abc261/tasks/abc261_d)

- [第三回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 262）D - I Hate Non-integer Number](https://atcoder.jp/contests/abc262/tasks/abc262_d)
実行制限時間が2.5秒でいつもより0.5秒長い

- [AtCoder Beginner Contest 265 E - Warp](https://atcoder.jp/contests/abc265/tasks/abc265_e)
細かい高速化を挟めばPythonでもギリギリ辞書型で通せる

- [AtCoder Beginner Contest 266 D - Snuke Panic (1D)](https://atcoder.jp/contests/abc266/tasks/abc266_d)

- [NECプログラミングコンテスト2022 (AtCoder Beginner Contest 267) D - Index × A(Not Continuous ver.)](https://atcoder.jp/contests/abc267/tasks/abc267_d)
レートを上げるにはDPが解けないといけない

- [京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271) E - Subsequence Path](https://atcoder.jp/contests/abc271/tasks/abc271_e)
求めたいものをしっかりと把握しよう

- [キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274） D - Robot Arms 2](https://atcoder.jp/contests/abc274)
問題文をしっかり読んで理解しよう

- [AtCoder Beginner Contest 133 E - Virus Tree 2](https://atcoder.jp/contests/abc133/tasks/abc133_e)
木DPです。

- [AtCoder Beginner Contest 275 F - Erase Subarrays](https://atcoder.jp/contests/abc275/tasks/abc275_f)
PythonでTLEしましたが、DP配列を全て１次元に分解すると通りました。

- [AtCoder Beginner Contest 215 E - Chain Contestant](https://atcoder.jp/contests/abc215/tasks/abc215_e)
小さい制約に気を付けてDPする。bitで状態を持つDP。

- [AtCoder Beginner Contest 285 E - Work or Rest](https://atcoder.jp/contests/abc285/tasks/abc285_e)
手で色々なケースを書いてみることが大事。

- [ユニークビジョンプログラミングコンテスト2022 冬(AtCoder Beginner Contest 283) E - Don't Isolate Elements](https://atcoder.jp/contests/abc283/tasks/abc283_e)
めちゃくちゃ実装が重い。

- [Ｓｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 289）E - Swap Places](https://atcoder.jp/contests/abc289/tasks/abc289_e)
「状態」のDP。状態の発想が出てこなかった。



## グラフ

### BFS
- [AtCoder Beginner Contest 224 D - 8 Puzzle on Graph](https://atcoder.jp/contests/abc224/tasks/abc224_d)
状態遷移をBFSする問題。いろいろテクニックが必要なので難しい。

- [AtCoder Beginner Contest 151 D - Maze Master](https://atcoder.jp/contests/abc151/tasks/abc151_d)
グリッド上のBFS。目標時間２０分。

- [AtCoder Beginner Contest 146 D - Coloring Edges on Tree](https://atcoder.jp/contests/abc146/tasks/abc146_d)
BFSで解きました。

- [EDPC H - Grid 1](https://atcoder.jp/contests/dp/tasks/dp_h)
BFSでDP

- [AtCoder Beginner Contest 176 D - Wizard in Maze](https://atcoder.jp/contests/abc176/tasks/abc176_d)
ワープ後に塗り替えられる可能性を考慮してBFSをする
結構良い問題で好きです

- [AtCoder Beginner Contest 184 E - Third Avenue](https://atcoder.jp/contests/abc184/tasks/abc184_e)
ワープする系BFSでした。
queueに突っ込むタイミングに少し迷いましたが、BFSの性質を理解してそのまま実装すれば難しくはありません。

- [AtCoder Beginner Contest 246 E - Bishop 2](https://atcoder.jp/contests/abc246/tasks/abc246_e)
（解説AC）枝刈りBFSをしました。01BFSよりも考え方が簡単な気がします。（[参考解説記事](https://qiita.com/u2dayo/items/4896cea07b59c707df3a#e%E5%95%8F%E9%A1%8Cbishop-2)）

- [AtCoder Beginner Contest 213 E - Stronger Takahashi](https://atcoder.jp/contests/abc213/tasks/abc213_e)
01BFSです。その場所から壁を破壊して到達できる区画だけを+1してappendする。distでしっかりqueueに突っ込まない場合分けを書くのがポイント。

- [AtCoder Beginner Contest 160 D - Line++](https://atcoder.jp/contests/abc160/tasks/abc160_d)
BFSをN回できるのがポイント。組み合わせを全探索する。

- [AtCoder Beginner Contest 188 E - Peddler](https://atcoder.jp/contests/abc188/tasks/abc188_e)
トポロジカルソートでも解けますが、普通のBFSでも解けます
X_i < Y_i という制約からDAGになるとういことが言えるそうです

- [AtCoder Beginner Contest 272 D - Root M Leaper](https://atcoder.jp/contests/abc272/tasks/abc272_d)
飛ぶ座標の位置は限られている

### DFS
- [AtCoder Beginner Contest 138 D - Ki](https://atcoder.jp/contests/abc138/tasks/abc138_d)
基本的なDFS。再帰でPyPy3を使うとTLEしてしまうので注意！

- [AtCoder Beginner Contest 198 E - Unique Color](https://atcoder.jp/contests/abc198/tasks/abc198_e)
BFSしようとするとそのつど配列を作り直さないといけないのでTLEになります。

- [AtCoder Beginner Contest 236 D - Dance](https://atcoder.jp/contests/abc236/tasks/abc236_d)
計算量の見積もりが難しいDFSです。常に小さい値を選択する工夫がないとTLEになります。
このような問題だと、__再帰の深さが浅いので、PythonではTLEになりますがPyPyだとACできます__。特殊な例なので注意。

- [AtCoder Beginner Contest 220 F - Distance Sums 2](https://atcoder.jp/contests/abc220/tasks/abc220_f)
（解説AC）部分木を求めた後に答えを求めていきます。これはDP？

- [EDPC P - Independent Set](https://atcoder.jp/contests/dp/tasks/dp_p)
DFSで部分木に対する情報をまとめていく

- [エクサウィザーズプログラミングコンテスト2021（AtCoder Beginner Contest 222）E - Red and Blue Tree](https://atcoder.jp/contests/abc222/tasks/abc222_e)
制約をしっかり見ればDFSできることに気付けます

- [デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239） E - Subtree K-th Max](https://atcoder.jp/contests/abc239/tasks/abc239_e)
制約をよく見ましょう

- [AtCoder Beginner Contest 240 E - Ranges on Tree](https://atcoder.jp/contests/abc240/tasks/abc240_e)
コンテスト中に５完できて初めて水パフォが出せました！！！

- [AtCoder Beginner Contest 054 C - One-stroke Path](https://atcoder.jp/contests/abc054/tasks/abc054_c)
Nが非常に小さいことからシンプルにDFSをするだけでできます
8!は5040通りで非常に小さい。パスの種類の上限は2~Nの順列の個数。

- [競プロ典型 90 問 072 - Loop Railway Plan（★4）](https://atcoder.jp/contests/typical90/tasks/typical90_bt)
グリッドの範囲がかなり狭いのでDFSで全探索をします

- [AtCoder Beginner Contest 266 F - Well-defined Path Queries on a Namori](https://atcoder.jp/contests/abc266/tasks/abc266_f)
向きのないFunctional Graphはなもりグラフというらしい？

- [ユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268) D - Unique Username](https://atcoder.jp/contests/abc268/tasks/abc268_d)
小さい制約に注目しましょう

- [トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270) C - Simple path](https://atcoder.jp/contests/abc270/tasks/abc270_c)
DFSで探索するかBFSで経路復元するか
色々な解き方があるのでチェックしておこう

- [AtCoder Beginner Contest 133 E - Virus Tree 2](https://atcoder.jp/contests/abc133/tasks/abc133_e)
DFSで組み合わせを求める。

- [AtCoder Beginner Contest 278 F - Shiritori](https://atcoder.jp/contests/abc278/tasks/abc278_f)

### Union-Find
- [NECプログラミングコンテスト2021(AtCoder Beginner Contest 229) E - Graph Destruction](https://atcoder.jp/contests/abc229/tasks/abc229_e)
グラフの分割は逆からUnion-Find

- [AtCoder Beginner Contest 226 E - Just one](https://atcoder.jp/contests/abc226/tasks/abc226_e)
閉路判定は頂点の数>=辺の数
単純な閉路判定だけならUnionFindだけで可能

- [デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239） F - Construct Highway](https://atcoder.jp/contests/abc239/tasks/abc239_f)
(解説AC)次数の問題です。UFの使い方が参考になりました。

- [freee プログラミングコンテスト2022（AtCoder Beginner Contest 264）E - Blackout 2](https://atcoder.jp/contests/abc264/tasks/abc264_e)
逆からUnion-Find
発電所をまとめておくという発想で実装を楽にできる

- [UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269) D - Do use hexagon grid](https://atcoder.jp/contests/abc269/tasks/abc269_d)
10分で解けるようにしよう

- [トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270) F - Transportation](https://atcoder.jp/contests/abc270/tasks/abc270_f)
空港と港をそれぞれ別の頂点を追加して管理することでクラスカル法を適用することができる
頂点を追加する実装方法は典型？

- [HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282) E - Choose Two and Eat One](https://atcoder.jp/contests/abc282/tasks/abc282_e)
考察メインで分かればあとはやるだけ

- [AtCoder Beginner Contest 157 D - Friend Suggestions](https://atcoder.jp/contests/abc157/tasks/abc157_d)
考察しましょう


### 最短経路問題

#### ダイクストラ
- [AtCoder Beginner Contest 237 E - Skiing](https://atcoder.jp/contests/abc237/tasks/abc237_e)
ポテンシャルという概念が必要です。難しいです。水色下位のdiffじゃないです。
- [SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) E - Train](https://atcoder.jp/contests/abc192/tasks/abc192_e)
シンプルなダイクストラです。実装する際にミスをしてTLEを連発したのでちゃんとしたダイクストラを使えるようになりましょう。([ダイクストラ法のよくあるミス](https://snuke.hatenablog.com/entry/2021/02/22/102734))

- [AtCoder Beginner Contest 252 E - Road Reduction](https://atcoder.jp/contests/abc252/tasks/abc252_e)
コンテスト中にダイクストラであることに気づけませんでした

- [AtCoder Beginner Contest 191 E - Come Back Quickly](https://atcoder.jp/contests/abc191/tasks/abc191_e)
有向辺をひっくり返したりゴールの頂点を新しく作ったりなど

#### ワーシャルフロイド

- [AtCoder Beginner Contest 208 D - Shortest Path Queries 2](https://atcoder.jp/contests/abc208/tasks/abc208_d)
ワーシャルフロイド

- [AtCoder Beginner Contest 073 D - joisino's travel](https://atcoder.jp/contests/abc073/tasks/abc073_d)
小さい制約に注目してみましょう

- [AtCoder Beginner Contest 079 D - Wall](https://atcoder.jp/contests/abc079/tasks/abc079_d)
やるだけワーシャルフロイド

- [AtCoder Beginner Contest 243 E - Edge Deletion](https://atcoder.jp/contests/abc243/tasks/abc243_e)
ワーシャルフロイドまでは一瞬で思いついたのですが、辺の削除がわかりませんでした。

- [ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)](https://atcoder.jp/contests/abc286/tasks/abc286_e)
24分で本番AC
制約からエスパーしてDPの要領で答えを求めました。

### トポロジカルソート
- [AtCoder Beginner Contest 223 D - Restricted Permutation](https://atcoder.jp/contests/abc223/tasks/abc223_d)
やるだけトポロジカルソートです。これを機にライブラリ化しておきましょう。

- [EDPC G - Longest Path](https://atcoder.jp/contests/dp/tasks/dp_g)
DAGであるということがポイントになります

- [AtCoder Beginner Contest 291（Sponsored by TOYOTA SYSTEMS）E - Find Permutation](https://atcoder.jp/contests/abc291/tasks/abc291_e)
トポロジカル順が一意に決まるかどうかを判定する

### 強連結成分分解
- [競プロ典型 90 問 021 - Come Back in One Piece（★5）](https://atcoder.jp/contests/typical90/tasks/typical90_u)
DFSやら帰りがけ順やらで強連結成分分解をします

- [東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）E - Takahashi's Anguish](https://atcoder.jp/contests/abc256/tasks/abc256_e)
図を書いて、使えそうな良い性質があるかどうか考えてみましょう。
コンテスト中にACできました。

- [AtCoder Beginner Contest 296 E - Transition Game](https://atcoder.jp/contests/abc296/tasks/abc296_e)
この問題で入水を決定づけることができました。

### bitDP
- [キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274） E - Booster](https://atcoder.jp/contests/abc274/tasks/abc274_e)
前計算できるものはしておきましょう。

### 構築
- [デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239） F - Construct Highway](https://atcoder.jp/contests/abc239/tasks/abc239_f)
(解説AC)次数の問題です。難しい…
- [AtCoder Beginner Contest 131 E - Friendships](https://atcoder.jp/contests/abc131/tasks/abc131_e)
(解説AC)自力ACすべきだったと思いました…
「最大最小を考えてその中の任意の値に対応できるか」を考えるといいかも。おそらく最大最小内はできるものが多そう

### その他
- [パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 273） E - Notebook](https://atcoder.jp/contests/abc273/tasks/abc273_e)
終了間際にグラフに落とし込めそうと思ったけど実装まではいかなかった
面白い問題です


## BIT(Binary Indexed Tree)
- [AtCoder Beginner Contest 221 E - LEQ](https://atcoder.jp/contests/abc221/tasks/abc221_e)
BITの使い方や逆元の使い方などを学べたので非常に教育的な良問だと思っています。
(参考記事：[解説](https://rosso01.hatenablog.com/entry/2021/10/04/065018)・ [BIT](https://scrapbox.io/pocala-kyopro/BIT)・[逆元](https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#3-2-mod-p-%E3%81%AB%E3%81%8A%E3%81%91%E3%82%8B%E9%80%86%E5%85%83)・[Fermatの小定理](https://qiita.com/drken/items/6b4031ccbb2cab7436f3) )

- [パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231) F - Jealous Two](https://atcoder.jp/contests/abc231/tasks/abc231_f)
もうちょっとで解けそうだった…

- [AtCoder Beginner Contest 241（Sponsored by Panasonic） D - Sequence Query](https://atcoder.jp/contests/abc241/tasks/abc241_d)
クエリ先読みで使う数値をあらかじめ決めて座標圧縮したあとBITでクエリを処理していく
tatyamさんの[SortedMultiset](https://github.com/tatyam-prime/SortedSet)でも解けます!

## SegmentTree
- [トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228) D - Linear Probing](https://atcoder.jp/contests/abc228/tasks/abc228_d)
セグ木で殴ってみたい人におすすめです

- [AtCoder Beginner Contest 157 E - Simple String Queries](https://atcoder.jp/contests/abc157/tasks/abc157_e)
殴れます

- [AtCoder Beginner Contest 179 D - Leaping Tak](https://atcoder.jp/contests/abc179/tasks/abc179_d)
区間取得一点更新のセグ木でDPを高速化

- [AtCoder Beginner Contest 281 E - Least Elements](https://atcoder.jp/contests/abc281/tasks/abc281_e)
セグ木とSortedMultisetどちらを使っても解けます。
後者のほうが実装が簡単です。

__遅延評価セグメント木__
- [競プロ典型 90 問 029 - Long Bricks（★5）](https://atcoder.jp/contests/typical90/tasks/typical90_ac)
遅延評価をするためには、実現したい操作を線形変換で表現する必要があるそうです。ライブラリは[ACL-for-python](https://github.com/shakayami/ACL-for-python)のものを借りました。

## しゃくとり法

- [AtCoder Beginner Contest 250 E - Prefix Equality](https://atcoder.jp/contests/abc250/tasks/abc250_e)
比較する場面は集合の大きさが同じ時だけ
Zobrist hashで解く方法もあるそうです

- [AtCoder Beginner Contest 250 F - One Fourth](https://atcoder.jp/contests/abc250/tasks/abc250_f)
(解説AC)幾何の問題です。かつっぱ先生の動画を見ていると色々勉強になります。。

## 貪欲
- [AtCoder Beginner Contest 137 D - Summer Vacation](https://atcoder.jp/contests/abc137/tasks/abc137_d)
（解説AC）制約がキツい方から考える

- [AtCoder Beginner Contest 245 E - Wrapping Chocolat](https://atcoder.jp/contests/abc245/tasks/abc245_e)
SortedMultisetで解きました。「制約のキツい方から考える」「片側を固定する」で縦に余裕のある箱のうち、一番横幅がキツくなるものを順番に当てはめていくと良い。

 

## 距離
- [AtCoder Beginner Contest 102 C - Linear Approximation](https://atcoder.jp/contests/abc102/tasks/arc100_a)
マンハッタン距離の最小化は中央値

- [AtCoder Beginner Contest 178 E - Dist Max](https://atcoder.jp/contests/abc178/tasks/abc178_e)
マンハッタン距離の最小化は45度回転してx+y,x-yそれぞれの中での絶対値の大きい方

- [競プロ典型 90 問 070 - Plant Planning（★4）](https://atcoder.jp/contests/typical90/tasks/typical90_br)
中央値で最小化


## bit
- [モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 238） D - AND and SUM](https://atcoder.jp/contests/abc238/tasks/abc238_d)
エスパーで本番通しました。bitごとに考えてみましょう

- [AtCoder Beginner Contest 185 F - Range Xor Query](https://atcoder.jp/contests/abc185/tasks/abc185_f)
XORの性質を考えるとあるデータ構造が使えることが分かります

- [AtCoder Beginner Contest 117 D - XXOR](https://atcoder.jp/contests/abc117/tasks/abc117_d)
制約に注意しましょう

- [AtCoder Beginner Contest 147 D - Xor Sum 4](https://atcoder.jp/contests/abc147)

- [AtCoder Beginner Contest 242 D - ABC Transform](https://atcoder.jp/contests/abc242/tasks/abc242_d)
（解説AC）周期性を見つける
二分木の前からK番目は2進数にして0だと左1だと右に進む(みたいな(よくわからないです…))

- [AtCoder Beginner Contest 261 E - Many Operations](https://atcoder.jp/contests/abc261/tasks/abc261_e)
これもなかなか面白い問題
indexを入力の情報として出力を配列の中身にするとうまく実装できる

- [AtCoder Beginner Contest 295 D - Three Days Ago](https://atcoder.jp/contests/abc295/tasks/abc295_d)
ひとつひとつの文字列の種類は0~9なのでbitで状態をもつことができる。
「偶奇を持てばよい」、「bitで管理できる」という発想が必要。



## ゲーム系
- [トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270) D - Stones](https://atcoder.jp/contests/abc270/tasks/abc270_d)

- [EDPC K - Stones](https://atcoder.jp/contests/dp/tasks/dp_k)

- [AtCoder Beginner Contest 278 F - Shiritori](https://atcoder.jp/contests/abc278/tasks/abc278_f)

## Sparse Table
- [HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282) F - Union of Two Sets](https://atcoder.jp/contests/abc282/tasks/abc282_f)
すごく教育的な問題なので聞いたことがない人はぜひこの問題で履修してみてください。

## Mo's algorithm
- [AtCoder Beginner Contest 293 G - Triple Index](https://atcoder.jp/contests/abc293/tasks/abc293_g)
Kiriさんのコードからライブラリを窃盗してしまいました（自白）

- [AtCoder Beginner Contest 242 G - Range Pairing Query](https://atcoder.jp/contests/abc242/tasks/abc242_g)
Pythonだと遅くて高速化に工夫が必要
入力が多いため入力の高速化や、状態遷移の高速化を行った

## 二次元累積和
- [AtCoder Beginner Contest 106 D - AtCoder Express 2](https://atcoder.jp/contests/abc106/tasks/abc106_d)
Nが小さいときは考えるといいかも

## 二次元いもす法
- [典型90問 028 - Cluttered Paper（★4）](https://atcoder.jp/contests/typical90/tasks/typical90_ab)

## 数学問題

__幾何__
- [ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248）E - K-colinear Line](https://atcoder.jp/contests/abc248/tasks/abc248_e)
割り算ではなく掛け算で同じ直線上にあるかを判定するという典型テクニック。
あとは同じ点をカウントしないように数えればOK。

- [AtCoder Beginner Contest 250 F - One Fourth](https://atcoder.jp/contests/abc250/tasks/abc250_f)
(解説AC)幾何の問題です。かつっぱ先生の動画を見ていると色々勉強になります。。

- [AtCoder Beginner Contest 259 D - Circumferences](https://atcoder.jp/contests/abc259/tasks/abc259_d)
円の問題です。2つの円が交わっているかどうかの判定をしましょう。
判定方法をライブラリ化しておけば安心ですね


__包除原理__
- [AtCoder Beginner Contest 206（Sponsored by Panasonic） E - Divide Both](https://atcoder.jp/contests/abc206/tasks/abc206_e)
約数系包除原理です

- [AtCoder Beginner Contest 246 F - typewriter](https://atcoder.jp/contests/abc246/tasks/abc246_f)
この問題で包除原理を理解しました。

- [NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253） D - FizzBuzz Sum Hard](https://atcoder.jp/contests/abc253/tasks/abc253_d)
知識がある人からすると自明なのでしょうが、僕はだめでした…

__鳩の巣原理__
- [AtCoder Beginner Contest 174 C - Repsept](https://atcoder.jp/contests/abc174/tasks/abc174_c)
全くわかりませんでした…。漸化式立てたりmodで考えたりする発想が難しい。。

__GCD__
- [AtCoder Beginner Contest 125 C - GCD on Blackboard](https://atcoder.jp/contests/abc125/tasks/abc125_c)

__フェルマーの小定理__
- [トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228) E - Integer Sequence Fair](https://atcoder.jp/contests/abc228/tasks/abc228_e)

- [AtCoder Beginner Contest 034 C - 経路](https://atcoder.jp/contests/abc034/tasks/abc034_c)
大きい数のcombinationの方法を学びました

- [AtCoder Beginner Contest 156 D - Bouquet](https://atcoder.jp/contests/abc156/tasks/abc156_d)
pow()がポイントです（逆元）


__約数＆素数__
- [AtCoder Beginner Contest 142 D - Disjoint Set of Common Divisors](https://atcoder.jp/contests/abc142/tasks/abc142_d)
公約数の中からある性質の数を高速に求める問題です

- [AtCoder Beginner Contest 172 D - Sum of Divisors](https://atcoder.jp/contests/abc172/tasks/abc172_d)
(解説AC)maspyさんの[解説記事](https://maspypy.com/atcoder-%e5%8f%82%e5%8a%a0%e6%84%9f%e6%83%b3-2020-06-27abc-172#toc4)を見ましたが計算量の見積もりが難しいです……

- [AtCoder Beginner Contest 125 C - GCD on Blackboard](https://atcoder.jp/contests/abc125/tasks/abc125_c)
dictを使って高速化しました

- [AtCoder Beginner Contest 112 D - Partition](https://atcoder.jp/contests/abc112/tasks/abc112_d)
まず条件が成り立つ時を考えてからそれを満たす状態を全探索。

- [AtCoder Beginner Contest 254 D - Together Square](https://atcoder.jp/contests/abc254/tasks/abc254_d)
難しいです。片方を固定してもう片方をどうやって高速に求めるかを考えました。

- [AtCoder Beginner Contest 259 E - LCM on Whiteboard](https://atcoder.jp/contests/abc259/tasks/abc259_e)
条件をしっかり確認。Eの水diffとしては簡単な方？

__mod__
- [AtCoder Beginner Contest 164 D - Multiple of 2019](https://atcoder.jp/contests/abc164/tasks/abc164_d)
余りが重要になってくる。それくらいしか言うことがない。

__期待値__
- [AtCoder Beginner Contest 266 E - Throwing the Die](https://atcoder.jp/contests/abc266/tasks/abc266_e)
期待値DPらしいですが難しいです…

- [デンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280) E - Critical Hit](https://atcoder.jp/contests/abc280/tasks/abc280_e)
典型的な期待値DPです。[こちらのページ](https://compro.tsutaj.com//archive/180220_probability_dp.pdf)が参考になります。

- [LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263） E - Sugoroku 3](https://atcoder.jp/contests/abc263/tasks/abc263_e)
上の問題を解いてからみると理解できました。

__その他__
- [AtCoder Beginner Contest 233 E - Σ[k=0..10^100]floor(X／10^k)](https://atcoder.jp/contests/abc233/tasks/abc233_e)
下の桁から決定していく。

- [AtCoder Beginner Contest 245 D - Polynomial division](https://atcoder.jp/contests/abc245/tasks/abc245_d)
多項式の割り算です。頭がバグりました。pythonには便利なライブラリがあるそうです。


## ダブリング
- [AtCoder Beginner Contest 241（Sponsored by Panasonic） E - Putting Candies](https://atcoder.jp/contests/abc241/tasks/abc241_e)
参考記事：https://algo-logic.info/doubling/

- [AtCoder Beginner Contest 167 D - Teleporter](https://atcoder.jp/contests/abc167/tasks/abc167_d)
周期性のある問題をダブリングで解く

- [AtCoder Beginner Contest 179 E - Sequence Sum](https://atcoder.jp/contests/abc179/tasks/abc179_e)
けんちょんさんの[解説記事](https://drken1215.hatenablog.com/entry/2020/09/20/091500)を参考にしました

- [AtCoder Beginner Contest 136 D - Gathering Children](https://atcoder.jp/contests/abc136/tasks/abc136_d)
この問題は答えがある一つの場所に収束するため、最終的な答えの求め方が特殊でした

- [競プロ典型 90 問 058 - Original Calculator（★4）](https://atcoder.jp/contests/typical90/tasks/typical90_bf)
ダブリング！！！

- [AtCoder Beginner Contest 293 E - Geometric Progression](https://atcoder.jp/contests/abc293/tasks/abc293_e)
数式を書いてみて考えることで方針が見えるかも

## 半分全列挙
- [京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271) F - XOR on Grid Path](https://atcoder.jp/contests/abc271/tasks/abc271_f)
「言われてみれば確かに…」な制約ですね

## 式変形系
- [AtCoder Beginner Contest 166 E - This Message Will Self-Destruct in 5s](https://atcoder.jp/contests/abc166/tasks/abc166_e)
等式を作り片方を固定して、もう片方の値を高速に求める

## 絶対に小数誤差許さないマン問題
- [AtCoder Beginner Contest 191 D - Circle Lattice Points](https://atcoder.jp/contests/abc191/tasks/abc191_d)
`Decimal.sqrt()`なるものがあるのを知りました。

## 四角形敷き詰める系問題
- [AtCoder Beginner Contest 062 C - Chocolate Bar](https://atcoder.jp/contests/abc062/tasks/arc074_a)
制約をちゃんと見れば解けるかも

- [AtCoder Beginner Contest 196 D - Hanjo](https://atcoder.jp/contests/abc196/tasks/abc196_d)
制約が小さいのでDFSをする

- [サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）E - Moat](https://atcoder.jp/contests/abc219/tasks/abc219_e)
制約が小さい！

- [AtCoder Beginner Contest 223 E - Placing Rectangles](https://atcoder.jp/contests/abc223/tasks/abc223_e)
３つの四角形の敷き詰め方は２通りしかないので向きと長さを変えて全探索する

## 考察典型
### 主客転倒
それぞれの要素がどれくらい関与しているかを数える
- [AtCoder Beginner Contest 148 E - Double Factorial](https://atcoder.jp/contests/abc148/tasks/abc148_e)


- [AtCoder Beginner Contest 151 E - Max-Min Sums](https://atcoder.jp/contests/abc151/tasks/abc151_e)

### 平面走査
- [ユニークビジョンプログラミングコンテスト2022 冬(AtCoder Beginner Contest 283) F - Permutation Distance](https://atcoder.jp/contests/abc283/tasks/abc283_f)
i, j の順序を考えて更新したり、大小を固定するなど

### Ad-hoc
- [AtCoder Beginner Contest 293 F - Zero or One](https://atcoder.jp/contests/abc293/tasks/abc293_f)
クソむずい。「こうすれば解ける」ということは分かるけど、なんでその条件が出てくるのか分からない。
解説に「こうしたい」「こういう気持ちになる」とか書いてくれれば嬉しいんだけどなぁ…


## 要早解き

### シミュレーション
- [ユニークビジョンプログラミングコンテスト2022 冬(AtCoder Beginner Contest 283) D - Scope](https://atcoder.jp/contests/abc283/tasks/abc283_d)
スタックを使ってシミュレーションする。
「スタックを使ってシミュレーションできないか」をまず考える、という癖をつけていてもいいかもしれない。

- [AtCoder Beginner Contest 294 E - 2xN Grid](https://atcoder.jp/contests/abc294/tasks/abc294_e)
イベントソートをした後に区間をうまいこと処理して数える
個人的に区間の処理が苦手なので練習する必要がある

### 全探索
- [キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227) C - Repsept](https://atcoder.jp/contests/abc227/tasks/abc227_c)
これはもっと早く解きたかった…

- [AtCoder Beginner Contest 129 D - Lamp](https://atcoder.jp/contests/abc129/tasks/abc129_d)
壁と壁の間の距離を計算する問題。両端に-1とw・hを置くと計算しやすい。
### 式変形系
- [AtCoder Beginner Contest 165 D - Floor Function](https://atcoder.jp/contests/abc165/tasks/abc165_d)
灰茶の時に比べ、「速い考察」が身に付いてきた気がする

- [AtCoder Beginner Contest 167 D - Teleporter](https://atcoder.jp/contests/abc167/tasks/abc167_d)
処理を紙に書き出して落ち着いて手順を考える

- [AtCoder Beginner Contest 108 C - Triangular Relationship](https://atcoder.jp/contests/abc108/tasks/arc102_a)
考察のスピードが必要。40分かかったがもう半分くらいで解きたい。

### 尺取り法
- [NECプログラミングコンテスト2021(AtCoder Beginner Contest 229) D - Longest X](https://atcoder.jp/contests/abc229/tasks/abc229_d)
バグらせない尺取り法をマスターしよう

- [AtCoder Beginner Contest 247 E - Max Min](https://atcoder.jp/contests/abc247/tasks/abc247_e)
壁を作ってその通り数を数えていくのですが、難しいです。左を固定して右を全部数える、を繰り返す。

### 累積和
- [AtCoder Beginner Contest 105 D - Candy Distribution](https://atcoder.jp/contests/abc105/tasks/abc105_d)
modと累積和を利用した問題です。考察のスピードを上げたい…
「右側を固定して、条件を満たす左端を高速に数え上げるテク」というキーワードを頭に入れておきたい

- [AtCoder Beginner Contest 181 E - Transformable Teacher](https://atcoder.jp/contests/abc181/tasks/abc181_e)
累積和で差の合計を持っておいて差分をO(1)で更新
20分くらいで解けるようになりたい……