CodeChef Starters 99 (Div. 2)

밀린 후기가 있어 이것만 작성하고 UCPC 후기를 쓰려 한다. Div. 4에서 1등을 했더니 3은 칠 기회도 없이 Div. 2로 와버렸다.

 

P1. Card Swipe (0:02) 

잘 구현해주면 된다.

 

P2. Exclusion-Inclusion (0:04) 

작은 값부터 빼주면 된다.

 

P3. Segment Three (0:19) 

각 원소 당 더해야 하는 숫자는 최대 2이다. 저 쉬운 풀이가 있을 것 같기도 한데 잘 모르겠어서 \(O(27N)\) 3진법 Bit DP를 돌렸다.

 

P4. Two Piles (0:32) 

어디서 많이 본 문제라 바로 짰다. 대충 하나 고정하고 스위핑을 잘 해주면 된다.

 

P5. Maximize Ones (0:54) 

연산으로 바꿀 수 있는 수가 없는 경우나 모든 수가 같은 경우는 예외처리를 해주자. 그러면 바꿀 수 없는 양 끝 수를 기준으로 경우를 나눌 수 있다.1) 양 끝이 0,0인 경우: 0111...1110을 만들 수 있다.2) 양 끝이 0,1 / 1,0인 경우: 0111...1111 이나 1111...1110을 만들 수 있다.3) 양 끝이 1,1인 경우: 1011...1111을 만들 수 있다.이는 몇 개를 가지고 놀다 보면 발견할 수 있는데, 자명하지만은 않은 것 같다.

 

P6. Musical Chairs (1:20) 

기댓값 식은 선형성을 이용해 분리해줄 수 있다. 어차피 각 사람이 방문하는 색의 개수는 최대 \(N\)이고, 이는 처음 한 번만 \(K\)번을 돌며 저장해주면 나머지는 한 사람당 \(O(N)\)에 확인할 수 있다. 따라서 \(O(K+N^2)\)에 문제를 해결할 수 있다.

 

P7. Yet Another Bitwise Problem (-) 

풀이의 상당 부분을 찾았지만, 마지막 파트를 완성하지 못해 결국 풀지 못 했다.

 

 

아쉽게도 4분 차이로 2등을 하게 되었다. 2번 쳤는데 레이팅이 한국 3등이 된 것을 보면 가성비가 좋은 것 같다.