Educational Codeforces Round 137

대회 리뷰/Codeforces

hijkl2e 2022. 10. 22. 07:53

Dashboard - Educational Codeforces Round 137 (Rated for Div. 2) - Codeforces

codeforces.com

단순 수학

00:02 AC

단순 구현

00:05 AC

dp로 풀이하였다.

00:17 AC

그리디 풀이도 가능하고 dp 풀이보다 간단하다.

dp는 overkill이었다.

입력 데이터가 랜덤이라는 점을 이용하는 문제이다.

초반에 지문을 완전히 잘못 이해하였다.

대강 읽고 이러한 문제겠구나 하고 내 마음대로 판단한 것이 패착이었다.

00:33 WA

00:36 WA

00:45 WA

예제는 잘 나와서 코너 케이스만 찾고 있었다.

그러다가 지문을 다시 읽었는데 나 혼자 다른 문제를 풀고 있었다.

눈물을 흘리며 처음부터 다시 짰다.

01:06 AC

문제를 꼼꼼히 제대로 읽자.

대회 중에는 입력 데이터가 랜덤이라는 점을 100% 이용하지 못하였다.

때문에 조금 복잡하게 풀어서 대회 끝나고 새로 짰다.

이분 탐색 시도하다가 대회가 끝났다.

dp 풀이가 정석인 듯 한데 정말 경이롭다.

대회 중에 dp 문제라고 알려줬어도 못 풀었을 듯 하다.

~~Segment Tree로 풀이할 수 있다고 한다.~~

11월 4일 업솔빙하였다.

정해는 Segment Tree + 행렬인 듯 한데 행렬 없이 Lazy Propagation으로 해결할 수 있다.

잘 관찰해보면 각 인덱스에 대하여 마지막으로 등장한 시점만 중요하다는 것을 알 수 있다.

Pass