[코드포스] Round #804 (Div. 2)

안녕하세요 aim_higher 입니다.
코드포스 Round #804 (Div. 2) 코드리뷰 및 업솔빙입니다.

---

A. The Third Three Number Problem
https://codeforces.com/contest/1699/problem/A

• Math(수학)

문제의 요지는 n이 입력으로 들어오면,
(a ⊕ b)+(b ⊕ c)+(a ⊕ c) = n 을 만족하는 a, b, c를 출력하면 됩니다.

---

먼저 저희는 a, b, c의 마지막 비트에 주목해야합니다.
즉, a, b, c가 홀수인지 짝수인지에 따라 나오는 결과값의 홀/짝 유무를 확인해봅시다.

i) 홀수가 0개일 때
(0 ⊕ 0)+(0 ⊕ 0)+(0 ⊕ 0) = 짝

ii) 홀수가 1개일 때
(1 ⊕ 0)+(0 ⊕ 0)+(1 ⊕ 0) = 짝

iii) 홀수가 2개일 때
(1 ⊕ 1)+(1 ⊕ 0)+(1 ⊕ 0) = 짝

iv) 홀수가 3개일 때
(1 ⊕ 1)+(1 ⊕ 1)+(1 ⊕ 1) = 짝

결론은, 모든 경우의 수에서 짝수가 나오기 때문에 홀수는 불가능합니다.
 
처음으로 돌아가서 문제에서 요구하는 a, b, c를 구하기 위해서
저희는 XOR의 기본 법칙에 대해 정리할 필요가 있습니다.

• 0 ^ n = n : 0은 n값에 XOR연산에서 영향을 주지 않아 그대로 n값이 출력됩니다.
• n ^ n = 0 : n과 n은 서로 같으므로 다름을 요구하는 XOR에서는 0이라는 결과로 나타납니다.

어차피 a, b, c가 서로 먹고 먹히는 관계이기 때문에
공평하게 a = 0, b = c와 같다고 설정했습니다.
식을 다시 정리하면 (0 ⊕ b) + (b ⊕ b) + (0 ⊕ b) = 2*(0 ⊕ b)
 
즉, 2*b = n을 만족하는 b를 구하면 됩니다. (a = 0, c = b)
위 식을 통해 수식으로도 n이 짝수임이 증명이 됩니다.
 
그래서 정답은 a = 0, b = n / 2, c = n / 2 입니다.

---

B. Almost Ternary Matrix
https://codeforces.com/contest/1699/problem/B

• Constructive(구성적)

 
모든 칸에 대해서, 자신의 타일의 색깔과 다른 색깔의 인접한 타일이
정확히 2개인 상태를 유지하도록 행렬을 구성하는 문제입니다.
 
입력값에 대한 추가적인 명시사항은 이렇습니다.

• n과 m은 짝수이다.

이를 통해, 2x2 단위로 타일을 지켜볼 필요가 있습니다.
 
그리고 테스트케이스를 통해 다음과 같은 결과를 알 수 있습니다.
n = 2, m = 2일 때, 아래와 같은 타일 패턴이 나옵니다.