Codeforces Round #736 (Div. 1)

Dashboard - Codeforces Round #736 (Div. 1) - Codeforces

 

 

떡락했다. 직전까지 애니 보다가 급하게 참가했는데, 그냥 마저 볼 걸 그랬다.

 

Prob. 1A

인접한 사람 중 나보다 큰 사람이 있다면 무조건 죽는다. 그래서 나보다 큰 사람이 몇 명인지가 중요한데, 이를 set $N$개로 관리하다가 뇌절하고 단순히 명수만 세주는 식으로 코드를 갈아엎었다.

 

Prob. 1B

2 이상의 수로 나누어 떨어지는 최대 구간을 구하는 문제로 치환할 수 있다. 투포인터로 풀어야 할 듯 한데, gcd를 롤백할 방법만 고민하다가 gcd 세그가 나중에 생각이 났다. 그런데 투포인터도 계속 잘못 짜고 bottom case를 잘못 넣어줘서 페널티를 엄청 쌓아버렸다.

 

Prob. 1D1

내부 격자점 개수를 구하는 공식으로는 픽의 정리가 있고 변 위의 점의 개수는 gcd로 구할 수 있다. 이를 이용해 정리해보면 gcd 세 개의 합이 4의 배수가 되는 쌍의 개수를 구하는 문제가 되는데, 더 이상 생각을 발전시키지 못했다.

 

 

DIv.1 은 아직 무리인 것 같다. DIv. 2에서는 쉬운 문제를 빠르게 풀고 남은 시간을 충분히 써서 어려운 문제를 해결하는 것만으로 좋은 결과를 냈는데, Div. 1은 바로 어려운 문제부터 시작하니 경쟁력이 없는 것 같다.

대회 끝나고 보니 C, D는 어차피 못 풀었을 것 같고 B에서 실수를 하지 않았더라도 좋은 퍼포를 받기는 무리였다. 아무래도 오렌지 달성은 겨울방학에나 도전해야 될 것 같다.