Codeforces Round #735 (Div. 2)

Dashboard - Codeforces Round #735 (Div. 2) - Codeforces

 

 

무난한 라운드였는데 C에서 크게 말리는 바람에 퍼플 퍼포를 받았다. D를 먼저 잡았으면 어땠을까 하는 아쉬움이 남는다.

 

Prob. A

구간이 길어서 좋을 게 없다. $a_{i}*a_{i+1}$ 만 검사해주면 된다.

 

Prob. B

식에서 뭔가를 관찰하기는 어려워 보이고, 범위가 조금 수상하다. $a_{i}<n$ 이라는 조건 때문에 $a_{i}*a_{j}< 2n$ 임을 알 수 있고, $k\leq 100$ 이기 때문에 뒤쪽에서 정답이 나온다는 것을 유추할 수 있다. 따라서 유효한 범위에서만 전부 검사해주면 된다.

 

Prob. C

Case Work 인 줄 알고 열심히 나누다가 망했다. 결국 Case Work로 $O(Tlog^2N)$ 에 풀어내긴 했는데, 풀이는 별로 설명하고 싶지 않다.

 

Prob. D

C를 풀고 나니 17분 밖에 남지 않아서 좌절했으나 문제를 보니 어렵지 않게 풀이가 떠올라서 다행히 해결했다. 분명 구성적인 풀이가 존재할 텐데, 26을 이용하지는 않을 것 같아서 적은 알파벳으로 답을 만들 수 있을 것이라 생각했다. 일단 $aaa\cdots aaa$ 같은 길이가 $k$인 수열을 써봤는데, 길이가 1인 수열이 $k$개, 길이가 2인 수열이 $k-1$개, $\cdots $ 길이가 $k$인 수열이 1개이므로 길이가 $k-1$인 수열이 있으면 적당히 다 상쇄된다는 것이 보였다. $n$의 홀짝성에 따라 $b$와 $c$를 적당히 넣으면 되는데, $n=1$ 일 때의 예외 처리를 해주지 않아 1틀했다.