Codeforces Round 937 (Div. 4)

달콤한 꿈을 꾸었다. 백준과 코드포스 그리고 앳코더를 통틀어 대회 사상 최초로 모든 문제를 시간 안에 푼다는 달콤한 꿈... 그 꿈은 ps_gallery의 잔혹한 핵과 함께 산산이 흩어지고 말았다. 인생 첫 핵이라 기분이 좀 많이 묘하다.

사실 그렇게 잔혹하지는 않았다.  Div. 2에서 이걸 당했으면 땅을 치고 울었겠지만 Div. 4를 통해서 내 레이팅이 변할 수 없었던 터라서 그렇게 핵의 무게가 무겁지는 않았다. 이번 핵으로 얻은 교훈이 더 많다. 물론 38개의 프리테스트를 만들어 놓고는 개중 단 하나도 커팅 조금 한 단순한 백트래킹을 저격하지 않은 운영진은 살짝 아쉽지만... 다른 문제는 마음에 들었고, 무엇보다 내 마음에 쏙 드는 문제만 있는 대회만 있을 수는 없다.

Contest Submissions :: Hacked

반성할 점

F에서 급히 코드를 작성한다고 제수를 \(a+1\)이 아니라 \(a\)로 작성하여 한 번 WA를 받은 것.

그리고 G를 비트필드 DP가 아니라 백트래킹 DFS로 오해하여 세 번의 제출에도 결과적으로 AC를 따내지 못한 것. 이건 내가 배움이 짧아 웰노운도 잘 모르기 때문이라서 당장이라도 배워야 하지 않을까 싶다. 아직 모르는 게 너무 많다. 배움이 짧은 것 뿐만이 아니라 너무 순조롭게 흘러가서 G의 난이도를 매우 과소평가한 것도 문제이기는 하지만... 주된 문제점은 배움 부족이기 때문에.

 

첫 올솔에 눈이 멀어서 G를 과소평가한 게 이번 Div. 4에서의 내 패인이 아닐까 싶다. A부터 F까지 너무 술술 잘 풀려서 G에 본격적으로 도전한 30여분 간은 시야가 너무 좁아졌었다.

 

0:01 A AC

def solve():
    a,b,c = map(int,input().split())
    if a < b:
        if b < c: print('STAIR'); return
        elif b > c: print('PEAK'); return
    print('NONE'); return
for _ in range(int(input())): solve()

 \(a<b<c\)인지 \(a<b>c\)인지 아니면 둘 다 아닌지를 가리는 문제. Div.4의 A 치고는 구현량이 많지만 요구하는 게 너무 단순한 나머지 쉽게 슥삭 할 수 있었다.

 

0:04 B AC

def solve(N):
    hol = [['#' if (i%4<2 and j%4<2) or (i%4>1 and j%4>1) else '.' for j in range(2*N)] for i in range(2*N)]
    for row in hol: print(''.join(row))
for _ in range(int(input())): solve(int(input()))

사실 여기서 시간을 좀 더 줄일 수 있었다. \(\lfloor\frac{i\bmod4}{2}\rfloor=\lfloor\frac{j\bmod4}{2}\rfloor\)이면 해당 칸이 #, 안 그러면 .임을 이용할 수 있었는데, 처음에 그냥 4로 나눈 나머지의 합으로 접근했어서 허둥대다가 시간을 좀 날려먹었다. Div. 3이나 Div. 4에서는 스피드포스로 처음 네다섯 문제를 되는 한 빨리 끊기 위해서 서두르다 보니 거꾸로 늦어지는 감이 있다. 침착함이 필요하다.

 

0:07 C AC

def solve():
    x,y = map(int,input().split(':'))
    if x+y == 0: print('12:00 AM'); return
    am = 'AM' if x<12 else 'PM'
    x = 12 if x%12==0 else x%12
    print(f'{str(x).zfill(2)}:{str(y).zfill(2)} {am}'); return
for _ in range(int(input())): solve()

12시를 00시로 출력하지 않는 것이 관건이다. 여기서도 필요가 없는 세 번째 줄을 굳이 집어넣음으로서 시간을 소모했지만 조금 더 각 잡고 코드를 예쁘게 꾸미려면 꾸밀 수 있을 것 같다.

 

0:11 D AC

binary = [int(bin(i)[2:]) for i in range(2,64)]
def solve(N):
    for i in binary[::-1]:
        while N%i == 0: N//=i
    if N == 1: print('YES')
    else: print('NO')
for _ in range(int(input())): solve(int(input()))

1001이 예제에 없었으면 난 100%의 확률로 작은 수부터 탐색하다가 터져죽었을 것이다. \(1001=11\times91\)이다. Proof by AC로 대충 때워 넘겼지만 지금 이 후기를 쓰는 와중에 증명을 하려고 에디토리얼을 참고했는데, 끔찍하기 그지없는 시간복잡도가 튀어나와서 기겁하고 도망쳤다.

\[\mathcal O\left(n^{\log_{10}\left(\frac{2+\sqrt[3]{395-3\sqrt{16881}}+\sqrt[3]{395+3\sqrt{16881}}}{3}\right)}\right)\]

을 시간복잡도로, 정확하게는 시간복잡도의 조금 널널한 상계로 가지는 문제라니 뭐 이런...... 물론 시간복잡도 식의 복잡성과 실제 풀이의 난이도가 전혀 상관은 없다만 그럼에도 불구하고 거부감이 느껴지는 것은 어쩔 수가 없는 것이다.

 

0:15 E AC

def solve(N):
    s = input()
    for i in range(1,1+N//2):
        if N%i == 0:
            prefix,suffix = s[:i],s[-i:]
            pre,suf = 0,0
            for j in range(N):
                if prefix[j%i] != s[j]: pre += 1
                if suffix[j%i] != s[j]: suf += 1
            if pre < 2 or suf < 2: print(i); return
    print(N)
for _ in range(int(input())): solve(int(input()))

다음 문제를 푸시오. 4354 문자열 제곱

뭔 뜬금없이 KMP 플래티넘 문제냐고 묻겠지만 풀이의 골자는 거의 같다. 애초에 저것도 이 문제도 KMP를 전혀 안 쓰고도 풀 수 있다!

문자열 길이 \(N\)의 약수 \(d\)에 대해서, 문자열의 첫 \(d\)문자 혹은 마지막 \(d\)문자를 반복하여 길이 \(N\)으로 늘였을 때 최대 한 글자만 달라지는 경우가 있느냐? 이건 각 약수마다 \(\mathcal O(N)\)번만에 처리가 가능하며, 문자열 길이는 최대 20만이고, 이 이하의 정수 중 약수는 많아봤자 200개를 넘지 않는다. 약수 개수에 대한 브루트포스로도 손쉽게 해결이 가능하단 소리다.

 

0:34 F AC (+1)

from math import log2,floor,ceil
from sys import stdin
input = stdin.readline
def solve():
    a,b,c = map(int,input().split())
    if c-a != 1: print(-1); return
    if a+b == 0: print(0); return
    if a == 0: print(b); return
    k = floor(log2(a)); residue = 2**(k+1)-1-a
    if residue >= b: print(k+1); return
    print(1+k+ceil((b-residue)/(a+1)))
for _ in range(int(input())): solve()

맨 처음, 정점이 0개인 미완성 트리에 추가할 수 있는 리프 노드의 수가 1개라고 정의하자. 리프 노드를 degree \(d\)인 정점으로 바꿔 주면 리프 노드 하나가 줄어드는 대신에 새로 추가된 정점의 \(d\)개의 자식으로 리프 노드를 추가할 수 있으므로 추가할 수 있는 리프 노드의 수가 \(d-1\)개 늘어난다.

따라서 자식이 2개인 정점 \(a\)개와 자식이 1개인 정점 \(b\)개에 대해서, 이 정점들로만 만든 미완성 트리에 추가할 수 있는 리프 노드의 수는 \(a+1\)개가 된다. 처음에 1개가 있었으므로... 자식이 0개인 정점은 모조리 리프 노드가 된다. 리프 노드가 들어갈 수 있는 자리의 수와 리프 노드의 수가 일치해야 하고, 그러니 \(a+1\ne c\)이면 트리를 만들 수가 없다.

트리를 만들 수 있을 때 높이를 최소화하려면 어떻게 해야 할까? 그리디하게 가장 루트 노드에 가까운 놈들부터 자식이 2개인 정점으로 채워 버리면 된다. 그러면 너비가 넓어질 테니까 높이는 당연히 낮아진다. 그 다음 자식이 1개인 정점은 놓을 수 있는 모든 자리에다가 붙이고, 자식이 0개인 정점은 안 봐도 된다. \(c=a+1\)이므로 높이를 정확히 1 높이는 것밖에 못 한다.

 

1:08 G AC (+2) → Hacked (-3)

from sys import stdin
input = stdin.readline
max_cnt = 0
def solve(N):
    global max_cnt
    songs = [input().split() for _ in range(N)]
    if N == 1: print(0); return
    graph = [[] for _ in range(N)]
    for i in range(N-1):
        for j in range(i+1,N):
            if songs[i][0] == songs[j][0] or songs[i][1] == songs[j][1]:
                graph[i].append(j)
                graph[j].append(i)
    max_cnt = 0
    vst = [False]*N
    def dfs(v,cnt):
        global max_cnt
        if max_cnt == N: return
        if cnt == N: max_cnt = N; return
        vst[v] = True
        for i in graph[v]:
            if not vst[i]: dfs(i,cnt+1)
        vst[v] = False
        if cnt > max_cnt: max_cnt = cnt
    for i in range(N): dfs(i,1)
    print(N-max_cnt)
for _ in range(int(input())): solve(int(input()))

Hacked라니 이처럼 마음 아픈 여섯 글자가 없다...

내 코드는 제법 커팅을 한 백트래킹 DFS 코드이다. 이 코드의 로직이 큰 문제점이 있는 건 아니고, 그냥 이 코드의 시간복잡도가 내가 지금까지 백트래킹의 시간복잡도로 알고 있었던 \(\mathcal O(2^N)\)이 아니라 \(\mathcal O(N!)\)이었던 게 문제였다. 시간제한 3초에 비해 이 코드가 돌아간 시간이 186ms로 매우 짧아서, 아무리 시스탯이 돌더라도 코드의 목이 날아갈 거라는 생각을 전혀 못 했는데, 그냥 DFS로 풀리는 문제라고 남에게 이 코드를 보여주자마자 내 코드의 모가지가 날아갔다. 뭐 이런;;;

외판원 순회와 비슷한 bitfield DP로 풀린다고 한다. 일단 내가 그 유형 문제를 풀어 본 적은 없어서 오늘부터 공부한 뒤에 조만간 업솔빙으로 제대로 된 풀이를 내 보도록 하겠다. 공부에 얼마만큼 시간이 걸릴지는 예상 못 하였지만...