Semi-Game Cup 3 후기

지인이 연 백준 대회인데, 홍보를 열심히 하고 다니길래 궁금해서 A만 풀고 스코어보드 구경이나 하려고 했다.

정신을 차리니 ABCFH를 풀고 D를 뇌절하며 눈물을 흘리고 있었다.

---

A. 루나의 게임 세팅

$N$과 $K$가 주어질 때, $1$부터 $N$까지의 수에서 $K$개를 골라 만들 수 있는 바이토닉 순열의 개수를 출력하라.

$N$개에서 $K$개 고르는 방법 수는 그냥 조합이고, 고른 다음에 바이토닉하게 $K$개를 재정렬하는 방법의 수가 핵심이었다.
생각해보면 그냥 제일 큰 거 고정하고 양쪽에 큰거부터 추가하는 것과 동치였다. $K - 1$개 왼쪽 / 오른쪽 선택하는 거니까 결국 $2^{K-1}{N \choose K}$이 답이다.

풀이가 쉬워서 대회 끝나고 한 'A는 실5~4쯤 되지 않나?'라고 말하려 했는데, 생각해보니 이항계수는 실버 상위고 모듈러 역원은 골드 중상위였다. 사실 $N \le 2000$ 이라 모듈러 역원은 필요없긴 했는데, 검수 중엔 모듈러 역원 쓰는 버전을 다들 실3으로 평가했다고 한다. 내 생각에도 제곱보다 역원이 쉬운 것 같긴 하다 ㅎㅎ;

B. 다오와 트리플 멕스 게임

배열 $A$가 주어진다.
$A$에서 임의의 subsequence를 골라 $\mathbf{mex}$ 값을 배열 $B$의 끝에 추가할 수 있다.
배열 $B$에서 임의의 subarray를 골라 $\mathbf{mex}$ 값을 배열 $C$의 끝에 추가할 수 있다.
두 연산은 모두 원하는 만큼 시행 가능하다. 배열 $C$의 $\mathbf{mex}$ 값을 최대화하여라.

일단 $B$에는 $0$부터 $A$의 $\mathbf{mex}$ 값까지 원하는 순서대로 원하는 만큼 추가 가능하다. 대충 $0$부터 쭉 나열해놓고 $C$로 넘어가면, 얘도 그냥 $B$의 $\mathbf{mex}$값까지 추가 가능하다. 그래서 그냥 $A$의 $\mathbf{mex}$값에 2 더한 게 답이다.
사실 예외가 있는데, $A$에 $0$이 없으면 $0$이 답이고, 그 외에 $A$의 크기가 $1$이면 $1$이 답이다.

문제 설명이 살짝 꼬여 있어서 뇌절을 좀 했는데, 풀이 자체는 상당히 쉬운 편이다.

C. 공 꺼내기 게임

크기가 $N$인 배열 $A$, $B$와 확률 $q$가 주어진다. $i$가 적힌 공이 빨간 주머니에 $A_i$개, 파란 주머니에 $B_i$개 들어 있다.
빨간 주머니 혹은 파란 주머니에서 임의로 공이 주어진다. 당신은 적힌 번호 $i$를 보고, $P_i$ 확률로 빨간색이라 답하고 $1 - P_i$ 확률로 파란색이라 답해야 한다.
파란 주머니에서 꺼낸 공을 빨간 색이라 답할 확률이 $q$ 이하여야 할 때, 빨간 주머니에서 꺼낸 공을 빨간 색이라 답할 확률을 최대화하는 $P$ 배열을 구하여라.

빨간 주머니에 든 공의 개수가 모두 $X$개, 파란 주머니는 $Y$개라 하자.
$i$번 공이 주어졌을 때 빨간 걸 옳게 답할 확률 $R_i$는 $\frac{P_i A_i}{X}$다. 파란 걸 틀리게 답할 확률 $Q_i$는 $\frac{P_iB_i}{Y}$다.
식을 $P_i$에 대해 정리해보면, 각각 $P_i = \frac{R_i X}{A_i}$, $P_i = \frac{Q_i Y}{B_i}$가 된다. 따라서 $R_i = Q_i \frac{Y}{X} \frac{A_i}{B_i}$가 된다. 우린 $Q_i$를 최소한으로 증가시키며 $R_i$를 최대한 증가시키고 싶다. $\frac{Y}{X}$는 상수이니 무시하면, $\frac{A_i}{B_i}$가 클 수록 $Q_i$를 늘릴 때 $R_i$도 크게 증가한다. 그래서 저걸로 정렬하고 위 정의들에 따라 $P$를 쭉 계산해주면 된다.

'빨간 주머니 혹은 파란 주머니에서 임의로 공이 주어진다' 부분이 색도 랜덤하게 고른단 건지, 색을 임의로(악의적으로) 고를 수도 있단 건지 좀 모호해서 고민을 했다. 근데 다들 쓱쓱 풀길래 그냥 믿고 풀이를 냈다.
식으로 쓰니 한 플래 하위쯤 될 것 같이 보이는데 난 대충 찍고 풀어서 골드 줬다.

H. 정령과 눈 감고 숨바꼭질 게임

여기부턴 따로 디스크립션 요약을 쓰진 않겠다. 너무 길어...

애들의 좌표를 다 저장하기엔 연산의 횟수 제한이 너무 빡세다. 대신 애들 $9$명이 각각 사분면 어디에 위치해 있는지는 $4^9 = 262144$ 이하의 수로 나타낼 수 있다. $23^4 = 279841$다. 그래서 그냥 2x2 격자로 쪼개고 주변 값을 쭉 읽으면 끝이다.

문제를 제대로 못 봐서, '뭐지? 애들 무게중심을 찾아서 뭔가 해야 하나? 사실 배열 각각에 쓸 수 있는 건 페이크고 Find 연산으로 찾은 좌표 + Get으로 4개 읽어서 $\lg(200^2 \times 23^4)$ 비트 안에서 뭔가 해야 되나?' 하고 뻘생각을 많이 했다.
$|x| \leq 1, |y| \leq 1$란 조건을 본 순간 탄식이 나오며 $\lvert i_{k} - i_{0} \rvert > 1, \lvert j_{k} - j_{0} \rvert > 1$이랑 Get을 최대 네 번만 쓸 수 있단 조건이 달려있던 이유와 함께 1분만에 풀이가 도출됐다. 너무 허망했음...
난이도는 골1로 줬는데 동의하지 않는 사람이 꽤 많은 것 같다. 근데 플래 중상위 ~ 다이아로 평가하기엔 대회 때도 초반 솔브 빠르게 나왔던 데다가 ABC 다음으로 가장 많이 풀린 문제여서 좀 에바인 것 같다.

F. 환승역 찾기 게임

Confuzzle이랑 상당히 유사한 문제다. 풀이가 너무 뻔해서, 이게 맞나? 이게 맞나?? 하고 더 좋은 풀이를 오래 고민하다가 안 떠올라서 그냥 무지성으로 복붙하고 맞았다.

살짝 Colorful Tree 느낌도 나는데, 저게 쓸 수 있는 웰논 풀이가 훨씬 제한되기도 하고 구현도 어려운 것 같다. 그래서 저기서 두 티어 낮춘 플2로 매겼다.

---

D는... 대회 중엔 못 푼 게 아쉬웠는데, 끝나고 보니 너무 어렵다. 한참 틀리다가 문제를 잘못 읽은 걸 발견했는데, 발견한 뒤에도 무한 맞왜틀의 늪에서 빠져나오질 못하겠다. 안 잡길 잘한 듯

대체로 상당히 재밌는 문제들이었다. D만 빼고. F도 너무 웰논이라 살짝 애매한 것 같다. 아무튼 문제 퀄리티는 운영진들의 수준에 걸맞게 꽤 높아서 잘 즐긴 것 같다.

문제를 너무 자주 잘못 읽는 것 같아 슬프다. 구현도 뇌절하는 경우가 많은 느낌이다. 그냥 구현 잘하는 팀원만 믿고 목 아래론 갖다버린 다음 누가 문제 말해주면 풀이만 뱉고 싶다.