UCPC 2022 인터넷예선 후기

• Team
• 팀연습
• 대회
  • A. 코딩은 체육과목 입니다
  • B. N수매화검법
  • J. 수 정렬하기 (근데 이제 제곱수를 곁들인)
  • E. solved.ac 2022
  • F. Twitch Plays VIIIbit Explorer
  • D. Functionx
  • G. SCV Chain
  • H. yo, i herd u liek ternary operators, so..
• After Contest

• 본문에서 언급되는 난이도 티어 (브/실/골/플/다/루) 는 Solved.ac 기준입니다.

Team

올해는 조금 새로운 구성으로 UCPC 2022에 출전하기로 했습니다. Hashcode 때 함께하던 DHDroid, Coffeetea, Dlwocks31 중 저랑 DHDroid가, Coffeetea와 Dlwocks31이 각각 팀을 구성하고 한명을 더 영입(?) 하기로 헀는데, 마침 저랑 안면이 있던 Stet-stet 이 연락이 닿아 함께하기로 했습니다.

DHDroid는 그동안 항상 같이 PS를 해왔는데, 최근 저희 모두 PS를 쉬긴 했지만 작년 SCPC때 보여준 실력으로 보아 크게 실력이 degrade한것 같지는 않습니다.

Stet-stet은 같이 대회를 뛴건 처음이지만 개인적으로 DHDroid와 비슷한 느낌을 받았습니다. 둘 다 저보다 construction이나 DP같은 문제들에 전반적으로 강한 편입니다.

팀연습

예선을 대비한 팀연습을 한번 돌았습니다. BAPC 2021 (5시간 1PC) 대회를 3시간 3PC로 돌았는데, 무려 9솔브를 할 수 있었습니다.

팀연습을 통해 대충 각자 코포 퍼플 턱걸이 정도 퍼포먼스는 맞출 수 있는걸 확인했고, 저희 입장에서는3PC일 때 나름대로의 전략(?) 을 구조화할 수 있었습니다.

• 코딩속도가 제가 제일 빠르므로, 쉬운문제(브론즈~골드 하위) 를 최대한 제가 빨리 쳐냅니다.
• 각자 플래티넘 정도 난이도 문제 하나를 잡고 해결합니다.
• 플 상위 ~ 다이아 하위 정도 문제 하나를 같이 잡고 풀면 완성

이 방법이 정확히 execution 가능하다면 플레 이하의 모든 문제 + 4개를 풀 수 있어야 합니다. 예년의 난이도를 기준으로 7솔브 정도를 기대할 수 있었습니다.

대회

35도에 근접한 폭염 중에 대회를 치르게 되었습니다.

저희는 딱히 예선 탈락 여부를 걱정하지는 않기 때문에, 부담없이 대회에 임할 수 있었습니다.

A번쪽에 쉬운문제를 한두개 넣어주는 전통에 따라, 제가 앞 / Stet-Stet이 중간 / DHDroid가 뒤 문제를 먼저 읽기로 했습니다.

A. 코딩은 체육과목 입니다

난이도 : B5             AC Time : 00:01
code : gratus907

정답 스포 : print("long "*(int(input())//4) + "int") 를 하면 됩니다.

B. N수매화검법

난이도 : G2             AC Time : 00:12
solve : gratus907     code : gratus907

말이 조금 어렵습니다. 선분들을 들어온 역순으로 생각하면 내공의 소모량은 다음과 같습니다.

(이미 들어와 있는 선분들과, 새로 추가되는 선분의 교차점의 개수) x (새로 들어오는 선분의 가중치)

이 값의 합을 최소화하는 순서를 찾아야 합니다.

어떤 순서로 베기를 수행하든, 마지막에 나오는 그림은 똑같습니다. 그리고 그 그림에서 나타나는 임의의 교차점이 선분 $a$와 $b$의 교차로 인해 만들어졌다고 할 때, 그 교차점에 의해 추가되는 내공 소모량은 (a와 b 중 늦게 들어온 것의 가중치) 와 같음을 관찰합니다. 그렇다면, 무조건 일단 비싼 동작을 처리해야 최대한 나중에 낮은 소모값을 얻을 수 있습니다.

따라서, 가중치 순으로 정렬하고 하나씩 선분을 추가하면서 새로 생기는 교차점의 개수를 세면 충분하고, $n$이 작으므로 $O(n^2)$ 에 풀어도 됩니다.

다만 우리는 앞서 순서를 거꾸로 보았으므로 실제로는 가중치가 낮은 선분부터 넣어야 합니다.

선분교차 판별이 몹시 귀찮은 일이지만, KACTL 라이브러리의 기하를 통째로 팀노트에 가지고 있기 때문에 무지성으로 가능합니다. :)

DHDroid는 J가 가장 쉬운 것으로 판단, J를 풀러 갔고 Stet-Stet은 E와 F 모두 쉬운데 구현문제라는 말과 함께 G를 향해 떠났습니다.

J. 수 정렬하기 (근데 이제 제곱수를 곁들인)

난이도 : G1             AC Time : 00:31
solve : DHDroid       code : DHDroid

무슨 문제인지는 잘 모르겠지만, $ab, bc$ 가 모두 제곱수라면 $ac$ 가 제곱수인 뭐 그런 관찰을 이용하는 문제였다고 합니다. DHDroid가 읽다가 잡고 금방 해결해 왔습니다.

이제, 쉬운 문제로는 E와 F가 남아 있고 / 나름대로 “해결해야 할 플레 문제” 로 D, G, H 정도를 남겨두고 있었습니다. 만약 5문제를 모두 해결해서 8솔브를 할 수 있다면 꽤 높은 등수를, 4문제만 해결해도 무난히 진출할 것으로 전망하였고 E랑 F는 제가 잡고 금방 어떻게 풀 수 있을 것 같아 보였기 때문에 Stet-Stet이 G를, DHDroid가 H를 먼저 잡았습니다.

E. solved.ac 2022

난이도 : G2             AC Time : 00:32(+1)
code : gratus907

공식을 그대로 구현하는 문제인데, 날짜를 파싱 해야 하는 끔찍한 구현이 있습니다. 제가 python의 datetime 라이브러리 사용법을 검색해가며 해결했습니다. ICPC에 이런 문제가 나온다는 것은 상상할 수 없는 일이지만, 예선이니 뭐… 여러가지 새로운 것들이 등장하는 게 아닌가 싶습니다.

• 1년으로 나눠야 할걸 하루로 나눠서 한번 틀렸습니다. :(

F. Twitch Plays VIIIbit Explorer

난이도 : G5             AC Time : 00:53
solve : Stet-stet     code : gratus907

2D 그리드에서 정해진 순서대로 아이템을 먹고 맨 끝으로 내려가는 문제로, “주어진 move 수의 한계” 가 매우 크다는 점을 관찰하면 naive하게 마구 움직여도 됩니다. 각 알파벳별로 위치를 모두 찾아놓고 그냥 순서대로 먹으면 되기 때문에 딱히 난점은 없습니다.

제가 E를 풀고 F를 읽어보는 중에, stet-stet이 “이거 사실 움직이는 횟수 제한이 없고 최단경로를 안찾아도 돼서 막 돌아도 된다” 고 알려줘서 바로 구현했습니다.

D. Functionx

난이도 : P4             AC Time : 01:18
solve : gratus907     code : gratus907

E를 잡기 전부터 조금씩 생각해 보고 있던 문제입니다. 쿼리가 주어지는데, 가지고 있는 $f(x)$ 에다가 $ax + b$ 가 들어오면 그걸 곱해서 $f_2(x)$ 를 만드는 쿼리와 상수 $c$에 대해 가지고 있는 다항식 $f$를 evaluate해서 부호를 판단하는 쿼리가 주어지고 이를 빠르게 처리하고자 합니다.

결국 중요한 것은, $ax + b$에서 기억해야 할 것은 절편만 기억하면 됩니다 (evaluate를 부호만 확인할 것이므로). 이 절편들을 $x_1, \dots x_n$ 이라고 하면, 이들 중 어떤 수 $c$가 들어왔을 때 $c$보다 작은것이 몇개인지 / 큰것이 몇개인지 파악할수 있으면 끝.

이는 Segment tree 또는 Order-statistics tree로 뚝딱할 수 있습니다. 다만.. $x_i$ 가 정수가 아닌 유리수일 수 있어서, 원래는 유리수를 저장하는 OST를 짜야 하는데 이것이 매우 귀찮습니다. double로 구현해서 맞을지는 잘 모르겠지만 어차피 들어오는 값 $c$가 모두 정수이므로 정수와의 대소만 판별하면 되기 때문에, 모든 정수를 $\times 2$ 해서 저장하고 정수가 아닌 유리수들은 홀수에 저장하는 식으로 구현했습니다.

G. SCV Chain

난이도 : P4             AC Time : 01:53(+3)
solve : Stet-stet     code : Stet-stet

Stet-stet이 DHDroid랑 얘기를 좀 하더니 구현을 한참동안 잡으러 갔던 문제입니다. 설명을 안들어서 무슨 문제인지는 정확히 모르겠습니다.

H. yo, i herd u liek ternary operators, so..

난이도 : P3             AC Time : 02:33(+3)
solve : Together      code : Stet-stet

재밌는 문제였고, 세명이 차례대로 관찰을 쌓으면서 풀이를 incremental하게 발전시키는 연습을 해볼 수 있었습니다.

Ternary operator들이 ?:??:???:::: 같은 형태로 주어져 있을 때, 이들 사이에 괄호와 변수를 끼워넣어서 만들 수 있는 올바른 evaluation의 개수를 세는 문제입니다.

• 이 문제는 DHDroid가 꽤 오래 붙잡고 있었습니다. 뭔가 조합론/DP스러운 문제를 워낙 잘 푸니까 별 무리없이 풀어낼것으로 생각했는데, 무엇보다 작은 케이스를 손으로 해보기가 너무 어려워서 규칙성을 찾는데 많은 어려움이 있었습니다.
• DHDroid가 많은 아이디어를 제안했고, 결국 뭔가 재귀적인 formulation을 찾아내었습니다. “단순한 케이스” 에 대해서는 $O(n^2)$ 시간에는 어떻게 풀 수 있어 보였습니다.
• FunctionX(D) 를 푼 다음, 저도 거의 한시간 가까이를 이 문제를 노려봤습니다. “괄호와 변수를 끼워넣어서 만들 수 있는 올바른 evaluation” 이라고 써놓고 보니 카탈란 수열처럼 들립니다. DHDroid가 제안한 점화식도 카탈란 formulation이 가능했습니다.
• “이거 그냥 답이 카탈란 아닌가?” 라고 생각해서 내고 WA를 받았습니다. 다만 “간단한 경우” 에 답이 카탈란 수열임은 거의 확신을 가질 수 있었습니다.
• Stet-Stet이 이것저것 생각해보더니 스택 + 카탈란을 쓰면 된다는 사실을 알아냈습니다. 괄호 문자열 문제를 풀 때 쓰는 두가지 방법을 동시에 쓰는 신기한 구조가 되었는데.. 결국은 스택에 집어넣다가, 뺄 때 카탈란 수열을 이용해서 경우의 수를 구하는 형태가 되었습니다.

After Contest

본선 진출은 7솔브면 충분해 보였고, 8솔브를 했기때문에 별 부담은 없었습니다. 결과적으로는 7솔브가 커트라인이었고 저희 팀이 22등인 것을 보면 생각보다 전반적으로 PS판의 수준이 너무 많이 올라간 거라는 생각이 듭니다. B번 문제를 한 30분정도 같이 논의하다가, 풀이 비슷한걸 생각하긴 했는데 시간도 없고 구현도 어려워서 그대로 해산했습니다. 본선을 위해서는 팀연습도 몇판 돌고 들어갈것 같은데 한 15등 정도를 조심스럽게 목표해 보고 있습니다.

오랜만에 팀대회 뛰는건 너무 재밌었습니다. 3시간에 3PC다보니 거의 컴퓨터 앞에만 붙어있었던 것 같은데, 본선에서는 좀더 종이와 펜 + Discussion하는 시간을 기대하고 있습니다.