Codeforces Round 1082 (Div. 2) 후기

2026년 2월 23일~24일에 진행한 Codeforces Round 1082 (Div. 2)에 참가했습니다. 9문제 중 5문제를 해결하여 퍼포먼스 1850을 기록하였고, 레이팅은 61점 증가한 1672가 되었습니다.

[0:04] A. Parkour Design [AC]

$k$회 위로 올라가고 $k$회 아래로 내려가는 것은 $k$회 직진과 다르지 않습니다. 따라서 목표 높이를 먼저 맞춘 뒤 앞으로 이동하는 것이 최적이고, 이 케이스만 고려해 주면 됩니다.

[0:13] B. ABAB Construction [AC]

$n$이 홀수라면 $A$는 반드시 a로 시작해야 합니다. 이 조건을 먼저 검사했다면, $n$을 $1$ 줄이고 $X$의 두 번째 글자부터 확인하는 것으로 모든 $n$을 짝수로 만들 수 있습니다. 이제 $X$를 두 글자씩 끊었을 때, 같은 글자가 2회 반복되는 (물론 ?는 제외) 묶음이 있다면 답은 NO, 그렇지 않다면 답은 YES입니다.

[0:26] C1. Lost Civilization (Easy Version) [AC]

배열을 입력받기 전 스택을 하나 만들어 줍니다. 배열의 원소 $a_i$가 들어오면, 스택이 완전히 비거나 스택의 끝 원소가 $a_i-1$일 때까지 pop합니다. 스택이 비었다면 결과 변수를 $1$ 더해주고, 스택의 상태에 관계없이 $a_i$를 스택에 push합니다.

[1:34] C2. Lost Civilization (Hard Version) [AC]

아이디어를 얻는 데 매우 많은 시간을 쓴 문제였습니다. 먼저 C1의 스택에서 각 원소별로 자신이 들어갈 때 앞에 있었던 (없을 수도 있음) 원소를 자신의 부모로 하면, 배열을 루트가 여러 개인 트리로 볼 수 있습니다. 각 루트를 한 가상 정점의 자식으로 설정하면 서로 다른 트리 간의 정점 깊이 차도 정의할 수 있죠. 트리를 만든 과정에 의해, 인덱스 $i$에 대해 $i-1$의 깊이가 깊어졌다면 인덱스 $i-1$은 형제의 자식, 얕아졌다면 부모, 같다면 형제입니다. 이제 $DP[i]$를 인덱스 $i$로 시작하는 모든 구간의 함숫값 합으로 정의합니다. 초깃값은 $DP[N]=1$입니다. 이제 점화식을 세우면 다음과 같습니다.

• $i$의 깊이가 $i+1$의 깊이보다 얕은 경우: 인덱스 $i$의 자식 중 가장 오른쪽에 있는 것 $x$에 대하여, $DP[x]+x-i$
• 그렇지 않은 경우: $DP[i+1]+N-i+1$

이제 전체 DP 테이블의 합을 구해 주면 답이 됩니다.

[2:14] D. Recollect Numbers [AC]

C2에서 끝낼까 잠시 고민했지만, 레이팅을 확실히 높이기 위해 D를 풀기로 했습니다. 먼저 답이 YES가 되는 $k$의 범위는 $n$ 이상 $2n-1$ 이하라는 발상을 했습니다. $k<n$이거나 $k>2n$인 것은 불가능함이 자명하고, $k=2n$이려면 모든 카드를 뒤집는 데 $n$번의 차례를 쓰고 제거하는 데 다시 $n$번의 차례를 써야 하는데, 반드시 이보다 줄어들기 때문입니다. 다음으로 $k=2n-1$일 때의 답을 만들어 봅니다. 1 2 (3 1) (4 2) (5 3) ... (n-1 n-3) (n n-2) n-1 n 형태가 $k=2n-1$을 만족합니다. $n>\frac{k+1}{2}$일 때는 적절한 $n'$에 대하여 위 답을 적용한 다음, (n'+1 n'+1) (n'+2 n'+2) ... (n n)을 덧붙여 답을 완성하면 됩니다.

결론

이렇게 해서 서브태스크 포함 5솔로 1800대 퍼포먼스를 달성했습니다. 레이팅도 1672로 크게 올라, 다음 라운드에 1700을 노려볼 수 있을 것 같습니다.