Educational Codeforces Round 112 (Div. 2)

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

 

실제론 45 올랐다

 

잘 풀고 있다는 느낌이 드는데 점수가 생각보다 오르지 않는다 ㅠ

 

Prob. A

$6:15=8:20=10:25$ 이므로 무엇을 선택할지는 딱히 중요하지 않다. $6$이상 짝수는 모두 만들 수 있으니 $n<6$ 일 때, $n$이 홀수일 때를 따로 처리해주면 된다.

 

Prob. B

구석에 추가하는 것이 최적이므로 4가지 케이스를 모두 확인해주면 된다. 답을 소수로 출력하라길래 sqrt가 들어가는 줄 알고 뇌절했다.

 

Prob. C

Alice의 이동이 끝나면 Bob은 두 그룹 중 한 그룹 만을 지날 수 있다. 누적합을 박으면 풀린다. C<B 였던 것 같다.

 

Prob. D

잘 생각해보면 $abc, acb, bac, bca, cab, cba$ 중 하나가 반복되어야 한다. 이를 쿼리마다 계산했더니 TLE를 받았고, 각각 전처리한 다음 $O(1)$ 에 쿼리를 처리하는 방향으로 바꿨다.

 

Prob. E

$w_{i}$ 순으로 정렬한 다음 투포인터를 돌리자는 발상을 할 수 있다. 하지만 구간을 넣고 빼는 것과 연결 여부를 최소 $O(logN)$ 에 수행해야 하는데, 이 아이디어가 쉽지 않았다. map으로 가능한지, 유파가 쓰이는지, 세그 트리로 되는지 한참 고민하다가 min lazy 세그를 쓰면 된다는 것을 깨달았다. max lazy 세그를 최근에 짠 적이 있어서 그대로 가져왔고, 이것저것 잔실수 고치다가 2분 전에 제출한 코드가 맞았다.