UCPC 2023 예선 후기 (팀명: 관리상의이유로정규식을통과하는팀명만을허용하게되었습니다)

# 팀원 구성

팀원은 cozyyg, kipa00, crescent_h입니다. kipa00과는 UCPC 5번째, 전체 PS 팀 대회로 따지면 8번째, 해시코드까지 합치면 12번째로 함께 나간 대회입니다. 사실 너무 많이 나가서 이 횟수가 맞는지도 잘 모르겠습니다... crescent_h와는 2019년 이후 2번째로 UCPC에 함께 나갔습니다.

팀명이 정해진 과정은 다음과 같습니다.

흔한 디자인 의뢰

이렇게 아무말을 하다 보면 팀명이 완성된다!

그러나 이 팀명이 스코어보드에 쓰이는 일은 없었다

그렇게 팀명을 정하면서 생겼던 고난과 역경을 모두 담은 팀명이 완성되었다

# 대회 준비

팀으로 준비한 건 딱히 없었습니다. 평소에 각자 풀고 싶은 문제를 자유롭게 풀어보면서 대비했습니다.

팀원들은 공통적으로 애드 혹 문제들을 잘 풉니다. 장점이긴 한데, 애드 혹 문제의 경우 실력이 충분하지 않다면 문제 하나에 모든 시간을 쏟아붓고도 풀지 못하는 대참사가 벌어질 수 있기 때문에 양날의 검이라고 생각합니다. 올해도 애드 혹 문제가 나왔는데, H번 문제는 어떻게 되었을까요?

cozyyg가 맛있게 먹었습니다.

# 대회 전략 수립

문제 분배를 제외하고는 크게 신경쓸 부분은 없었습니다.

cozyyg는 문제를 읽는 속도, 그리고 대략의 풀이를 생각해내는 속도가 빠릅니다. 그래서 거의 대부분의 UCPC에서는 A부터 시작하여 3개씩 뛰어넘으며(ADGJ) 읽었습니다. 어차피 어떤 문제를 누가 먼저 읽는지는 팀원들의 대회 경험이 많은 팀에서는 크게 상관이 없지만, 이 방법에는 한 가지 큰 문제가 있었습니다.

cozyyg가 UCPC A번 문제를 풀면 항상 한 번 틀린다.

그래도 다시 한 번 A를 풀어서, 이 징크스를 스스로 끊어낼까 하는 생각도 해봤지만, "아직은 그럴 준비가 안 되었다" 라고 생각했습니다. 그래서 올해는 G H I J K를 읽었습니다. 이 전략은 과연 잘 통했을까요?

실제로 저는 F H I를 풀었고, 팀은 A번을 틀리지 않고 맞았으니, 전략은 꽤나 성공적이었다고 할 수 있습니다.

# 대회 결과

8솔브, 18등으로 예선을 마무리했습니다! 대회 종료 후에 Open Contest가 열려서 스코어보드 공개가 늦어졌지만, 본선 진출에 큰 문제가 없으리라 짐작할 수 있었습니다. 그래서 가벼운 마음으로 링고에 가서 맛있는 치킨과 피자와 오렌지 주스를 즐겼습니다.

# 대회 타임라인

각자 집에서 디스코드로 현황을 공유하다 보면, "이거 제가 짭니다", "D AC"와 같이 타임라인을 짐작할 수 있는 로그가 많이 남습니다. 하지만 올해는 오프라인에서 모여서 대회를 치다 보니, 정확한 시각과 다른 팀원들의 현황은 잘 모릅니다. 그래서 이 글에서는 cozyyg의 타임라인에만 초점을 맞추려 합니다.

(0:00 ~ 0:08) 문제 읽기

문제를 G번부터 순서대로 읽었습니다. 문제를 읽으면서 했던 생각은 다음과 같습니다.

 

G: 일단 tree_set이나 priority_queue 같은 게 필요할 것 같은 문제고, 정말 어처구니없는 쉬운 풀이가 있는 게 아닌 이상, 빨리 풀 수 있는 문제는 절대 아니라고 생각했습니다. (그리고 그런 풀이가 있는지는 중간에 스코어보드를 확인하면 쉽게 판단이 가능하기 때문에, 꼭 빨리 잡을 필요는 없는 문제입니다.)

H: 맛 있 다 !

I: 이런 형태의 문제는 어려워봤자 priority_queue의 간단한 활용 정도니, 다른 쉬운 문제가 없다면 이것부터 풀기로 했습니다.

J: 총 다섯 개의 줄이 주어진다. 라는 문장 하나만으로도, 이 문제가 어려운 문제임을 예상할 수 있었습니다. 그래서 문제 내용만 이해하고 넘어갔습니다.

K: 문제 관상이 너무나도 parametric search였습니다. 그래도 I번보다는 구현에 시간이 걸릴 것 같았고, 다른 사람이 짜도록 하고 내가 H를 짜야겠다 라고 생각했습니다.

 

이런 과정을 거친 결과, 제가 할 일은 I를 짠 다음, 다른 쉬운 문제가 남아있지 않다면, 즐겁게 H를 음미하기 였습니다. 이 때 A와 D는 다른 팀원들이 이미 풀었습니다.

(0:08 ~ 0:14) I 구현

I번 문제의 코딩에 바로 착수했습니다. 생각을 좀 하다 보니 \(a_i - K \cdot i\)와 \(a_i + K \cdot i\)가 중요해 보였고, 이걸 priority queue로 관리하면 되겠다고 생각했습니다. 그런데 어차피 최소만 중요하고 이 값이 \(i\)마다 고정되니까, 최솟값만 들고 있어도 충분하면 된다는 결론이 나왔습니다. 그래서 빠르게 코드를 짰고, 14분 2초째에 낸 코드가 AC를 받았습니다.

(0:14 ~ 0:16) 스코어보드 확인

다른 쉬운 문제가 있지는 않은지 확인해보기로 했습니다. A D I만 많이 풀렸고, 간간히 B나 K를 푼 팀이 있는 정도였습니다. K가 생각했던 대로 전형적인 문제일 것이라는 확신을 가질 수 있었고, 저는 저의 할 일을 하러 가기로 했습니다. 이 때 다른 팀원들은 풀이가 나온 C를 짜고, 일찍 풀린 문제들인 B와 K를 보고 있었던 것 같습니다.

(0:16 ~ 0:57) H 맛있게 먹기 구현

풀이는, 문제 읽기 과정에서 이미 나왔습니다. 작년에 출제했던 돌무더기 게임 1 문제와 밀접한 관련이 있었기 때문에, 문제를 읽자마자 불가능한 경우를 바로 알아낼 수 있었습니다. 그리고 변환이 가역적이라는 점에 착안하여 두 팔찌를 작은 base case로 변환하면 되겠다고 생각했고, 몇몇 경우들을 메모장에 써보고 나니 구현할 준비가 완료되었습니다.

\(RG \rightarrow B\)

\(RRG \rightarrow RB \rightarrow G\)

\(RRR \rightarrow RBGR \rightarrow GGR \rightarrow GB \rightarrow R\)

\(GG \rightarrow RBG \rightarrow RR\)

이런 문제는 Python으로 짜고 싶을 때가 많습니다. 구현을 하다 보면 비슷한 과정을 반복하게 될 때가 많아서, 함수로 잘 분리해줘야 합니다. C++보다 Python이 나을 거라 생각해서 Python으로 구현을 시작했습니다. 여러 함수를 선언해가며 구현을 해나갔고, 한두 번의 디버깅 끝에 예제에 대해 정확한 출력이 나오는 것을 눈으로 확인했습니다. 57분째에 코드를 제출했더니 바로 맞았습니다. 제 코드가 어떻게 만들어졌는지, 자세한 구현 과정을 아래에 써둡니다.

1. 일단 base case를 정합니다. 저는 R, G, B, RR로 정했습니다.

2. 함수를 하나 만듭니다. 이 함수는, 문자열을 입력으로 받아서, 어떤 base case로 환원되는지, 그리고 환원하는 과정을 순서대로 return 하는 함수입니다. 일단 이런 함수를 만들 것이다 라는 사실만 알아두고, 이 함수의 구현은 나중에 진행합니다.

3. 출력 부분을 먼저 만들어줍니다. 환원되는 base case가 다르면 불가능하니까 -1을 출력하고 끝냅니다. 아직 a, b라는 리스트에 뭘 넣을지는 모르겠지만, 일단 출력 형태를 그대로 넣는다고 생각하고 함수를 짭니다. b에 있는 원소는 순서도 뒤집고, 각 쿼리도 뒤집어야 하니까, 쿼리를 뒤집는 함수도 하나 선언해줍니다. 여기까지를 구현하면 다음과 같습니다.

# 1 1 2
# 2 2 R G

def iv(x):
    pass

def f(s):
    pass

_,s=input().split()
_,t=input().split()
q, a = f(s)
r, b = f(t)
if q != r:
    print("-1\n")
    exit(0)
print(str(len(a)+len(b))+"\n")
for x in a:
    print(' '.join(map(str, x)))
for x in b[::-1]:
    print(' '.join(map(str, iv(x))))

4. 이렇게 구현해놓고 iv 함수를 짜려는데, 짤 수가 없습니다. 2 쿼리를 1 쿼리로 바꿀 수는 있는데, 1 쿼리를 2 쿼리로 바꾸려고 보니 색깔을 모릅니다. 그래서 a, b 리스트에 들어갈 형태를 수정해줍니다. 두 쿼리 모두, [쿼리 번호, 왼쪽 구슬의 인덱스, 왼쪽 구슬의 색깔, 오른쪽 구슬의 인덱스, 오른쪽 구슬의 색깔]을 저장하도록 합니다. 이때 원소를 출력하는 것이 조금 복잡해졌기 때문에, show라는 함수를 선언하여 수정하고, 주석도 수정해줍니다. 이제 iv 함수를 구현하려는데, 놀랍게도 쿼리 번호만 바꾸면 됩니다! 이럴 거면 왜 함수로 뺐지 라는 생각이 들 수도 있지만, 한 줄짜리 함수도 큰 의미가 있는 경우가 많습니다. 그대로 둡니다. 참고로 저는 다른 문제를 풀던 중 x, y를 입력으로 받아서 x*y를 return하는 함수도 그대로 둔 적 있습니다. 그 결과 코드 부분마다 실제 곱셈과 해당 프로세스 중 어떤 것을 시행한 건지 구분할 수 있어서 도움이 되었습니다.

import sys
input=lambda:sys.stdin.readline().strip()
print=sys.stdout.write

# 1 1 R 2 G
# 2 2 R 3 G

def show(p):
    if p[0] == 1:
        return f"1 {p[1]+1} {p[3]+1}\n"
    else:
        return f"2 {p[1]+1} {p[2]} {p[4]}\n"

def iv(x):
    return [3-x[0]] + x[1:]

def f(s):
    pass

_,s=input().split()
_,t=input().split()
q, a = f(s)
r, b = f(t)
if q != r:
    print("-1\n")
    exit(0)
print(str(len(a)+len(b))+"\n")
for p in a:
    print(show(p))
for p in b[::-1]:
    print(show(iv(p))

놀랍게도 여기서 f 함수만 구현하면 정답 코드가 완성됩니다. 문제 풀이의 핵심인 이 함수는 여러분이 직접 구현해보세요! 팁을 드리자면, 끝의 2개 또는 3개를 1개로 바꾸는 과정을 반복하면 됩니다. pop과 append는 \(O(1)\)에 되니까 시간 초과를 걱정할 필요가 없습니다.

그 사이 다른 팀원들은 C를 풀었고, K도 조금 뒤에 풀렸습니다.

(0:57 ~ 1:38) F 구현

B가 많이 풀리고 있길래, B를 kipa00이 봤고, 풀이가 생각나긴 했는데 이렇게 어려운 게 어떻게 많이 풀리는 것인지 모르겠다고 했습니다. 그리고 F가 많이 풀리고 있었기 때문에, 귀찮은 자료구조 구현 문제 같다는 kipa00의 의견을 듣고 구현을 시작했습니다.

고민을 좀 하다가 홀수 열 홀수 행에 있는 원소들이 어떻게 이동할지를 생각해보니, 다 함께 움직인다는 사실을 파악했습니다. swap 쿼리가 고민이었는데 kipa00이 던져준 조언을 받아들여서 그대로 짰더니 예제가 거의 나왔습니다. 예제 2에서 출력되는 수의 순서가 살짝 이상하길래, 아무 생각 없이 코드에 있던 몇 개의 -를 +로 바꿨더니 예제가 잘 나왔습니다. 98분째에 제출한 다음 맞기를 기도한 결과 한 번에 맞았습니다. 한 번 틀리기 시작하면 말리기 좋은 문제라서 틀렸다면 정신적 고통이 엄청났을 것 같은데, 운이 좋았던 것 같습니다.

(1:38 ~ 2:08) 러버덕 + 기도

F를 풀고 나서도 B는 계속 kipa00이 구현하고 있었습니다. 쉬운 풀이가 있지 않을까 생각하고 던진 풀이는 안타깝게도 small to large를 생각해내지 못한 저희 팀에게는 \(O(NK)\) 풀이였고, 그 결과 \(\sqrt{N}\)을 기준으로 나눠, 무려 LCA까지 써가며 문제를 해결하는 \(O(N \sqrt{N \log N})\) 풀이를 구현하는 kipa00을 응원할 수밖에 없었습니다. 몇 번의 시행착오가 있었는데, 옆에서 함수를 하나하나 같이 보면서 문제점을 찾아 고쳤습니다. \(\sqrt{N}\)과 같이 산술-기하 평균 부등식으로 결정되는 기준을 잡을 때 저는 가장 큰 값에 대해 최적인 값을 고정값 기준으로 정합니다. 이러한 팁을 전달해주었고, 거기에 연산 속도에 대한 저의 감을 더해 200을 기준으로 잡자는 결론을 냈습니다. 그 결과 128분째에 AC를 받았습니다.

(2:08 ~ 3:00) 남은 문제 감상 및 휴식

남은 문제는 E G J였고, 하나씩 읽어봤습니다. E는 어려운 수학이거나 FFT일 거라 생각했고, 그걸 풀 기운이 남아있는 팀원은 없었습니다. G랑 J는 제 처음 느낌 그대로 풀 만한 문제가 아니었고, 풀 수 있다고 해도 본선 진출이 거의 확정된 시점에서 딱히 풀고 싶지는 않았습니다. 그래서 스코어보드를 보면서 놀았습니다. 그리고 kipa00에게 H번을 던져주고 풀이를 생각해보도록 했습니다. 처음에 H번이 생각보다 너무 안 풀려서 살짝 놀랐는데, kipa00이 푸는 데 걸린 시간을 보니, 제가 비정상적으로 빨리 풀이를 생각한 것이었습니다.

# 짧은 후기

문제를 잘 풀어낸 것 같아서 기쁩니다. B번 문제의 경우 최근 커뮤니티 대회의 트렌드였다고 하는데, 요즘 들어 커뮤니티 대회에 별로 참여를 못 해서 잘 몰랐던 것 같습니다. 트렌드를 따라가는 일은 정말 어려운 것 같습니다. H번 문제를 너무 재밌게 풀었고, 지금도 계속 문제를 풀어냈던 과정이 떠오를 정도로 인상적이었습니다. 다른 까다로운 문제들을 잘 풀어주고, 문제를 안 풀고 있을 때도 모니터로 제가 풀던 문제의 입력 형식과 예제를 띄워주고 러버덕이 되어준 팀원 kipa00, crescent_h에게 정말 고맙다는 말을 해주고 싶습니다. 그리고 앞으로도 애드 혹 강자로서의 입지를 더더욱 굳혀나가고 싶습니다. 본선도 화이팅!