Codeforces Round 930 (Div. 2)

오늘은 두 번째 Codeforces 후기이다. 매우 만족스러운 결과라서 후기로 아니 남길 수가 없다.

보랏빛 퍼포먼스

3문제, 2526점으로 전체 323등에 오르면서 무려 1985, 퍼플 퍼포먼스를 기록했다. 예측기는 블루 승급은 따놓은 당상이라고 하는데... 정말 그대로 되었으면 좋겠다.

Became Expert

되었다, 블루가.

 

반성할 점

B를 풀 때 디버깅용 손풀이를 만들지 않은 채 그대로 낸 것. 그러지만 않았어도 50점을 공중에 날릴 일은 없었다. 이 50점이 퍼포먼스에서도 50점의 차이점을 만들었다는 걸 생각하면 다른 게 다 좋았는데도 아쉬울 수밖에 없다. 퍼플 퍼포먼스는 실력이 더 뛰어오르기 전까지는 힘들지도 모른다는 사실 때문에 더더욱.

 

0:02 A AC

from math import log2,floor
def solve():
    print(2**floor(log2(int(input()))))
for _ in range(int(input())): solve()

1은 swap(2) 때문에 2번 자리에 가게 된다. 만약 1이 swap(k)로 k번 자리에 가게 된다면 그 다음으로 k번 자리를 움직일 수 있는 것은 k를 가장 큰 약수로 가지는 2k가 만드는 swap(2k)이다.

1의 위치에 변동이 생기는 매 swap마다 1의 위치를 나타내는 번호는 정확히 2배가 된다. 따라서 정답은 \(N\) 이하의 가장 큰 2의 거듭제곱.

 

0:18 B AC (+1)

def solve():
    N = int(input())
    array = [list(map(int,input())) for _ in range(2)]
    ans,cnt = [array[0][0]],1
    for i in range(1,N):
        x,y = array[0][i],array[1][i-1]
        if x==y: cnt += 1; ans.append(x)
        else:
            if x>y:
                print(*array[0][:i],*array[1][i-1:], sep='')
                print(cnt); return
            else:
                ans.append(0); cnt = 1
    ans.append(array[-1][-1])
    print(*ans,sep='')
    print(cnt)
for _ in range(int(input())): solve()

더 작은 문제로 분할해서 풀 수 있다. 현재 위치가 \((0,i)\)일 때 경우를 생각하면.

바로 오른쪽 칸과 바로 밑 칸에 같은 숫자가 존재한다면 경로의 숫자가 정확히 하나 늘어난다. 만약 밑 칸이 1이면서 오른쪽 칸이 1이면 아래 이동이 강제되면서 답이 이 시점에서 결정되어 버린다. 만약 밑 칸이 1이고 오른쪽 칸이 0이면 오른쪽 이동이 강제되면서 더 작은 문제로 변형 가능하다.

이걸 종합적으로 고려해주면서 풀면 된다. Div.2 B번 치고는 조금 매콤한 맛이 나긴 했지만...

 

0:58 C AC

from sys import stdin
from math import log2,ceil
input = lambda: stdin.readline().strip()
def solve(N):
    i = 0
    for j in range(1,N):
        print(f'? {i} {i} {j} {j}', flush=True)
        if input() == '<': i = j
    j = [0]
    for k in range(N):
        print(f'? {i} {j[0]} {i} {k}', flush=True)
        state = input()
        if state == '<': j = [k]
        elif state == '=': j.append(k)
    temp = j[0]
    for item in j:
        print(f'? {temp} {temp} {item} {item}', flush=True)
        if input() == '>': temp = item
    print(f'! {i} {temp}', flush=True)
for _ in range(int(input())): solve(int(input()))

아이디어가 중요한 인터랙티브 문제가 나오면서 영혼을 탈곡해 버렸다. 이 문제를 보고 15분쯤 문제를 해석하는 데에만 시간을 쓴 것 같다. 어떻게 or 연산만 가지고 xor가 최대가 되는 쌍을 찾을 수 있다는 건지도 모른 채 죽어라 헤맸다.

답으로 이끌어 주는 것은 \(3N\). 인터랙터에게 질문할 수 있는 기회이다. 당연히 \(p_i \text{or} p_i\)는 \(p_i\)이므로, \(N\)번 질문함으로서 최대 원소 \(N-1\)이 어디에 있는지 확인 가능하다. 그리고 다시 \(N\)번 질문함으로서 \(N-1\)과 or 한 값이 가장 큰, 정답 후보를 얻을 수 있다.

나머지 \(N\)번의 연산은 어디다 쓰는 게 좋을까? 가능하기는 할까? 정답 후보들의 공통점은 \(N-1\)의 0 비트가 있는 자리가 1 비트로 채워져 있다는 것이다. 왜? \(\max_{1\le i<j\le N}p_i\oplus p_j\)는 모든 비트가 1이기 때문에. \(N-1\) 이하의 가장 큰 2의 거듭제곱 \(2^r\)과 \(2^r-1\)을 xor한 값이 모든 비트가 1이기 때문이다.

1이 있어야 할 특정한 비트 빼고는 다 0인 것이 xor를 최대로 만드는 것은 자명하다. 중복한 1은 오히려 xor를 줄이니까. 그런데 이건 후보들 중 최솟값이기까지 하다. 그럼 남은 것은 자명하게도, 모든 후보를 순회하면서 \(N-1\) 위치를 알아냈듯이 후보를 순회하면서 최솟값을 찾으면 끝이다.