CodeTON Round 3

Dashboard - CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

A - Indirect Sort

a[1]이 1이어야만 한다.

00:03 AC

 

B - Maximum Substring

원본 string 그리고 모든 문자가 동일한 substring만 고려하면 된다.

00:09 AC

 

C - Complementary XOR

우선 a와 b의 모든 문자가 동일하거나 모든 문자가 동일하지 않아야 한다.

모든 i에 대하여 b[i]가 1이라면 구간 [i, i]에 대하여 연산을 수행한다.

모든 연산을 마치면 a와 b의 모든 문자는 각각 0 또는 1이 된다.

a의 모든 문자가 1이라면 구간 [1, N]에 대하여 연산을 수행한다.

b의 모든 문자가 1이라면 구간 [1, 1], [2, N], [1, N]에 대하여 연산을 수행한다.

00:34 AC

 

D - Count GCD

우선 i > 1인 모든 i에 대하여 a[i - 1]는 a[i]로 나누어떨어져야 한다.

a[i]가 a[i - 1]보다 작아지는 경우가 핵심인데 포함-배제의 원리로 잘 처리해주면 된다.

01:11 AC

 

E - Bracket Cost (not solved)

열심히 노력하였지만 적절한 식을 찾을 수 없었다.

그런데 대회 종료 후 에디토리얼을 보니 식이 상당히 단순하였다.

알고 보니 문제를 잘못 읽었다.

 

아무튼 다음과 같은 배열 A를 정의하자.

A[i] = A[i - 1] + (S[i] == '(' ? 1 : -1);

S[i..j]에 대한 비용을 C[i, j]라고 하자.

(i) A[l - 1] = A[r]인 경우

C[l, r] = A[r](= A[l - 1]) - min(A[l - 1], A[l], ..., A[r])

(ii) A[l - 1] < A[r]인 경우

C[l, r] = (A[r] - A[l - 1]) + (A[l - 1] - min(A[l - 1], A[l], ..., A[r]) = A[r] - min(A[l - 1], A[l], ..., A[r])

(iii) A[l - 1] > A[r]인 경우

C[l, r] = (A[l - 1] - A[r]) + (A[r] - min(A[l - 1], A[l], ..., A[r]) = A[l - 1] - min(A[l - 1], A[l], ..., A[r])

일반화하면 C[l, r] = max(A[l - 1], A[r]) - min(A[l - 1], A[l], ..., A[r])

 

이제 S의 모든 substring S[i..j]에 대하여 C[i, j]의 합을 계산해주면 된다.

max 항과 min 항을 나누어서 계산하자.

max 항의 합은 A를 정렬하면 쉽게 구할 수 있다.

 

min 항의 합은 Segment Tree를 이용하여 구할 수 있다.

prev[x]를 x가 마지막으로 등장한 인덱스라고 하자.

S[i]가 '('라면 이전의 모든 min 값은 변하지 않으므로 구간 [i, i]를 A[i]로 업데이트한다.

S[i]가 ')'라면 prev[A[i]] 이전의 모든 min 값은 변하지 않으므로 구간 [prev[A[i]] + 1, i]를 A[i]로 업데이트한다.

이때 구간 [0, i - 1]의 합이 C[1, i], C[2, i], ..., C[i, i]의 min 항의 합이다.

 

추가적으로 업데이트 과정을 잘 살펴보면 Segment Tree가 굳이 필요하지 않음을 알 수 있다.

 

F - Majority (not solved)

Pass

 

G - Doping (not solved)

Pass

 

H - BinaryStringForces (not solved)

Pass

 

끝

끝