精進したAtCoderの問題を分類する(〜rating800) #AtCoder

はじめに

精進の過程で苦手なパターンを洗い出し、まとめることでパフォを安定させることを目的としてこの記事を書いています。筆者は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

heap

・AtCoder Beginner Contest 212 D - Querying Multiset
- クエリ操作を実現する方法を思いつくのがしんどかった

動的計画法(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)

精進したAtCoderの問題を分類する(〜rating800)