Codeforces Round #742 복기

라운드가 4~5일 정도 없다가 오랜만에 진행한 코드포스 라운드, 라운드가 없는동안 알고리즘에 소흘하기도 했다가 당일에서야 라운드가 있는걸 알고 2시간 정도 전에 등록했었다.

컨디션도 안좋고 피곤한 상태라 라운드를 안하는게 맞았지만 두 문제정도 풀 생각으로 참여했었다.

https://codeforces.com/contest/1567/problem/A

Problem - A - Codeforces

문제 A는 시간복잡도 O(N)으로 L, R이 입력되면 그대로 출력, U나 D가 입력되면 반대로 출력하면 되는 문제. 풀어본 Div 2 문제 중에서 가장 쉬웠던거 같다.

 

https://codeforces.com/contest/1567/problem/B

Problem - B - Codeforces

 문제 B는 입력값 a, b에 대해서 정수 배열의 MEX 값이 a이고 배열내의 모든 값을 XOR 계산한 결과가 b를 만족하는 배열 중 가장 짧은 배열의 길이를 출력하는 문제.

피곤한 상태라 영어도 잘 안읽히고 MEX도 처음보는 개념이라 스트레스 받았었다.

일단 MEX 값이 a이기 위해서 배열은 0, 1, ... , a-1을 배열에 포함하고 있어야한다. 그리고 0부터 a-1까지 XOR 연산한 결과를 x라고 할 때  x ⊕ x ⊕ b = b라는 xor의 성질을 이용해 푸는 문제.

세가지 경우로 나뉘는데

1. x = b인 경우 0부터 a-1까지 포함하고 있는 배열이 최소 길이이기 때문에 a를 출력한다.

2. x != b이고 x ⊕ b != a인 경우, x ⊕ b만 배열에 추가하면 조건을 만족하기 때문에 a+1를 출력한다.

3. x != b이고 x ⊕ b = a인 경우, x ⊕ b를 배열에 추가할 수 없기 때문에 x ⊕ b ⊕ 1과 1을 배열에 추가하면 조건을 만족한다. a+2를 출력.

MEX의 개념때문에 그런건지 몰라도 배열에 중복된 숫자를 포함하면 안된다는 조건이 없었는데 중복이 불가능하다 생각해서 못풀었었다. 약간 아쉬운 문제.

 

https://codeforces.com/contest/1567/problem/C

Problem - C - Codeforces

B에서 막혀 C로 바로 넘어갔는데 나에게는 너무 어려웠던 문제.

덧셈에서 올림을 다음 자릿수가 아니라 다다음 자릿수에 넘겨주는 방식으로 한다고 할 때 주어진 입력 값 n을 두 양의 정수의 합으로 만들 수 있는 쌍이 몇 개 있는지 출력하는 문제.

올림이 두자리 위로 가기 때문에 홀수 자릿수와 짝수 자릿수의 숫자들은 서로에게 영향을 주지 않는다는 점을 이용해서 홀수 자릿수와 짝수 자릿수를 추출해 두 개의 숫자를 만들면 각각을 정상적인 덧셈으로 만드는 정수 쌍을 찾는 문제로 변한다.

숫자 n을 정수 두 개로 만드는 쌍은 (0, n), ... (n, 0)로 n+1개라는것을 간단하게 알수 있고 홀수 자릿수의 경우의 수와 짝수 자릿수의 경우의 수를 곱해주고 부분적인 경우에서는 0이 될 수 있지만 전체 경우에서는 0이 될 수 없기 때문에 2를 빼준것이 정답이 된다. 시간복잡도는 O(log n).

여전히 A, B, C 문제에서 헤매고 있다. 아이디어만 떠올리면 따로 최적화도 필요없고 대부분 시간복잡도가 커봐야 O(n)인 문제들인데 따로 공부 할 수 있는게 아니라 경험과 수학능력을 요구하는거라 오히려 답답하기도 하다.