Educational Codeforces Round 104 (Div. 2)

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

 

 

퍼플 퍼포먼스를 처음으로 받아봤다. D번까지 말리지 않고 빠르게 해결하니 가능했던 것 같다. 하지만 그 뒤로 아무것도 못하고 스탠딩만 초조하게 바라보고 있었다. 

 

Prob. A

문제에 쓸 데 없는 말이 좀 많은데, 결국 최소가 아닌 a들의 개수가 답이다. 정렬 후 최소 개수 세주고 n에서 빼면 AC.

 

Prob. B

문제가 심플해서 좋았고, 바로 규칙 찾기에 몰두했다. 초반엔 규칙을 잘못 찾아서 예제도 안 나오다가 멍청했다는 것을 깨닫고 바로 고쳐서 AC. n=5, n=7만 시뮬레이션해도 규칙을 금방 찾을 수 있다.

 

Prob. C

이게 C번이 맞나 싶었던 문제. 솔직히 n=2k+1 꼴이면 k승 k패, n=2k+2 꼴이면 k승 1무 k패가 자명해 보인다. 구현도 더럽게 쉬워서 그냥 j-i<n/2 일 때 1, j-i==n/2 일 때 0, j-i>n/2 일 때 -1을 출력하면 된다. 코드 다 짜 놓고 이게 맞나? 싶어서 더 최적인 경우가 있는지, 내 코드대로 하면 항상 답이 나오는지 검증하다가 시간을 많이 썼다. 물론 틀리는 것보다는 시간 더 써서 고치는 게 낫지만, 이렇게 자기 자신을 못 믿어서는 좋은 점수를 받을 수 없다.

 

Prob. D

이게 D번이 맞나 싶었던 문제. 생각보다 풀이가 다양하더라. 문제에서 주어진 식과 피타고라스 식을 연립하면 c-b=1 임을 쉽게 알 수 있다. 그렇다면 a가 홀수임은 자명하고, a=2k+1로 두면 b=2k^2+2k, c=2k^2+2k+1 로 표현할 수 있다. k=1부터 c <=n까지 k의 개수가 답. 나는 피타고라스 원시근을 이용해서 조금 돌아갔으나 크게 다른 건 없다.

 

Prob. E

남은 시간은 많았지만 아이디어가 잘 떠오르지 않았다. 30분 쯤 남았을 때 sort와 lower_bound를 남발하는 뇌절 풀이가 생각났는데, 이걸 내가 시간 내에 구현할 수 있을지도 모르겠고 시간 안에 돈다는 믿음도 없어서 더 좋은 풀이를 생각하다가 실패했다. 대회 끝나고 보니 내 아이디어랑 똑같이 구현한 분이 계시더라. 약간 아쉬움도 들었는데, 구현이 좀 구데기여서 30분 내에는 못 풀었을 것 같았다. 고수들은 이 문제에 세그 트리를 박던데, 이해를 포기했다.

 

내 제출 현황을 봤는데 코드 길이가 A>B>C>D 순이더라...ㅋㅋ 4문제 모두 3~4줄 내외로 해결이 가능했던 만큼 날먹셋이었다. D를 해결했을 때 300등 정도였는데 오렌지 퍼포먼스인 걸 보고 조금 설렜다. 별 다른 연습을 하지도 않았는데 최근 퍼포먼스가 잘 나와줘서 좋고, 오늘 있는 div3에는 맘 편하게 참가할 수 있을 것 같다.