9
11

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2021-05-02

はじめに

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


(2021/10/25)入緑しました!
image.png

数問

・座標系

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

論理演算系

AtCoder Beginner Contest 189 D - Logical Expression

AtCoder Beginner Contest 171 E - Red Scarf

二分探索

AtCoder Beginner Contest 205 D - Kth Excluded

座標圧縮

AtCoder Beginner Contest 213 C - Reorder Cards

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

  • 1度も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)

9
11
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
9
11

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?