Codeforces Round #742 (Div. 2)

역대급 퍼포먼스다. 원래 carrot은 잘라내고 캡쳐해오는데 오늘은 좀 자랑하고 싶어서 다 나오게 찍었다.

 

A. Domino Disaster

입력된 문자열의 각 문자에 따라 출력할 문자가 1대1로 대응된다. U이면 D, L이면 L, R이면 R로 대응해서 출력하면 된다.

 

B. MEXor Mixup

MEX 결과가 a라는 것은, [0, a) 범위의 모든 정수가 이미 수열 내에 존재한다는 뜻이다. 오프라인으로 일단 0~3e5 까지 xor한 결과를 저장해 둔다. a-1까지 xor한 결과를 가지고 b와 비교해볼 수 있다. 만약 $xored[a-1] = b$라면 a가 답이다. $xored[a-1] \ne b$ 라면 $xored[a-1] \oplus b$을 추가하면 b가 나오기 때문에 a+1이 답이다. 그런데 $xored[a-1] \oplus b$가 a와 같을 수 있다. 그렇다면 임의의 x에 대하여 $xored[a-1] \oplus b \oplus x$와 $x$를 수열에 추가하면 된다. 이 때 답은 a+2이다.

 

C. Carrying Conundrum

brute force로 해결될 수도 있을 것 같은데, 그냥 무지성 경우의 수 DP를 사용했다.

$dp[i][bit] = (i\text{번째 자리까지 덧셈을 했을때, 자리올림이 }bit)$으로 정의한다. 자리 올림을 2bit로 들고 다니면서 관리해주고, 1의 자리부터 1e9의 자리까지 처리해주면 된다. 이 때, (0, n), (n, 0)인 순서쌍도 세지므로 dp 결과에 -2를 하면 답이다.

 

E. Non-Decreasing Dilemma

아주 전형적인 세그먼트 트리 문제이다. 흔히 알려진 테크닉인 금광세그를 풀어봤다면 쉽게 풀이를 떠올렸을 것이다.

세그먼트 트리의 노드를 다음과 같은 6개의 원소를 가진 struct로 정의하자.

• ans : 이 구간에서 단조증가하는 subarray의 개수. 즉, 구간쿼리의 답
• sz : 이 구간의 길이
• lval : 이 구간의 왼쪽 끝 원소의 값
• lsz : 이 구간의 왼쪽 끝 원소를 포함하는 subarray의 길이
• rval : 이 구간의 오른쪽 끝 원소의 값
• rsz : 이 구간의 오른쪽 끝 원소를 포함하는 subarray의 길이

일단 트리의 leaf에서는 ans = 1이고, lval = rval, sz = lsz = rsz이다.

두 서브노드 left와 right가 합쳐질 때 위 그림과 같이 두 가지 경우가 존재할 수 있다. 그림에서 초록색 박스는 left 노드, 파란색 박스는 right 노드이다. 노란색은 각 노드가 커버하는 구간에서 subarray이다.

첫 번째로 $left.rval > right.lval$인 경우이다.(빨강색 박스) 이 때, left의 오른쪽 끝 subarray(노란색 r) 과 right의 왼쪽 끝 subarray(노란색 l)은 그대로 나열된다. 따라서, $ret.ans = left.ans + right.ans$이다.

두 번째로 $left.rval \leq right.lval$인 경우이다.(하늘색 박스) 이 때, left의 오른쪽 끝 subarray(노란색 r) 과 right의 왼쪽 끝 subarray(노란색 l)은 merge된다. 즉, 이전에 존재했던 두 subarray를 제외하고, 새로 생긴 subarray(노란색 r+l)을 계산해야 한다. 따라서, $ret.ans = left.ans + right.ans - \frac{left.rsz(left.rsz+1)}{2} - \frac{right.lsz(right.lsz+1)}{2} + \frac{(left.rsz+right.lsz)(left.rsz+right.lsz+1)}{2}$이다.

단, 여기서 주의해야 할 것은, 서브노드 전체가 하나의 subarray로 존재하는 경우에는 ret.lsz 또는 ret.rsz를 다시 계산해야 한다. 예를 들어 위 그림처럼 $left.lsz = left.sz$인 경우, ret.lsz는 left.lsz가 아니라 left.sz + right.lsz이다. 마찬가지로 $right.lsz = right.sz$인 경우, $ret.rsz = left.rsz + right.sz$이다.

이러한 방식으로 두 서브노드를 합칠 수 있다. 세그먼트 트리를 정의했다면 나머지는 각 쿼리에 맞게 트리에 update 또는 query를 하면 된다.