대회후기: Educational Codeforces Round 80 (Rated for Div. 2)

밖에 나와있는 관계로 대회를 치지 못할 것 같았지만, 11시 6분에 대회를 뛰자는 Nyso의 연락을 받고 갑자기 필을 받아서 허겁지겁 집으로 향했다. 음주를 꽤나 한 상태였고, 집에 들어와서 컴퓨터를 켰을 때는 이미 13분가량 늦은 상태였지만 지난번에도 조금 늦어 포기한 대회가 매우 아쉬웠던 경험이 있어서 이번에는 핸디캡에도 불구하고 참여하기로 했다.

---

A: Deadline

정수 $n$과 $d$가 정해졌을 때, 부등식 $x+\lceil \frac {d}{x+1} \rceil \leq n$를 만족하는 정수 $x$의 존재성 판별 문제이다. 부등식의 좌변을 ceiling function을 무시하고 미분해 극소가 되는 실수 $x$값을 찾은 후, 그 주변의 정수 2000개를 조사하는 방식으로 해결했다.

19분에 AC

사실 역에서 집으로 걸어오는 시간동안 문제를 읽어보고 이미 해결 방법을 떠올린 상태였다. 구현이 더 간단한B를 먼저 제출하느라 이번 대회는A가 오히려 더 늦어졌다.

---

B: Yet Another Meme Problem

두 정수 $A$와 $B$가 주어졌을 때, $1 \leq a \leq A$이고 $1 \leq b \leq B$인 정수 순서쌍 $(a, b)$중에서

a * b + a + b == int(str(a) + str(b))

인 순서쌍의 수를 찾는 문제이다. 식 우변의 concatenation을 $b$의 자릿수에 따라 수식적으로 처리하면 답이 쉽게 보인다. $a$의 값은 상관이 없고, $b$의 값은 숫자 9로만 이루어져야 조건이 만족된다. 구현은 간단하니 생략한다.

15분에 AC

역시 집으로 걸어오는 시간동안에 미리 풀어놓았었다.

---

C: Two Arrays

각각 길이 $m$의 증가하는 수열과 감소하는 수열(정확히는 감소하지 않는 수열과 증가하지 않는 수열)이 있다. 증가하는 수열의 각 항이 감소하는 수열의 각 항보다 작거나 같아야 할 경우, 두 수열을 만들 수 있는 경우의 수를 구해야 한다. 이때 각 수열의 원소는 $n$까지의 자연수이다.

두가지 특성을 파악할 수 있었다. 우선, 증가 수열의 마지막 항은 감소 배열의 마지막 항보다 같거나 작아야 한다. 둘째, 각 수열의 숫자 순서는 숫자들을 뽑아놓기만 하면 유일하게 결정된다. Counting 문제는 보통 어떤 기준을 놓고 경우를 나누어 숫자를 세는 경우가 많다. 앞의 두가지 특성을 파악하면 자연스럽게 두 배열의 경계값(i.e. 증가 배열의 마지막 값)을 기준으로 경우를 나누고 싶어진다.

증가 배열의 마지막 값은 경우를 나누면서 정해지므로, 이 숫자를 제외한 두 배열의 모든 수들을 중복조합을 이용해 선택해주면 된다. (처음 구현에서는 증가 배열의 마지막 값을 고정해두지 않아 counting이 잘못되었었다.)

 

특정 소수에 대한 modular값으로 정답을 출력해야 하므로 중복조합 계산 과정을 위해 exponentiation by squaring과 modular division을 구현해놓아야 한다.

27분에 AC

Pypy 구현체의 실행시간이 998 ms로 찍히는 것을 보고 쫄려서 C++로 다시 구현했다. 결국 안터지더라.

UPD) 숫자들만 뽑아주면 두 수열조차도 정해진다. 그냥 중복조합으로 한번에 숫자 $2m$개를 뽑으면 되는거였다...

---

D: Minimax Problem

오늘의 뇌절문제.

 

길이가 짧은(8 이하) 정수 수열 여러개(몇십만개)가 들어온다. 이 중에서 수열 두개를 골라서 출력해야 하는데, 두 수열을 $a$, $b$라고 하면 $\min (\max (a_i, b_i))$ over all values of $i$의 값을 최대화해야한다. 정확히 기억은 안나지만 첫 제출 시간으로 짐작해보면 최소 20분 동안은 풀이법을 떠올리지 못한 것 같다(그래프 형태로 그려보는 등 진전 없는 뻘짓을 좀 했다). 그러다가 수열의 길이가 짧다는 점에 착안한 풀이를 떠올리게 되었다.

특정 목표값 $t$를 설정한다면, 주어진 수열들에서 둘을 골라 그 목표값을 meet할 수 있는지의 판별은 $O(n)$시간에 가능하다:

각 수열들의 항이 $t$값을 넘는지를 기준으로 분류한다면, 수열의 길이 $l$에 대해 모든 수열을 $2^l$가지로 분류할 수 있다. 이렇게 각 항을 $t$ 기준으로 boolean 형태로 변환시킨 수열 중에서 둘을 골라 OR 연산을 취했을 때, 모든 항이 True가 나오는 경우가 있는지 판별해주면 된다.

목표값 $t$는 이진탐색으로 정해주면 된다.

목표값을 먼저 설정하고 살펴본다는 발상 덕분에 떠올린 풀이이다. 하지만 결과는 처참했다...

2 WA 6 TLE

응 파이썬은 느려서 안돼~

50분간의 디버깅과 최적화를 했지만, 그 시간에 C++로 다시 짰어야 한다.

---

총평

한줄평: 파이썬 나빠. (다음 후기에서 이 발언을 취소한다.)

 

핸디캡에도 불과하고 레이팅 방어... 가 아니라 적당한 상승을 했다. 하지만 D가 너무 아쉽다. 앞으로 입력 크기가 커지면 뒤도 안돌아보고 C++로 넘어갈거다. (지난 후기의 발언을 취소한다.)

 

레이팅 변화 1722 + 52 = 1774

My Performance: ★★★☆☆