Codeforces Round 900 (Div. 3)

khj20006 2023. 10. 29. 15:00

생애 두 번째 코드포스 대회이다. 첫 번째는 글을 쓰기엔 몇 달 지나기도 했고, 너무 말아먹어서 pass

CP가 다 그렇듯, 알고리즘 분류와 난이도를 볼 수 없고 영어로 되어있어서 실력 향상에 많이 도움이 될 것 같아서 시작했다. 열심히 해서 힘이 닿는 데까지 점수를 올려보려 한다.

00:04 AC

$k$가 등장했다면, 그 자체로 $k$가 most common element인 subsegment가 될 수 있다.

00:23 AC

$a_1 = 2, a_2 = 3$으로 놓고 $i>2$인 $i$에 대해 $a_i$를 $a_{i-1}$보다 크면서 $3(p-a_{i-1}) \mod (a_{i-2} + a_{i-1}) \neq 0$인 가장 작은 소수 $p$에 대해 $p-a_{i-1}$로 정의하면 된다.

00:29 AC

$x$가 $[ \frac{k(k+1)}{2}, \frac{n(n+1)}{2} - \frac{(n-k)(n-k+1)}{2} ]$에 존재하면 YES이다.

00:45 TLE 00:48 TLE 00:53 AC

$l$이 고정되어있다면, AND 연산의 성질에 의해 $r$이 증가할수록 $f(l, r)$은 단조감소한다.

$f(l, r)$의 값은 세그먼트 트리로 쉽게 구할 수 있다.

따라서 $l \le r \le n$에서 $f(l, r)$을 $O(\log{n})$만에 찾을 수 있고, 이분 탐색으로 $r$을 구할 수 있으므로 쿼리 하나를 $O(\log^2{n})$에 처리할 수 있다.

테스트 케이스가 여러 개 주어지는데 그 때마다 최대 크기로 배열 갱신을 해버려서 TLE를 받았다.

01:30 TLE 01:35 WA 01:37 TLE 01:52 TLE 01:55 WA 01:59 WA 02:00 AC

문제 조건에 의해 $[l_1, r_1], [l_2, r_2], \cdots$는 모두 겹치지 않고, 합집합이 $[1, n]$이 된다.

쿼리마다 이분 탐색으로 $l$에서의 인덱스 $i$를 구해서 reverse의 시작 위치와 끝 위치인 $x, r_i + l_i - x$를 구한다.

모두 저장해놓고, 마지막에 $O(n)$에 구간 별로 prefix sum으로 reverse 연산을 한번에 처리해주자. prefix sum이 홀수이면 구간 내에서 해당 인덱스에 대칭되는 것과 swap해주고, 아니면 건너뛴다.

???

이건 뭔가 hld를 잘 쓰면 될 것처럼 보였는데 시간이 없어 제대로 읽어보지 못해서 잘 모르겠다.

+434

449 $\rightarrow$ 883