Codeforces Round #838

Dashboard - Codeforces Round #838 (Div. 2) - Codeforces

A - Divide and Conquer

합이 짝수라면 답은 0이 된다.

그렇지 않다면 각 인덱스마다 parity가 변하기 위한 최소 연산 횟수를 구하면 된다.

00:02 AC

 

B - Make Array Good

x 제한을 무시하고 풀었다.

x 제한이 없다면 전부 maxv로 만들면 된다.

00:05 WA

 

모든 수를 가장 가까운 2의 제곱으로 만들면 된다.

00:12 AC

 

C - Binary Strings are Fun

순차적으로 보면 된다.

이전 수와 현재 수가 동일하다면 경우의 수는 2배 증가한다.

그렇지 않다면 경우의 수는 1이 된다.

00:26 WA

모듈러 연산을 빼먹었다.

00:27 AC

 

D - GCD Queries

0의 후보인 3개의 수 x, y, z에 대하여 3번의 query를 날리자.

그리고 결과로 얻은 gcd 값을 각각 gxy, gxz, gyz라고 하자.

다음과 같이 x, y, z 중 일부를 0의 후보에서 제거할 수 있다.

• gxy == gxz or gcd(gxy, gxz) != gyz이면 x는 0이 될 수 없다.
• gxy == gyz or gcd(gxy, gyz) != gxz이면 y는 0이 될 수 없다.
• gxz == gyz or gcd(gxz, gyz) != gxy이면 z는 0이 될 수 없다.

3번의 query로 최소 1개 최대 3개의 수를 0의 후보에서 제거할 수 있다.

최악의 경우 3번의 query로 1개의 수를 제거하므로 최대 query 횟수는 대략 3N번이다.

randomization을 적용하고 기도하였다.

00:52 WA

 

위의 방법을 4개의 수 x, y, z, w에 대하여 6번의 query를 날리도록 변형하였다.

이렇게 하면 6번의 query로 최소 2개 최대 4개의 수를 0의 후보에서 제거할 수 있다.

최악의 경우 6번의 query로 2개의 수를 제거하므로 최대 query 횟수는 마찬가지로 대략 3N번이다.

randomization을 적용하고 기도하였다.

01:12 WA

 

처음 풀이에서 x와 y를 고정하면 일부 query 결과를 재사용할 수 있다.

우선 1번의 query로 gxy를 구하자.

그리고 가능한 모든 z에 대하여 2번의 query로 gxz와 gyz를 구하자.

이때 z가 제거되면 gxy의 값은 유지되며 x 또는 y가 제거되면 gxy의 값은 이전 query의 결과로부터 얻을 수 있다.

gxy는 1번만 구하면 되므로 query 횟수는 2N - 3번이 된다.

01:50 AC

 

정해는 더욱 간결하다.

조건을 다음과 같이 변형할 수 있다.

• gxz < gyz이면 x는 0이 될 수 없다.
• gxz > gyz이면 y는 0이 될 수 없다.
• gxz = gyz이면 z는 0이 될 수 없다.

gxy를 구할 필요가 없어지므로 query 횟수는 2N - 4번이 된다.

 

E - Tree Sum (not solved)

우선 N이 홀수라면 good 트리는 존재하지 않는다.

good 트리의 정점의 개수는 항상 짝수임을 보이면 된다.

good 트리의 각 정점에 대하여 인접한 간선의 가중치의 곱은 -1이어야 한다.

이를 모두 곱한 값은 (-1)^N이다.

 

그런데 각 간선은 두 개의 정점에 영향을 미친다.

따라서 위에서 계산한 값은 모든 간선에 대하여 (간선의 가중치)^2의 곱과 동일하다.

간선의 가중치는 1 또는 -1이므로 결과는 반드시 1이 된다.

(-1)^N = 1이므로 good 트리의 정점의 개수는 항상 짝수이다.

 

N이 짝수인 경우 N^(N - 2)개의 모든 트리에 대하여 good 트리가 되는 가중치 조합은 유일하게 존재한다.

리프 노드부터 루트 노드까지 차례대로 올라가면 각 간선의 가중치는 유일하게 결정됨을 알 수 있다.

그리고 위의 논리와 유사한 방법으로 루트 노드와 인접한 간선의 가중치의 곱은 항상 -1임을 보일 수 있다.

 

이제 N^(N - 2) * (N - 1)개의 간선에 대하여 각 간선이 d(1, N)에 얼마만큼 영향을 미치는지 확인해야 한다.

이를 전부 확인하는 것은 불가능하므로 조합론적으로 접근해야 한다.

각 간선 e에 대하여 e를 제거하면 트리가 분할된다.

이때 왼쪽 분할과 오른쪽 분할을 각각 L과 R이라고 하자.

그리고 L과 R의 크기를 각각 l과 r이라고 하자.

이때 간선 e의 가중치는 (-1)^l = (-1)^r이 됨을 보일 수 있다.

 

간선 e가 d(1, N)에 영향을 미치기 위해서는 1번 정점과 N번 정점이 서로 다른 분할에 속해야 한다.

1번 정점이 L에 속한다고 가정하면 N번 정점은 R에 속해야만 한다.

이때 l과 r은 1 이상 N 미만이며 l이 결정되면 r 또한 결정된다.

따라서 가능한 모든 l에 대하여 1번 정점과 N번 정점을 분할하는 간선의 수를 세면 된다.

 

결론부터 말하자면 경우의 수는 nCr(N - 2, l - 1) * l * r * l^(l - 2) * r^(r - 2)이다.

우선 1번 정점과 N번 정점을 제외한 N - 2개 정점 중 l - 1개의 정점을 선택해야 한다.

1번 정점은 이미 L에 속하므로 l - 1개의 정점만 선택하면 된다.

여기서 nCr(N - 2, l - 1)이 도출된다.

 

그리고 간선 e가 연결하는 정점을 선택해야 한다.

이때 두 정점은 서로 다른 분할에 속해야 하므로 L과 R에서 하나씩 선택하면 된다.

여기서 l * r이 도출된다.

이제 각 분할에 대하여 가능한 트리를 모두 만들어보면 된다.

여기서 l^(l - 2) * r^(r - 2)이 도출된다.

 

간선 e의 가중치는 (-1)^l이므로 정답은 다음과 같이 계산할 수 있다.

for i = 1; i < N; ++i

    ans += (i % 2 ? -1 : 1) * nCr(N - 2, i - 1) * i * (N - i) * i^(i - 2) * (N - i)^(N - i - 2);

모듈러 연산은 적절히 추가해주자.

 

F - Good Pairs (not solved)

정해는 Segment Tree + Fenwick Tree + dp이다.

그리고 나는 Segment Tree with Lazy Propagation으로 풀었다.

 

정해부터 소개하도록 하자.

a_l = a_r이라면 (l, r)은 항상 good pair이다.

그렇지 않다면 a[l .. r]에서 문제의 조건을 만족하는 subsequence가 존재하는지 확인하면 된다.

이때 a_l < a_r이라면 단조 증가하는 subsequence만 고려해도 됨을 보일 수 있다.

마찬가지로 a_l > a_r이라면 단조 감소하는 subsequence만 고려해도 됨을 보일 수 있다.

 

모든 경우를 별도로 처리해주자.

a_l = a_r인 경우는 map으로 빈도수를 세면 된다.

나머지 경우를 처리하기 위하여 다음과 같은 함수를 정의하자.

ll solve(vector<int> &a) { // do something }

이 함수는 a_l < a_r인 good pair의 개수를 리턴한다.

a_l > a_r인 경우를 구하려면 solve(reverse(a))를 호출하면 된다.

 

solve 함수의 구현에 대하여 알아보자.

핵심은 dp이며 이 과정에서 Segment Tree와 Fenwick Tree를 이용한다.

다음과 같은 점화식을 세울 수 있다.

dp[i] = a_i < a_j이면서 (i, j)가 good pair가 되는 j의 개수

 

각 원소는 역순으로 처리해준다.

먼저 이전 원소 중에서 구간 [a_i + 1, a_i + K]에 속하는 원소가 있는지 확인한다.

여러 개 존재한다면 가장 작은 인덱스 j를 선택한다.

if j exists:

    dp[i] = dp[j] + 구간 [a_i + 1, a_j]에 속하는 원소의 수

else:

    dp[i] = 0

 

구간 [a_i + 1, a_i + K]에 속하는 원소 중 가장 작은 인덱스를 찾아야 한다.

이는 Segment Tree로 처리할 수 있다.

그리고 구간 [a_i + 1, a_j]에 속하는 원소의 수를 세야 한다.

이는 Fenwick Tree로 처리할 수 있다.

 

TC가 많으므로 매번 트리를 초기화할 수는 없다.

좌표 압축을 하고 작은 트리를 사용하거나 매번 모든 동작을 초기화해주면 된다.

 

이제 LzSeg 풀이를 살펴보자.

각 인덱스에 대하여 해당 인덱스가 도달할 수 있는 값의 범위를 관리하자.

이때 최솟값과 최댓값을 각각 L과 R이라고 하자.

 

각 원소는 순차적으로 처리해준다.

초기에 L_i = R_i = a_i이다.

업데이트는 다음과 같이 진행된다.

• i < j이고 L_i - K <= a_j < L_i이면 L_i를 a_j로 업데이트한다.
• i < j이고 R_i < a_j <= R_i + K이면 R_i를 a_j로 업데이트한다.

LzSeg를 이용하면 위의 업데이트를 효율적으로 처리할 수 있다.

L과 R을 별도로 관리하기 위하여 2개의 트리를 사용한다.

각 트리의 인덱스 j에서는 L_i 또는 R_i가 j인 i의 개수를 관리해주면 된다.

 

각 인덱스 i마다 (j, i)가 good pair가 되는 j의 개수를 세야 한다.

이는 i - (a_i에 도달할 수 없는 인덱스의 개수)와 동일하다.

정해보다 간단하기는 한데 LzSeg를 사용하기 때문에 속도는 비교적 느리다.

 

G - Unequal Adjacent Elements (not solved)

Pass

 

끝

끝