Codeforces Round 1035 (Div. 2)

코드포스를 사실 열심히 하진 않아서, 바로 이전 라운드에서 A,B 말리고 F번에 꽂혀 2시간을 버리고 0솔을 한 뒤로 회색 닉네임에 머물러 있었는데, 친구가 민트를 찍었다는 소식을 듣고 위기감을 느껴 이번 라운드에 참여하게 되었다.

A번#

$a \operatorname{XOR} 1$이 의미하는 걸 빠르게 캐치하면 된다. $a \operatorname{XOR} 1$은 항상 $a$의 마지막 비트를 반전시키기 때문에, $a$가 짝수면 $+1$, 홀수면 $-1$의 역할을 한다. 따라서 $a > b$라면 $a$가 홀수이면서 $b$보다 딱 1만큼 클 때만 가능하고, $a < b$라면 짝수일 때는 $a + 1$, $a \operatorname{XOR} 1$로 선택지가 2개인 것을 감안해서 코드를 짜면 된다. 구현은 보자마자 했는데, 비용 $x$와 비용 $y$를 서로 헷갈려서 페널티 -2나 먹고 AC받았다.

B번#

선분들의 위치를 물어보는 게 아니라 가능/불가능 여부만 물어보기 때문에, 어떻게든 거리만 된다면 배치할 수 있다는 확신을 가지고 풀면 된다. 선분들의 길이의 총합보다 점 사이 거리가 멀면 이을 수 없는 건 당연한데, 고려해야 할 게 한 가지 더 있다. 가장 긴 선분의 길이에서 나머지 선분의 길이의 합을 뺀 것이 두 점 사이의 거리보다 길면 안 된다는 것이다. 이는 모든 선분을 사용해야 하기 때문에, 가장 긴 선분은 두 점을 잇는 경로의 어딘가에 존재해야 하고 결국 나머지 선분들을 모두 이었을 때 가장 긴 선분과의 길이의 차가 두 점 사이의 거리보다 길면 어떻게 선분을 연결해도 경로를 만들 수 없게 되기 때문이다. 구현은 간단해서 바로 AC를 받았다.

C번#

코드포스식 애드혹이 바로 이런 게 아닐까 한다. 특히 비트 관련된 문제가 많이 나와서, 그 특징을 알아두는 게 더 편하다고 느낀다.

만약 $n$이 홀수이면, 배열의 모든 값은 $l$이 되는 것이 사전순으로 가장 앞서는 배치인 게 자명하다. 가능한 배열의 원소 중 가장 작은 것이 $l$이고, $n$이 홀수일 때는 모두 같은 숫자일 때 조건식이 항상 성립하기 때문이다. $n$이 짝수라면 어떨까? 우선 $n$이 2일 때 가능한 유일한 경우가 $[0, 0]$인데, $0 < l$이라는 조건이 있기 때문에 $n = 2$일 때 불가능하다. 그것이 아니라면, AND 연산자가 있는 항과 XOR 연산자가 있는 항이 모두 0으로 같아지도록 하는 것이 유일한 방법이 된다. 우선 AND 연산자가 있는 항을 0으로 만들기 위해서는, $l < 2^k \le r$을 만족하는 $2^k$ 꼴의 숫자 $q$가 있어야 한다. 그래야만 $l$과 $q$의 조합을 사용해서 사전순으로 가장 앞서는 배열을 만들었을 때, $l$의 비트 자릿수들을 모두 0으로 가지는 $q$ 때문에 AND 연산자가 있는 항이 0이 되기 때문이다. 이제 XOR 연산자가 있는 항을 보자면, $l$, $q$가 모두 적어도 1개씩 필요함은 자명하다. 그리고 $l$과 $q$는 서로 1인 비트가 겹치지 않는다. 즉, $l$과 $q$ 모두 1인 비트는 없다. XOR 연산자는 각 자리에 1 비트가 홀수 개 있다면 그 비트를 1로 만들고, 그렇지 않다면 0으로 만들기 때문에 $l$과 $q$ 모두 짝수 개 있어야 한다는 결론을 이끌어낼 수 있다. 사전순으로 가장 앞서야 하고 앞선 정의에서 $l < q$이므로 $l$이 $n - 2$개, $q$가 2개 있는 배열이 답이 된다. 즉 $k$가 $1 \sim n - 2$ 사이 index를 물어보고 있다면 $l$을, 그렇지 않다면 $q$를 답하면 된다. $l < 2^k \le r$을 만족하는 $2^k$ 꼴의 숫자 $q$가 없는 경우 어떠한 경우에도 서로 1인 비트가 겹치는 경우가 생기기 때문에 조건을 만족시킬 수 없다.

여담으로 이 문제를 풀면서, 코드포스에서 사용하는 JavaScript는 BigInt 구조체를 못 쓴다는 것을 처음 알았다. 결국 pypy로 AC를 받았다.

D번#

하필 이 글을 쓰는 지금 코드포스 서버가 터져서 문제를 볼 수 없지만, 기억상 $O(N^2)$ 정도의 DP 문제였었다. 당황했던 건 pypy로 풀었음에도 시간초과를 받은 것인데, 아무리 생각해도 $O(N \log N)$으로 풀 수 있을 것 같지가 않아서 상수커팅이나 하다가 대회가 끝났다. 끝나고 소스코드를 둘러보던 중 놀랍게도 D번을 C++로 $O(N^2)$을 구현한 게 AC를 받은 걸 보고 말았다... 언어의 부조리함을 다시 한번 느끼는 순간이었다.