[CF] Codeforeces Round #803 (Div2)

https://codeforces.com/contest/1698

Dashboard - Codeforces Round #803 (Div. 2) - Codeforces

나도 담에 그레이 탈출하나?

A. XOR Mixup (00:08)

처음엔 그냥 n제한이 100이라서, 그냥 \( O(n^2) \)으로 풀어야지 하고, 풀었었다. 

끝나고 나서, 다른 분들 코드랑 에디토리얼을 보니 XOR 연산의 특징을 이용한 \( O(n) \) 풀이가 있었다.

 

같은 수끼리 XOR 연산을 하면 0이라는 점을 이용하면 된다. (x^x=0)

또 어떤 수 x와 0을 XOR 연산을 하면 x라는 점도 생각할 기회가 없었는데, 새삼 알게 되었다. (x^0=x)

 

먼저, 내 풀이에서, (x^0=x) 를 이용해서 XOR 연산을 시작할 때 첫 피연산자를 a[0], a[1]과 같이 두지 말고, 그냥 0으로 두면 for문을 돌면서 예외 처리하지 않고 훨씬 쉽게 구현할 수 있다. 

 

다음으로는, \( O(n) \)풀이를 알아보자.

 x=a[0]^a[1]^ . . . ^a[n-2]^a[n-1]

위 식의 양변에 a[1]^a[2]^ . . . ^a[n-2]^a[n-1]를 XOR 연산해주면, 

우변은 a[0]^(a[1]^a[1])^ . . . ^(a[n-2]^a[n-2])^(a[n-1]^a[n-1]) = a[0] 이므로 (x^x=0), 

a[0] = x^a[1]^a[2]^ . . . ^a[n-2]^a[n-1] 이다. 따라서 a[0]이 n개의 수열 중에서 x의 역할을 할 수 있다.

왜냐하면 a[0]는 n개의 수열 중 나머지 n-1개의 수열들끼리 XOR 연산한 값과 같기 때문이다. 

이는 다른 a[i]에 대해서도 모두 같은 방법으로 증명할 수 있다.

따라서, 그냥 n개의 수열 중 아무 수나 하나 출력해주면 된다.

B. Rising Sand (00:22)

\( k==1 \) 일 때에는 각 pile 에 마음껏 모래를 추가 할 수 있고, i번째가 too tall 하면 이웃한 pile은 too tall 할 수 없으므로, 항상, 최대인 \( [{\frac{n-1}{2}}] \) 가 답이다.

 

\( k \geq 2 \) 일 때에는 i번째를 too tall로 만들려 모래를 추가하면 무조건 그 이웃한 곳도 모래가 추가되므로, 새로운 too tall한 pile 만들 수 없으므로, 처음에 주어진 만큼의 too tall한 pile 수가 답이다. 

C. 3SUM Closure (01:26)

에디토리얼의 풀이에선

- a배열 중 양수가 3개 이상이면 무조건 NO, 즉 양수는 최대 2개만 존재 가능

- a배열 중 음수가 3개 이상이면 무조건 NO, 즉 음수는 최대 2개만 존재 가능

- a배열 중 0이 3개 이상이면 의미가 없으므로 최대 2개의 0만 남겨주고 브루트 포스를 하자.

따라서 최대 길이가 6인 배열이 존재 가능하므로, 이 배열들에 한에서만 완전 탐색를 하면 된다.

\( {}_6 \mathrm{ C }_3 * 6 = 120 \) 의 연산을 해주면 되므로 충분히 제한 시간 안에 해결한다.

 

내 풀이는 에디토리얼의 풀이 중 1번째, 2번째 조건은 같은 방식으로 이용했지만, 3번째 조건은 다르게 이용했다. 

0의 개수 == n, n-1 인 경우, 무조건 YES

0의 개수 == n-2 인 경우, a배열의 최댓값과 최솟값이 서로 절댓값만 같고 부호가 다를 때만 YES, 아니면 NO

와 같이 0의 개수를 기준으로 케이스 분류를 더 사소하게 해준 후 n이 5이상, 4, 3인 경우를 나눠서 완전 탐색을 했다.

 

0의 개수를 기준으로 나눌 때 조금 더 깔끔하게 했으면 구현이 더 간단했을 것 같다.

---

D번은 업솔빙을 하려 했으나, 효율이 안나올거 같고, 귀찮아서 못했다...

 

거의 5월 초부터 코포 레이팅이 계속 횡보하고 있었는데, 그래도 이번에 간만에 엄청나게 올라서 기분이 좋아서 글을 쓰려고 했는데, 막상 쓰니까 귀찮아서 미루다가 이제야 썼다...

 

제발 담에 뻘짓하지 말고 바로 그린 가자!

---

XOR 연산의 기본 성질

- x^0 = x

- x^x = 0

- x^y = y^x (교환 법칙 느낌)

- (x^y)^z = x^(y^z) (결합 법칙 느낌)