Educational Codeforces Round 138

대회 리뷰/Codeforces

hijkl2e 2022. 10. 24. 12:49

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

codeforces.com

단순 비교

00:02 AC

단순 그리디

00:06 AC

Alice와 Bob 모두 큰 수부터 지우면 된다고 생각하였다.

00:14 WA

머리가 꼬였는지 이상한 코드를 제출하기 시작한다.

00:17 WA

00:23 WA

위의 두 WA는 말도 안 되는 코드이다.

하지만 대회 중에는 예제가 잘 나오니 올바른 풀이라고 생각하였다.

이후 Bob은 작은 수부터 지워야 최적임을 깨달았다.

00:25 AC

전체 개수에서 non-ambiguous array의 개수를 빼면 된다.

각 인덱스마다 하한이 정해지므로 이를 토대로 계산하면 된다.

마지막 예제가 제대로 나오지 않았는데 overflow 문제였다.

어떻게 해결할까 고민하다가 그냥 __int128 박았다.

00:56 AC

1시간 동안 붙잡았는데 감도 못 잡았다.

대회 끝나고 누군가 bfs로 풀이할 수 있음을 알려주었는데 듣자마자 금방 풀이가 떠올랐다.

역시 태그를 보고 푸는 것과 보지 않고 푸는 것은 차이가 크다.

이 문제는 맨 왼쪽 열에서 맨 오른쪽 열로 이동할 수 있는 대각선 cactus 경로의 최소 비용을 찾는 문제와 동일하다.

간선의 가중치가 0 또는 1이므로 0-1 bfs로 풀이할 수 있다.

Pass