Codeforces Round 915 (Div. 2)
Codeforces Round 915 (Div. 2) 에 참가했다.
이번 라운드는 내 안일한 판단때문에 아쉬웠던 라운드였다.
무지성 제출을 하면 안 된다는 걸 배워가는 좋은 기회라고 생각해야겠다.
A - Constructive Problems (00:04)
문제가 $n\times n$ 정사각형일 때를 생각해보면, 답은 $n$임을 쉽게 알 수 있다.
$n\times m$ 격자에서, 우선 $\min(n, m)$ 크기의 정사각형을 모두 build할 수 있다.
남은 직사각형의 크기가 $x \times y$ 라면, $\min(x, y)$ 크기의 정사각형을 또 모두 build할 수 있다.
$\vdots$
이 과정을 반복해서 정답을 구하면 $\max(n, m)$이 된다.
B - Beginner's Zelda (00:07)
하나의 zelda-operation에서 리프 노드 두 개를 선택하면, 리프가 둘 다 사라지거나 하나만 남게 된다.
둘 다 사라지는 경우를 우선으로 greedy하게 리프를 두 개씩 선택하면 하나만 남게 되는 경우가 나온다.
하나만 남게 되는 경우는 선택한 경로 상의 모든 정점이 자식 정점을 가지고 있지 않다는 것이고, 위처럼 greedy하게 선택을 해왔기 때문에 이 경우에서 노드는 단 하나만 남게 된다.
C - Largest Subsequence (00:49)
주어진 문자열 $s$에서 처음에 골라지는 lexicographically largest sequence는 유일하고, cyclic shift를 하더라도 이 원소들 이외의 것은 선택될 수 없다는 것이 핵심이다.
그 sequence를 $t$라고 하자.
$t$는 감소하는 수열이고, cyclic shift를 한 번 하면 $t$의 길이가 $1$씩 줄어든다.
가능한 만큼 cyclic shift를 하면 원래 골랐던 $t$가 정렬되고, 이 때부터는 전체 문자열 또한 고정된다.
그 때의 결과가 단조증가하지 않으면 답은 $-1$이다.
그렇지 않으면, 초기의 $t$가 정렬되기까지의 cyclic shift 횟수가 답이 된다.
여기서 삽질을 너무 많이 했다.
cyclic shift 횟수를 구하는 과정에서 반대로 문자를 뒤집어서 계속 틀렸고, 패널티가 많이 쌓인 것 같다.
D - Cyclic MEX
주어진 순열에서 $0$이 나오는 위치가 수열의 맨 끝이 되도록 수열을 shift하고, 이 수열을 뒤에 하나 더 붙여서 $2N$크기의 새로운 수열 $P$를 만들자. 즉, $P_N = P_{2N} = 0$이다.
이 수열을 가지고, 답을 구하기 위해 필요한 모든 항을 나열해보자. 테스트케이스 3을 예시로 들겠다.
$1\quad4\quad5\quad2\quad3\quad6\quad7\quad0\quad1\quad4\quad5\quad2\quad3\quad6\quad7\quad0$
====================================================
$0\quad0\quad0\quad0\quad0\quad0\quad0\quad8\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot$
$\cdot\quad0\quad0\quad0\quad0\quad0\quad0\quad1\quad8\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot$
$\cdot\quad\cdot\quad0\quad0\quad0\quad0\quad0\quad1\quad4\quad8\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot$
$\cdot\quad\cdot\quad\cdot\quad0\quad0\quad0\quad0\quad1\quad4\quad5\quad8\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot$
$\cdot\quad\cdot\quad\cdot\quad\cdot\quad0\quad0\quad0\quad1\quad2\quad2\quad2\quad8\quad\cdot\quad\cdot\quad\cdot\quad\cdot$
$\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad0\quad0\quad1\quad2\quad2\quad2\quad3\quad8\quad\cdot\quad\cdot\quad\cdot$
$\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad0\quad1\quad2\quad2\quad2\quad3\quad6\quad8\quad\cdot\quad\cdot$
$\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad\cdot\quad1\quad2\quad2\quad2\quad3\quad6\quad7\quad8\quad\cdot$
각 행의 모든 원소의 합이 최대가 되는 행을 구하면 된다.
$N$번째 이후의 원소들만 보면, mex의 값이 증가수열을 이루는 것을 볼 수 있다.
$P_{N+1}$부터 차례대로 탐색하며 수열이 증가하도록 스택으로 관리해주면 위의 합들을 $O(N)$에 구할 수 있다.
C번을 풀고 D를 읽어봤는데 못 풀 것 같아서 도서관에서 짐 싸고 집으로 왔는데, 대회가 끝나고 5분 뒤에 풀었다.
너무 안일한 생각이었다.
E - One-X
괴상한 문제다. 문제만 읽었을 땐 풀 수 있을 것 같았는데 $N$ 제한을 보자마자 포기하고 도망쳤다.
F - Field Should Not Be Empty
???
Rating
-29
1720 $\rightarrow$ 1691
처음으로 점수가 떨어졌다. 집 안가고 D를 풀거나 패널티만 안 쌓였어도 안 떨어졌을텐데..다음부터 이런 실수 하지 않도록 더 집중해서 해야겠다.