Codeforces Round 1037 (Div. 3)

분명 대회 종료 당시에는 8문제 중 7솔이었는데.. 자고 일어나니까 F 핵당하고 일과 끝나고 보니 B가 시스페일 뜨면서 등수가 확 떨어졌다.

B만 맞았어도 민트로 올라가는 레이팅인데 너무 아쉬움이 많이 남는 대회다.

A번 — 00:02 AC#

$x$의 각 자릿수 중에 가장 작은 수가 $y$임이 자명하다.

B번 — 00:07 AC → TLE(System testing)#

0이 $k$개 연속되어 있으면 등산 횟수를 올리고 날짜는 다음 다음날부터 다시 시작한다.

..였는데 $n$이랑 $k$ 제한인 $10^5$를 $10^4$로 생각해서 코드가 $O(n \times k)$로 구현돼버렸다. 아니 그냥 반복문 돌려도 될 것을 굳이 짧게 적겠다고..

C번 — 00:28 AC#

$a > b$라고 할 때, 현재 위치로부터 높이가 $a$인 탑을 $a$초 소모해서 가는 것보다, $b$탑을 $b$초 소모해서 텔레포트하고 $a$탑을 $a - b$초 소모해서 텔레포트하는 게 더 이득이다. 즉, 작은 탑부터 올라가는 게 항상 최선이다. 정렬하고 그리디하게 가능한지 여부만 보면 된다. 도착 전 현재 탑 높이보다 시간이 작아야 한다는 걸 유의하자.

E번 — 00:45 WA#

배열 두 개를 헷갈려서 $i$와 $i + 1$을 바꿔 적는 바람에 틀렸다. 찾기가 너무 어려워 10분 정도 버렸다. 그 와중에 공교롭게도 테케1은 통과했다.

E번 — 00:54 AC#

$p[i-1] \bmod p[i] = 0$, $s[i+1] \bmod s[i] = 0$을 만족하는지 확인해야 한다. 오른쪽으로 갈수록 나눠져야 하기 때문. 이후 $p[n] = s[1]$로 전체 GCD가 같은지 확인하는 걸로 구현할 수 있다.

F번 — 01:12 TLE#

아무 생각 없이 색 바뀌는 거만 인접한 노드를 정직하게 처리해줬다.

F번 — 01:16 TLE#

상수 커팅했으나 별 의미는 없었다. 아이디어 안 떠올라서 패스.

D번 — 01:29 AC#

C 풀고 처음 봤을 때 지문 이해가 안 돼서 빠르게 패스했다가 F 모르겠어서 돌아왔다.

코인 수가 늘어나면 방문할 수 있는 카지노도 늘어난다. 현재 코인 수에서 갈 수 있는 카지노 중에 $\operatorname{real}$이 가장 큰 카지노부터 그리디하게 방문하면 되며, 우선순위 큐를 사용하면 된다.

G1번 — 02:05 AC#

$\min$ 후보 $x$에 대해서 $x$보다 작은 수는 제외하고 1부터 배열의 최댓값까지 이분탐색으로 해서 조건 만족하면 배열 최대 쌍을 갱신해줄 수 있다. 여기서 조건을 만족한다는 건 $x$ 나타나는 순간까지 누적합보다 그 구간에서 점수 누적합이 같거나 커진다는 것을 의미한다. 범위가 1~100으로 작기 때문에 그냥 1부터 100까지 고정시켜가며 구하면 된다.

F번 — 02:13 AC → TLE(Hacked)#

말을 들어보니 해시핵 방지 안 하면 죄다 터진다고 한다. 이런 부조리한 게 있을 수가..