Educational Codeforces Round 111 (Div. 2)

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

 

오

 

2시간 동안 고작 3문제 푼 게 끝인데 지금까지 받아보지 못했던 퍼포를 받았다. 에듀 치고는 어려운 셋이었나 보다. 상승 폭을 보니 맥스 레이팅을 찍을 것 같아서 조금은 기쁘다. 퍼플은 언제쯤 갈 수 있을까...

 

 

Prob. A

$ ans^{2}\geq n $ 인 $ ans $를 구하면 된다. 왠지는 모른다. ㅋㅋ 인터넷 문제로 제출이 1분 정도 늦어져서 슬펐다.

 

Prob. B

처음에는 case work인 줄 알고 a, b의 범위를 나눠서 생각하고 있었다. 하지만 쓸데없는 짓이었고, a가 항상 n번 더해진다는 것을 알면 b의 범위만 고려해주면 된다. b가 음수일 때 최소 쿼리 수를 잘못 구해서 1틀 후 AC.

 

Prob. C

점을 몇 개 찍어보면 $ a_{i}, a_{j}, a_{k} $가 단조 증가, 혹은 단조 감소 수열인 것과 bad triple이 동치라는 것을 알 수 있다. 그렇다면 bad triple이 없는 구간의 개수를 빠르게 구할 수 있어야 하는데... 처음에는 bad triple을 포함하는 구간의 개수를 dp로 구해보려고 하다가 뇌절했다. 그러고는 풀이가 떠오르지 않아서 bad triple이 없는 구간을 아무 생각 없이 그리다가, $ n\geq 5 $이면 bad triple이 항상 존재한다는 것을 증명했다. 이 명제의 중요성을 깨닫지 못하고 다시 dp 풀이로 빠져들다가 이건 아니다 싶어서 생각을 정리하던 차에 $ n\leq 4 $인 경우를 O(N)에 브루트포싱한다는 아이디어가 떠올랐다. 구현은 어렵지 않았고 출력을 두 번하는 실수를 고친 후 AC.

 

Prob. D

$ F(a)=n-1 $ 임을 증명하고(확실하지 않다) 예제를 봤는데 두 번째 케이스가 어떻게 해야 10이 나오는지 전혀 모르겠어서 한참 고민하다가 버렸다.

 

Prob. E

이분탐색에 뭘 끼얹으면 될 것 같이 생겼는데 나는 비트마스킹+그리디를 얹었다가 망했다. 정해는 dp인 듯. 이분탐색에 dp 박는 문제 이젠 풀 때도 되지 않았나?