Codeforces Global Round 4

global round는 레이팅이 많이 오를 수 있는 기회기 때문에, 집으로 달려와 준비를 마쳤다. 목표는 약 500등 정도, 퍼플가기의 두 가지 목표를 가지고 시작하였다. 

A.Prime Minister

1번 (자신의) 그룹으로 나머지 그룹들을 흡수해서 그룹원의 숫자를 전체의 절반 이상이 되도록 만들 수 있는지를 판별하고 만들 수 있다면 그 방법을 출력하는 것이다. 다른 그룹을 흡수하기 위해서는 우리 그룹원의 수가 흡수할 그룹원의 수의 2배 이상이어야 한다. 이 문제도 지난번 A 처럼 해석이 미친듯이 어려웠다. 코딩 자체는 굉장히 naive 하게 가능하다. 다들 해석이 어려웠나보다. 00:07이었지만, 친구창중 꽤나 상위권

B.WOW Factor

전체문자열중 부분문자열 vvovv 의 갯수를 찾는 것이다. vv의 위치를 체크해놓고 전체 갯수를 세놓은 다음 한번쪽 순회하면서 (O(N)) o가 나오게 되면 o이전에 나온 vv의 갯수와 이후의 나온 vv의 갯수를 바로 알 수 있기 때문에 두 값을 곱하면서 다 더하면 된다. 약간 아이디어이지만, 생각하는 것이 크게 어렵지않았다. 00:15

C.Tiles

딱보자마자 어느정도 dp or 쉬운 수학이라고 생각했다. 64=2^8이라고 잘못생각하는 바람에 1*1에서 2*3정도 까지 해보니까 맨첫칸은 4가지 첫행과 첫 열은 2가지 나머지 칸은 1가지로 배치가 결정된다는 것을 알게 되었다. 따라서 행과 열을 입력받으면 둘을 더해서 2의 거듭제곱을 시키면 끝! 위의 계산 실수땜에 잘 못 생각한 것이 좀 컸다. 00:22

D.Prime Graph

아아 이래서 킹수론을 공부하는구나. 얼마전에 n과 2n사이에 소수는 반드시 존재한다는 것을 증명했다. 각 노드별 차수와 총 간선수가 모두 소수면 되는데 각 노드별 차수를 2또는 3으로 할 생각이었다. 그러기 위해서는 n과 3/2n사이에 소수가 존재해야 하는데 문제의 조건인 1000이하에서 성립하기 때문에 매우 쉬워졌다. 그래프를 원형으로 모두 이은후에 반대편에 있는것끼리 총 간선갯수가 소수가 될때까지 간선을 추가해 주면 된다. 왠지는 모르겠지만 시간이 좀 걸렸다. 00:35

E.Archaeology

이해하는데에 굉장히 오랜시간이 걸렸으며, 이해도 잘못하였다. 그냥 전체 문자열중 길이가 조건에 맞는 펠린드롬 부분 문자열을 뽑아내는 것이다. 문자 종류는 a,b,c 밖에 없으며 연속하지 않는다. 이 연속하지 않는다를 보지 못해 돌아가는 코드를 짰고, 그 코드는 특정케이스에 대해서 O(N^2)이었기 때문에 main 테스트에서 TLE가 나고 말았다. 정풀은 전체 문자열에서 양쪽 2개씩을 보면 무조건 2개는 같은 문자열이므로, 4개중 2개는 팔린드롬에 들어간다. 이후 마지막에 3개가 남고 모두 다르면 아무거나 문자 하나를 집어넣어야 한다. 이 부부을 고려하지 않은 사람을 발견해 hack을 성공 300등대에 진입했었다. 하지만 E를 system test fail 당했기 때문에 최종 1043등 +9로 마무리했다.