AtCoder青になるまでにやったこと
今日は競技プログラミングの話です。
先日のAtCoder Grand Contest 028で、（pythonで300点問題を早解きしたら）青coderになることができました。
この機会に、今までにやったことをまとめてみます。
ABC/ARC/AGCの400～600点問題を埋めた
5月くらいにAtCoderにハマり、ひたすら過去問を解いていた時期がありました（AtCoder ProblemsやAtCoder Scoresは便利ですね。）
過去問を埋めていると、同じ得点帯の問題を解くのに必要な知識や考え方が分かってきます。
400点くらいの問題を安定して（8～9割くらい）、あわよくば早く解ければ青になれるようです（なれました）
400点～600点の問題を解くために必要だった知識
・累積和、いもす法
・しゃくとり法
・modの世界での四則演算
・Union-Find木
・ダイクストラ法、ベルマンフォード法、ワーシャルフロイド法
・bisectを使った二分探索
・bit演算
・素因数分解のアルゴリズム
・素数列挙のアルゴリズム
・組み合わせの数nCrを計算するアルゴリズム
・高校数学（最小公倍数と最大公約数の性質、等差数列の和、重複を許す組み合わせの数など）
・各アルゴリズムの計算量
・pythonのあれやこれや
だいたいこんな感じだと思います。
コンテストに出て考えて何もわからず解説読んで知らないアルゴリズムが使われてると「は～～～～～～」ってなるので、とりあえず知識は身につけておきたいです。
pythonのあれやこれや
データ構造系
・set （集合型。C++でのstd::unordered_set）
・collections.deque （両側キュー）
・heapq （優先度付きキュー）
・collections.defaultdict （デフォルトの値を決められる辞書型）
便利系
・pow(a, b, m) （aのb乗をmで割った余りを求めてくれる）
・fractions.gcd() （最小公倍数を求めてくれる）
・itertools.product() （直積を求めてくれる）
・itertools.permutations() （順列を全列挙してくれる）
400点～600点の問題を解くのに必要だった考え方
・計算量を意識する（制限時間に間に合うようにするのはもちろんだけど，過度に高速にしようとしないのも重要）
・3つの点を求める問題は、真ん中を固定してみる
・複数の操作が行われる問題は、操作をゴールから逆順に考えてみる
・マンハッタン距離が出てくる問題は、座標を45度回転させてみる（x'=x+y, y'=x-y）
・絶対値の和を小さくする問題は、中央値が使えないか考えてみる
考え方の言語化はむずかしい…
黄色に向けて
700点問題がまあまあの確率で解けるようになれば黄色になれるらしいです。
700点問題になると解くのに必要な知識が増えてきます（動的計画法とかBinary Indexed Treeとか）。まだ過去問を全然埋められていないので、そこからやっていこうと思います。
また、700点問題になるとpythonの実行速度では辛くなることがあるようです。10^7回もループ回せないしもっと早くなるんだろうと考察してたのにそれが想定解で「は～～～～～～」ってなったりします。pythonは素早く書けるので難易度の低い問題には向いていますが、実行制限時間に間に合わなくてはどうにもなりません。しかたないのでちょっとずつC++も勉強していきます（つらい）
