はじめに

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

（2021/10/25）入緑しました！

数問

・座標系

・ZONeエナジープログラミングコンテスト “HELLO SPACE” B - 友好の印

・AtCoder Beginner Contest 218 D - Rectangles

座標上の点の組み合わせを全探索します

・AtCoder Beginner Contest 224 C - Triangle?

座標上の3点を全探索する問題。

・エラトステネスの篩

・AtCoder Beginner Contest 215 D - Coprime 2

・その他

・AtCoder Beginner Contest 131 C - Anti-Division

・AtCoder Beginner Contest 162 C - Sum of gcd of Tuples (Easy)

Python ユーザーは PyPy3を使わないとTLEになります。

N進数

・パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）C - Unlucky 7

文字列系

・ZONeエナジープログラミングコンテスト “HELLO SPACE” A - UFO襲来

・ZONeエナジープログラミングコンテスト “HELLO SPACE” D - 宇宙人からのメッセージ

・AtCoder Beginner Contest 199（Sponsored by Panasonic） C - IPFL

・AtCoder Beginner Contest 158 D - String Formation

計算量に注意してライブラリを使用しましょう(collections)

リスト計算量削減系

・AtCoder Beginner Contest 206（Sponsored by Panasonic） C - Swappable

・京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）C - Ringo's Favorite Numbers

・AtCoder Beginner Contest 187 D - Choose Me
　- O(NlogN)で解ける方法を考えましょう

・AtCoder Beginner Contest 171 D - Replacing

・AtCoder Beginner Contest 185 D - Stamp
　- 必要な操作をO(N)で済ませる方法を考えれば難しくはありません。

いい感じのでデータ構造作る系

・AtCoder Beginner Contest 199（Sponsored by Panasonic） C - IPFL

いい感じのデータ構造を作りましょう。意外とシンプルです。(kyopro_firendsさんの回はいい感じのデータ構造系の問題が出題される傾向にある気がする)

・UNICORNプログラミングコンテスト2021(AtCoder Beginner Contest 225) D - Play Train

パッと見Union-Findで解けそうですが…、やりたい処理をしっかり考えてそれを実現できるデータ構造を作成しましょう。

累積和

・パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）　D - Sum of difference

・AtCoder Beginner Contest 182 D - Wandering

累積和問題にひとひねり加えられた問題で、実装するときに頭がこんがらがりました。落ち着いて解きましょう。

・AtCoder Beginner Contest 172 C - Tsundoku

累積和・二分探索

木

・AtCoder Beginner Contest 223 D - Restricted Permutation

トポロジカルソート

探索（DFS・BFS・UnionFind）

・AtCoder Beginner Contest 206（Sponsored by Panasonic） D - KAIBUNsyo

グラフ問題に落とし込むまでが難しいかもしれません。

・AtCoder Beginner Contest 204 C - Tour

問題を見て計算量を見積もれるようになりましょう

・AtCoder Beginner Contest 177 D - Friends

Union-Findの使いどころです

・AtCoder Beginner Contest 209 D - Collision

・AtCoder Beginner Contest 168 D - .. (Double Dots)

・ACL Beginner Contest C - Connect Cities

・AtCoder Beginner Contest 214 D - Sum of Maximum Weights

重さの小さい順にUnionFind

bit全探索

・AtCoder Beginner Contest 189 C - H and V

できるだけ短いコードを書くことでミスを減らせます。お勧めはbitシフトを使ったbit全探索です。

・AtCoder Beginner Contest 221 C - Select Mul

クエリ操作を実現する方法を思いつくのがしんどかった

動的計画法(DP)

・AtCoder Beginner Contest 189 D - Logical Expression

・AtCoder Beginner Contest 204 D - Cooking

部分和DP

・AtCoder Beginner Contest 220 D - FG operation

いもす法

・AtCoder Beginner Contest 183 D - Water Heater

・AtCoder Beginner Contest 188 D - Snuke Prime

上の問題が解ければ解法はすぐ思いつくはずです。しかし実装が少し難しいので緑diffとなっています。

・AtCoder Beginner Contest 221 D - Online games

セグメント木

・AtCoder Beginner Contest 217 D - Cutting Woods

コーナーケース回避系

・AtCoder Beginner Contest 157 C - Guess The Number

１度もWAを出さないようにしてみよう

PyPy3でないとTLEになる

・AtCoder Beginner Contest 189 C - Mandarin Orange

・三井住友信託銀行プログラミングコンテスト2019 D - Lucky PIN

・AtCoder Beginner Contest 162 C - Sum of gcd of Tuples (Easy)