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를 풀거나 패널티만 안 쌓였어도 안 떨어졌을텐데..다음부터 이런 실수 하지 않도록 더 집중해서 해야겠다.