Codeforces Round 1040 (Div. 2)

D가 진짜 어려웠다.. 전형적인 코드포스 애드 혹의 극치가 아닐까 생각한다.

A B C 실수 없이 빨리 풀어서 D를 1시간 동안 고민하면서 풀 수 있었고, E도 이해는 쉬워서 인터랙티브 문제였지만 결국 E1까지 맞출 수 있었다. 인생 최고 등수라서 기분이 좋다. 블루를 찍었다! 야호!

A — 00:03 AC#

당연히 $\operatorname{sum}$이 최대인 것 같지만, $\operatorname{sum}$에 영향을 주지 않는 0을 $\operatorname{mex}$에 넣으면 1이 나오게 된다.

$S$의 모든 0을 1로 바꾸고 $S$의 합을 구하면 최대 점수가 된다.

B — 00:12 AC#

어찌 되었든 배열에서 1부터 $n$까지 가야 하기 때문에 최소 $\operatorname{sum}(a)$만큼의 비용이 든다. 따라서 비용이 $\operatorname{sum}(a)$보다 작으면 불가능하다.

중간에 직선으로 가다 왔다리 갔다리 하는 건, 배열에서 연속된 두 수의 합들로 표현될 수 있다.

예를 들어 $1\ 2\ 3\ 4\ 3\ 4\ 5$로 $3 \leftrightarrow 4$를 한 번 좌우로 움직이고 5까지 갔다고 하자. 이는 $1\ 2\ 3\ 4\ 5$ 직선일 때 비용 $\operatorname{sum}(a)$에 index $3, 4$를 더해준 것과 비용이 같다.

그리고 더 큰 폭으로 좌우로 움직여도 이는 똑같다. $1\ 2\ 3\ 2\ 1\ 2\ 3\ 4\ 5$로 $1 \leftrightarrow 3$을 한 번 좌우로 움직이고 5까지 갔다고 하면, $1\ 2\ 3\ 4\ 5$ 직선일 때 비용 $\operatorname{sum}(a)$에 index $1, 2$와 index $2, 3$을 다 더해준 것과 비용이 같다. 결국 $\operatorname{sum}(a)$에 인접한 두 수들의 합들을 잘 더해서 $s$에 도달하는 게 가능한지 보면 된다.

$a$의 원소가 0부터 2까지밖에 없기 때문에, 인접합으로 가능한 건 0, 1, 2, 3, 4이다. 우리는 배열을 재구성할 수 있기 때문에, 특정 인접합이 나오지 않게 해서 $s$에 도달하는 게 불가능하게 할 수 있다.

예를 들어 $0, 0, 0, \ldots, 2, 2, 2, \ldots, 1, 1$로 배열을 재구성하면, 0과 1의 합으로만 나타나는 인접합 1을 만드는 게 불가능하다. 따라서 $\operatorname{sum}(a) + 1 = s$인 경우에 불가능하게 만들 수 있다.

사실 그렇지 않으면 안 된다. $\operatorname{sum}(a) + h = s$에서, 인접합 1을 만들 수 있으면 그 인접합을 $h$번 더해서 $s$를 만들 수 있기 때문이다.

인접합 1을 만들지 않으려면 0과 1을 분리해야 하기 때문에.. 사실상 나머지 0, 2, 3, 4는 막을 수 없다. $h$가 2 이상이면 2, 3, 4의 합으로 표현될 수 있음이 자명하기 때문에 결론적으로 $\operatorname{sum}(a) > s$이거나, $\operatorname{sum}(a) + 1 = s$라면 불가능하게 할 수 있고, 나머지는 막을 수 없다.

C — 00:27 AC#

선택한 부분집합 $S'$에 사이클이 있다고 하자. 사이클을 이루는 간선 하나를 제거해도 $f(S')$는 변하지 않지만 $g(S')$은 커진다. 즉, $S'$에 사이클을 포함하지 않아야 한다. 최소 스패닝 트리를 만드는 방식에서 착안해서, 최대 스패닝 트리? 를 만드는 느낌으로 하면 된다. 간선 가중치 순으로 정렬해서 큰 거부터 사이클 안 만들게 골라주는 느낌.

D — 01:19 AC#

$2n - p[i]$로 반전시키는 것의 의미를 찾는 게 진짜 어렵다.

1. $i$번째 원소에 대해 할 수 있는 선택지는 $p[i]$를 유지하거나 $2n - p[i]$로 바꾸는 것이다.

$p[i]$를 유지하면, $i < j \le n$이고 $p[i] < p[j]$인 $(i, j)$ 쌍을 inversion pair로 안 만들고 놔둘 수 있다.

그와 동시에, $1 \le h < i$이고 $p[h] > p[i]$인 $(h, i)$ 쌍을 inversion pair로 만든다.

$2n - p[i]$로 바꾸면, $i < j \le n$이고 $p[i] < p[j]$인 $(i, j)$ 쌍들에서 $2n - p[i] > p[j]$가 되어 inversion pair로 만든다.

그와 동시에, $1 \le h < i$이고 $p[h] > p[i]$인 $(h, i)$ 쌍들에서 $p[h] < 2n - p[i]$가 되어 inversion pair인 쌍들을 아닌 걸로 바꾼다.

2. $i$번째 원소에 대해 $p[i]$ 또는 $2n - p[i]$를 선택하는 건 결과에 독립적으로 영향을 미친다.

일반성을 잃지 않고 $1 \le i < j \le n$이라고 하자. $p[i] < p[j]$라면, $i$ 기준으로 $i < j \le n$이고 $p[i] < p[j]$인 $(i, j)$ 쌍을 만들고, $j$ 기준으로는 $i$가 포함된 쌍을 만들 수 없다. 따라서 각 쌍들은 서로의 범위에 영향을 끼치지 않는다. 즉, 독립적이다.

1번과 2번을 $1 \le i \le n$에 대해 적용시켜서 각각 $i$에 대해 inversion pair의 개수를 최소로 한 것의 합이 답이 될 것이다.

실제로 구현할 때는 뒤죽박죽하게 식 정리를 해서 $p[i]$를 유지했을 때 inversion pair를 만드는 경우들을 계산했다.

$i$에 대해 $r[i]$는 $i < j \le n$이고 $p[i] > p[j]$여서 inversion pair를 만드는 개수

$i$에 대해 $g[i]$는 $1 \le h < i$이고 $p[h] > p[i]$여서 inversion pair를 만드는 개수

이렇게 놓고, $2n - p[i]$로 바꿨을 때 inversion pair의 개수의 변화 $d$를 구해서, $d$가 음수일 경우만 바꾸도록 하면 그 합이 답과 동치이다.

펜윅으로 $r[i]$와 $g[i]$를 구해주면 된다.

E1 — 02:13 WA#

이분탐색 짜는데 $n = 3$인 경우 따로 분기 작성을 안 해서 터졌다. 그거 말고도 아예 홀수 길이 처리에 대한 예외를 안 해준 것도 있다. 인터랙티브라서 테스트하기 너무 빡세요..

E1 — 02:35 AC#

550번이라는 쿼리 제한은 생각보다 널널하다. 단순하게 하나의 쿼리에 하나의 괄호만 판별하면 1000번이 필요하기 때문에, 550이라는 제한은 한 번의 쿼리에 적어도 괄호 2개를 판별해야 한다는 걸 의미한다. 그리고 굳이 E1 E2 E3로 나눠놓은 건.. E1에는 간단한 아이디어를 적용할 수 있지 않을까?

어차피 괄호 선택은 아무거나 할 수 있기 때문에 그냥 연속된 괄호라고 생각하면, 가능한 경우는 (), )(, )), ((으로 4개가 존재한다.

중요한 건, 이 4개의 쌍에 대해 각기 다른 고정된 결괏값을 내도록 하는 쿼리가 있는지이다.

다른 다양한 것도 있기야 하겠지만... 대회 당시에 찾은 쿼리는

aabbabab)이다. ($a$, $b$는 값을 모르는 괄호 문자)

$ab$가 (), )(, )), ((인 경우일 때 각각 다른 값을 내놓기 때문에, 이걸 통해 구분할 수 있다.

()일 때 (())()())가 쿼리가 되어서 7로 응답한다.

)(일 때 ))(()()()가 쿼리가 되어서 6으로 응답한다.

))일 때 )))))))))가 쿼리가 되어서 0으로 응답한다.

((일 때 (((((((()가 쿼리가 되어서 1로 응답한다.

이렇게 하면, 500번의 쿼리로 모든 문자열을 알아낼 수 있다.

이제 중요한 건, 쿼리에서 )라는 괄호 문자가 쓰인다는 것이다. 이건 항상 고정되어 있어야 7, 6, 0, 1이라는 서로 다른 값이 $a$, $b$에 의해서만 나올 수 있기 때문에, 결론적으로 적어도 )에 해당하는 문자를 한 개는 알아내야 한다는 것이다. 남은 50번의 쿼리만으로.

문제의 조건에 따르면 주어진 괄호 문자열이 모두 같은 문자로만 이루어져 있지는 않다. 즉, 적어도 )가 1개는 존재하고, (도 1개는 존재한다.

전체 문자열을 쿼리로 물어보면, 0 또는 자연수가 나올 것이다. 0이 나온다면, 문자열은 반드시 ))))....(((( 꼴이다. 따라서 1번째 문자가 )임이 자명하다. 그렇지 않다면 () 쌍이 적어도 1개 존재할 것이다. 쿼리에서 모르는 두 괄호 문자 $a$, $b$만 사용해서 질문했을 때, 답에 따라 바로 특정되는 쿼리는 뭐가 있을까? 바로 $ab$로 질문했을 때 답으로 1이 나오는 경우이다. 이 경우 $a$는 무조건 (이고 $b$는 무조건 )이다.

이제 이 두 가지 사실을 이용해서, 전체 문자열에서부터 이분탐색을 할 수 있다. 대회 당시 썼던 아이디어 노트는 다음과 같다.

우선, 질의했을 때 답을 $Q$라고 하자. 주어진 괄호 문자열은 $s$이고. (즉, 우리가 찾아야 하는 게 $s$) $s$의 1번째 문자를 $s[1]$, 2번째 문자를 $s[2]$... 라고 하자. $s$의 길이는 $n$이라고 주어졌다.

1차 목표: 정확히 )인 index 찾기.

만약 길이가 2인 문자열을 질의했는데 $Q = 1$이라면 문자열은 반드시 ()이라는 걸 이용한다.

문자열 $s$의 경우는 크게 2가지가 있다.

1. $Q(s) = 0$이다. 즉, RBS가 $s$ 안에 없다.

   이런 경우, $s$는 반드시 )))....((( 이런 형태여야 한다. 즉, $s[1] = )$이고, $s[n] = ($이다. 그러므로 1차 목표를 달성할 수 있다. 이 경우 1차 목표 달성.

2. $Q(s) > 0$이다. 즉, RBS가 $s$ 안에 있다.

   이런 경우, 이분탐색을 통해 알아낼 수 있다. 현재 문자열의 길이를 $k$라고 하자.

   I. 1부터 $\lfloor k/2 \rfloor$까지를 질의해보자. $Q > 0$이라면, 1부터 $\lfloor k/2 \rfloor$를 새로운 문자열로 잡고 다시 이분탐색을 한다.

   만약 $Q = 0$이라면,

   II. $\lfloor k/2 \rfloor + 1$부터 $k$까지를 질의해보자. $Q > 0$이라면 $\lfloor k/2 \rfloor + 1$부터 $k$를 새로운 문자열로 잡고 다시 이분탐색을 한다.

   만약 $Q = 0$이라면

   분명 $Q(s)$는 0보다 컸는데 둘 다 $Q$가 0이라는 건 두 부분에 의해 RBS가 잘렸다는 뜻. 즉, $\lfloor k/2 \rfloor$와 $\lfloor k/2 \rfloor + 1$로 분리되었다는 것이니,

   $s[\lfloor k/2 \rfloor] = ($이고 $s[\lfloor k/2 \rfloor + 1] = )$이다.

이렇게 이분탐색을 통해서, 문자열의 길이가 2가 될 때까지 반복하면, 그때 $Q$값이 1이 나오면 ()인 게 확정이 되니, 그걸로 (와 )의 index를 특정할 수 있다.

이분탐색이니 $n$이 최대 1000이라서, 최악의 경우에도 50번의 질의 이내로 알아낼 수 있다.

이렇게 얻어진 index에서, (와 ) 문자의 위치를 각각 $a$, $b$라고 하자.

2차 목표: 전체 문자열 $s$ 구하기

이제, 이미 알고 있는 $s[a]$와 $s[b]$를 제외한 나머지 것들을 구해야 한다.

간단하게 이렇게 2개씩 짝지어서 구하면 된다.

어떤 문자인지 모르는 $s[i]$와 $s[j]$에 대해 질의를 다음과 같이 한다.

• 만약 $Q = 7$이라면, $s[i] = ($이고 $s[j] = )$이다.
• $Q = 6$이라면, $s[i] = )$이고 $s[j] = ($이다.
• $Q = 1$이라면, $s[i] = ($이고 $s[j] = ($이다.
• $Q = 0$이라면, $s[i] = )$이고 $s[j] = )$이다.

이렇게 하면 한 번의 질의로, $s[i]$, $s[j]$를 알 수 있으므로 최대 500번의 질문으로 모든 문자열을 알아낼 수 있다.

이렇게 모든 문자열을 알아내고, 합쳐서 !으로 답을 출력하면 된다.

$n = 3$인 경우 특수 로직으로 나눠야 한다.

우선, $n$이 3인 경우에는 각각 $e$, $f$, $g$라고 놓자.

$Q(e, f, g)$를 한다.

만약 $Q(e, f, g)$가 0이라면 $g = ($이고, $e = )$이다. $f$를 알아보기 위해 $Q(f, e)$를 하자. 만약 $Q(f, e)$가 1이라면 $f = ($이고, $Q(f, e)$가 0이라면 $f = )$이다.

만약 $Q(e, f, g)$가 1이라면 $Q(e, f)$를 하자.

1. 만약 $Q(e, f)$가 1이라면 $e = ($이고 $f = )$이다. $g$를 알아보기 위해 $Q(g, f)$를 하자. 만약 $Q(g, f)$가 1이라면 $g = ($이고, 0이라면 $g = )$이다.
2. 만약 $Q(e, f)$가 0이라면 $f = ($이고 $g = )$이다. $e$를 알아보기 위해 $Q(e, g)$를 하자. 만약 $Q(e, g)$가 1이라면 $e = ($이고, 0이라면 $e = )$이다.

이렇게 하면 $n = 3$일 때 정답을 구할 수 있다.

자 이제 다음으로, $k = 3$인 경우. 즉 이분탐색을 하다 길이가 3인 경우를 만났을 때이다.

각각 $e$, $f$, $g$라고 놓자.

$Q(e, f, g)$를 한다.

만약 $Q(e, f, g)$가 0이라면, 이 구간에선 더 이상 할 게 없다. 다음 구간으로 넘긴다. (만약 지금 구간이 1부터 $\lfloor k/2 \rfloor$일 때였다면, $\lfloor k/2 \rfloor + 1$부터 $k$까지 구간으로 넘어가고, 만약 지금 구간이 $\lfloor k/2 \rfloor + 1$부터 $k$까지 구간이었다면, $s[\lfloor k/2 \rfloor] = ($이고 $s[\lfloor k/2 \rfloor + 1] = )$으로 정하고 이분탐색 종료하는 원래 로직을 따르면 된다.)

만약 $Q(e, f, g)$가 1이라면 $Q(e, f)$를 하자.

1. 만약 $Q(e, f)$가 1이라면 $e = ($이고 $f = )$이다. (와 )의 인덱스를 알아냈으니 이분탐색을 종료한다.
2. 만약 $Q(e, f)$가 0이라면 $f = ($이고 $g = )$이다. (와 )의 인덱스를 알아냈으니 이분탐색을 종료한다.