Codeforces Round #702 (Div. 3)

Dashboard - Codeforces Round #702 (Div. 3) - Codeforces

 

900등 정도로 마무리했었다..

 

div3 6솔을 했다. 사실 div3 치고도 쉬워서 6솔 하위권은 민트 퍼포가 나오는 참사가 벌어졌다.

 

Prob. A

앞에서부터 보면서 max/min>2 이면 max/min<=2 까지 min*2 하면서 카운팅해준다.

 

Prob. B

뇌절해서 1틀했다. 나머지를 집합으로 만들어서 모두 같아질 때까지 오른쪽으로 밀어준다.

 

Prob. C

이분탐색으로 많이들 풀었던데 나는 더 효율적인 투포인터를 사용했다. a=1,b=(b*b*b<=x인 최대 b) 로 설정하여 a를 증가, b를 감소시키며 가능한 경우가 있는지 판별한다.

 

Prob. D

아이디어가 쉽지는 않았다. 각 노드의 깊이를 갱신해주는 재귀함수를 만들면 깔끔하게 풀린다.

 

Prob. E

정렬하면, 본인 왼쪽에 있는 숫자들을 모두 흡수할 수 있고, 이 값이 오른쪽의 값보다 크다면 우승 가능성이 있다. 구현 방향이 잘못되어서 시간을 꽤 썼다.

 

Prob. F

마냥 쉽지는 않았는데 잘들 풀더라. 정렬한 다음 같은 수가 몇 번 반복하는지를 세서 저장한다. 그리고 개수의 구간합을 만들어야 한다. 그리고 나서는 c를 1부터 n까지 정해주며 최솟값을 갱신한다. 이때 각 c마다 제거해야 하는 수의 개수를 구간합을 이용하여 일반화할 수 있다.

 

Prob. G

O(NM)이 되는 줄 알고 신나게 짜다가 WA와 TLE를 받고 종료 3분 전에 잘못되었음을 깨달았다. 정해는 O(MlogN)이라는데 곧 풀어볼 것이다.

 

 

꽤 빠른 6솔을 했는데 퍼포는 블루 중반 밖에 나오지 않을 정도로 쉬운 라운드였다. 아이디어를 떠올리는 과정이나 구체화시키는 것을 더 빠르게 하는 연습이 필요한 것 같다.