[Codeforces] Round #475 (Div. 2)

오랜만에 5문제짜리 라운드를 한 것 같네요. C를 굉장히 늦게 맞추고, 더군다나 4번 틀리기까지 했습니다.

 

A - Splits

 

맨 처음에는 답이 잘 유추가 안되어서 굉장히 애먹었습니다. 그런데 생각해보니 그냥 2와 1로만 수열을 만든다고 생각하면 굉장히 자명한 문제였습니다. 그냥 주어진 N에 대해 N/2 + 1을 출력하면 됩니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20475%20Div.2/A.cpp

 

B - Messages

 

설명을 이해하고 나면 그냥 C < B일 때 메시지를 받은 즉시 읽고, C >= B일 때 메시지를 t초에 읽는 것이 나음을 알 수 있습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20475%20Div.2/B.cpp

 

C - Alternating Sum

 

항이 최대 $10^9$이기 때문에 정직하게 더해나가는 방식으로는 시간 내에 풀 수 없습니다. 대신 modulus의 성질과 기타 다양한 방식을 통해 수식을 간략화할 수 있는데,

우선 $a*b^{-1} = x$, $a^n = t,$ $n+1 = qk$라고 두고 나면 식을 예쁘게 정리할 수 있습니다. 단 $x^k-1$이 0과 합동일 때의 처리는 별도로 해주어야 합니다.

 

$k=1$이면 $1+x^k+x^2k+..$ 부분의 계산에 최대 $O(N)$이 필요하고, 이 부분을 맨 처음에 $(x^{qk}-1)/(x^k-1)$로 처리하지 않아 TLE를 여러 번 받았습니다. 맨 처음에는 제가 만든 pow 함수에서 문제가 생겨 TLE가 뜨는 줄 알았다가 대략 끝나기 20분 전 쯤에 $k$가 작을 때 연산량이 많을 수 있음을 알아차렸습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20475%20Div.2/C.cpp

 

그나마 C를 풀어내어 레이팅이 심각하게 깎이지는 않았지만 뭔가 조금 정체된 느낌입니다. 계속 열심히 하는 방법밖엔 없을 것 같네요.