Codeforces Round 1035 (Div. 2)

 

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

 

A번

a XOR 1 이 의미하는걸 빠르게 캐치하면 된다. a XOR 1은 항상 a의 마지막 비트를 반전시키기때문에, a가 짝수면 +1, 홀수면 -1의 역할을 한다. 따라서 a > b 이라면 a가 홀수이면서 b보다 딱 1만큼 클때만 가능하고, a < b 이라면 짝수일때는 a + 1, a 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 <= 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 ~ n-2 사이 index를 물어보고 있다면 l을, 그렇지 않다면 q를 답하면 된다.  l < 2^k <= r 을 만족하는 2^k 꼴의 숫자 q가 없는 경우 어떠한 경우에도 서로 1인 비트가 겹치는 경우가 생기기때문에 조건을 만족시킬 수 없다.

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

 

D번

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

+ 에디토리얼을 보니 N^2 풀이가 맞고, 내 코드는 그냥 구현이슈였다.