정진된 AtCoder 문제 분류(~rating800)

소개

정진의 과정에서 서투른 패턴을 씻어내고 정리하는 것으로 파포를 안정시키는 것을 목적으로 이 기사를 쓰고 있습니다. 필자는 Python과 정진 한정으로 C++에서 문제를 해결하고 있습니다. 해결한 문제는 수시로 본 기사에 추가해 갑니다.

(2021/10/25)입록했습니다!

수문

· 좌표계

· ZONe 에너지 프로그래밍 콘테스트 “HELLO SPACE” B - 우호 표시

· AtCoder Beginner Contest 218 D - Rectangles
- 좌표상의 점 조합을 모두 탐색합니다.

· AtCoder Beginner Contest 224 C - Triangle?
- 좌표에서 세 점을 모두 탐색하는 문제.

・엘라토스테네스의 체

· 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 - 스탬프
- 필요한 조작을 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 - 친구
- 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
- 가능한 한 짧은 코드를 작성하여 실수를 줄일 수 있습니다. 추천은 비트 시프트를 사용한 비트 전체 탐색입니다.

· 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 - 온라인 게임

세그먼트 트리

· 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)