Codeforces Round #697 (Div. 3)

Dashboard - Codeforces Round #697 (Div. 3) - Codeforces

 

대회 시작 5분 전부터 대기 타다가 갑자기 15분이 연기돼서 블로그 쓰러 왔다.. 사실 unrated round가 처음이라 약간 기분이 좋다 ㅋㅋ

다른 분들 편하게 푸실 때 부러웠는데 내가 그 입장이 되니 기분이 묘하다...ㅎ 

지금까지는 div.3에서 퍼포먼스가 잘 나오지 않았는데, 이번에는 다르길 기대해본다.

(10분이 추가로 연기되어서 12시 정각에 시작했다.)

 

실제로는 930등 정도였다.

 

Prob. A

1을 제외한 홀수 약수가 있는지 묻는 문제. 답이 빤히 보여서 예제도 안 돌려보고 제출. 하지만 자잘한 실수를 해서 1CE, 1WA 후 AC.

 

Prob. B

부정방정식 문제. 까다로운 듯하였으나 식을 전개해보니 n을 2020으로 나눈 몫과 나머지의 크기 비교를 해주면 되는 것 같아 구현 후 AC. 실제로 관찰까지 시간이 조금 걸렸다.

 

Prob. C

사람들은 잘만 풀던데 나는 풀이가 전혀 생각나지 않았다. 고민 끝에 포함 배제를 떠올렸고 다행히 AC. 정해는 무슨 그래프 간선 개수를 이용하던데 내 풀이와 비슷한 것 같다.

 

Prob. D

대회 중에는 풀지 못했다. 최근에 냅색 문제를 감명 깊게 풀어서 이 문제도 냅색 문젠 줄 알았다. 그런데 범위가 커서 냅색은 어림도 없었고 정렬+그리디인가 해서 짰는데 당연히 WA. 더 생각해도 못 풀 것 같아서 포기.

 

Prob. E

왜 E번인지 이해 안가는 문제. D보다 많이 풀려서 먼저 시도했다. 정렬 후 nCr만 계산하면 풀리는데 심지어 범위가 작아서 정해가 O(N^2)..

 

Prob. F

D에서 시간을 많이 끌었지만 F에서 만회했다. 한 줄의 모든 비트를 반전하여 a, b를 일치시킬 수 있는가 묻는 문제. 처음에 입력받을 때 a, b를 xor 해서 입력받고, a를 전부 0으로 만들 수 있는가로 변형할 수 있다. 그리고 한 줄을 두 번 반전하는 것은 의미가 없는데, 따라서 모든 줄의 반전 횟수는 0, 1로 생각할 수 있다. 여기서 작은 관찰을 해야 하는데, a를 모두 0으로 만들 수 있으려면 임의의 가로줄 2개, 세로줄 2개를 뽑았을 때 a(0,0)+a(1,1)=a(0,1)+a(1,0)이 성립해야 한다. 이는 a의 모든 2*2를 검사하는 것과 동치이다. (증명하지 않았다. CP는 믿음!) 따라서 O(N^2)으로 검사해주면 답을 얻을 수 있다. 나는 이렇게 풀었는데 나처럼 푼 사람은 아무도 없더라.

 

Prob. G

역시나 대회 중에는 풀지 못했다. F를 해결하고 남은 시간이 별로 없어 문제만 읽어봤는데 어려워 보였다. 정해는 에라토스테네스의 체를 응용한 DP. 많이 참신했다.

 

 

대회 중에 뭐가 문제였는지 채점이 원활하지 않았고, 그래서 Unrated로 정정되었다. Div.3치고 좋은 성적을 낸 것 같지만  D, G는 충분히 풀 수 있는 문제였기에 기본기를 더 연습해야겠다고 생각했다.