CodeForces Round 1022 $($Div.2$)$

자러가기 전 등수

 

총평 : Score distribution이 500 - 1250 - 1500 - 2250 - ... 확인하고 C 스피드포스가 되겠다고 생각은 했다만, 더 심했던 듯. C 난이도가 굉장히 쉬웠고, B에서 말리냐 안말리냐가 중요한 라운드였는데, 다행히 잘 빠져나왔다.

D까지 풀고 자려고 했는데 하필 그게 인터랙티브라 "This is an interactive problem." 보자마자 도망.

 

블루 복귀

 

---

 

A. Permutation Warm-Up $($+, 00:03$)$

 

$N$ 작은 것들을 수작업해보면, 가능한 $f(p)$가 $0, 2, 4, ...$로 $0$부터 최댓값까지 모든 짝수들이 나온다는 것을 확인할 수 있었고, 증명은 하지 않고, $N$이 작길래 $1, 2, 3, 4, 5, ..., N$을 $N, N-1, N-2, ..., 1$과 비교하여 나온 최댓값$($반드시 짝수$)$보다 작거나 같은 짝수 $($$0$ 포함$)$의 개수를 세서 제출했다.

 

https://codeforces.com/contest/2108/submission/317960999

 

 

 

B. SUMdamental Decomposition $($+, 00:20$)$

 

일단 $K$를 이진법으로 나타냈을 때, $1$이 되는 비트의 개수를 구한다. 이 개수를 $cnt$라고 하겠다. $cnt$가 만약 $N$보다 크다면 그 켜지는 비트들을 나눠먹어서 당연히 $xor$하는 모든 수의 합을 $K$로 구성할 수가 있다. 그렇지 않은 경우, 일단 $1$이 들어간 비트를 하나씩 나눠먹어서 $cnt$ 만큼의 수를 만들 수가 있고, 나머지 수를 최소화하기 위해서는 나머지를 모두 $1$로 구성해서 사라지게 해주면 되는데, $N-cnt$가 짝수이면 상쇄되어서 상관이 없지만, $N-cnt$가 홀수라면, $2$의 비트를 한 번씩 켜주고 꺼줘야 한다. 짝수면 $1, 1, 1, 1$, 홀수면 $1, 1, 1, 3, 2$ 이런 식. $($모든 수가 양수여야 하기 때문.$)$

 

https://codeforces.com/contest/2108/submission/317970195

 

 

 

C. Neo's Escape $($+, 00:43$)$

 

일단 이 문제 처음 봤을 때, DSU로 시뮬레이션 하듯이 하면 풀리겠다는 생각을 했다. 실제로 구현까지 하려고 했으나, 준비 단계에서 고려해야할 부분이 너무 많이 보였다. 그 순간에 아주 좋은 아이디어가 떠올랐는데, 결국은 양쪽에 있는 수보다 자신의 수가 더 큰 경우에만 시작점$($클론$)$들로 지정해주면 된다는 것이었다. 차근차근 생각해보면 당연한 것이니 증명은 생략하겠다.

여담으로, DSU로 시뮬레이션 하는 방법도 가능하며 BFS로 간단하게 시뮬레이션 하는 것도 가능하다고 한다.

 

https://codeforces.com/contest/2108/submission/317981706

 

 

업솔빙 예정 : 無 - 한다면 D인데 인터랙티브라서. 

 

인터랙티브 문제 연습을 언젠가 하긴 해야한다..