Educational Codeforces Round 163 (Rated for Div. 2)

https://codeforces.com/contest/1948

 

E는 깡 construction

F는 그닥 흥미롭지 못함

G가 흥미로운데 못 풀겠다...

 

A. Special Characters

 

어떤 구간 [L, R]까지 같은 character이면 여기서 special한 것은 양 끝의 무조건 2개

따라서 N이 짝수일 때만 가능하며, AABBCC...의 방식으로 만들면 된다.

지금 생각해보니 N <= 50까지 걸려있어서 Z를 넘는 걸 고려할 필요도 없다.

 

B. Array Fix

 

뒤에 있는 숫자는 당연히 클수록 이득이다.

따라서 뒤에서부터 쪼갤지 말지를 결정해주면 된다. (당연히 뒤 원소가 자신 이하면 쪼개면 된다.)

이렇게 쪼갰을 때 이 배열이 조건을 만족하는지 확인해주면 된다.

 

C. Arrow Path

 

BFS로 갈 수 있는 모든 위치를 체크해주면 된다.

여러 수정사항이 있는 것 같고 좀 번잡한데, 풀이 자체는 명료하다고 생각한다.

 

D. Tandem Repeats?

 

[L, L + 2k)가 tandem repeat이 되려면, [L, L + k)의 모든 x에 대해서 s[x] = s[x + k]가 가능해야 한다.

i = 1부터 |S| - k까지 순회하면서, 가장 마지막으로 s[x] = s[x + k]가 성립할 수 없었던 j( < i)를 저장하자.

그러면 i - j > k가 성립한다면, [i - k + 1, i + k + 1)까지가 tandem repeat이 된다는 뜻이다.

따라서 모든 k에 대해서 위의 과정을 해주면 O(|S|^2)으로 모든 tandem repeat을 찾을 수 있고, 답도 얻을 수 있다.

 

E. Clique Partition

 

claim) 조건 K를 만족하는 최대 크기의 clique는 K이다.

pf) K + 1개의 원소가 있다면, 가장 작은 원소와 가장 큰 원소가 조건을 만족할 수 없다.

     또한 다음의 방식으로 크기가 정확히 K인 clique를 설계할 수 있다. 

     -> K / 2, K / 2 - 1, ... 1, K, K - 1, ... K / 2 + 1 

     -> 예를 들어 K = 8이면 (4, 3, 2, 1, 8, 7, 6, 5), K = 9라면 (4, 3, 2, 1, 9, 8, 7, 6, 5)로 가능하다

 

따라서 (N - 1) / K + 1개의 clique를 설계해주면 된다.

앞에서부터 K개씩 묶어가면서 위에서 설명한 방식대로 a 값을 부여하여 조건을 만족하도록 할 수 있다.

 

F. Rare Coins

 

구간 내의 금과 은을 g1, s1, 구간 밖의 금과 은을 g2, s2라 하자.  (이 값은 누적합을 이용하여 구할 수 있다.)

그러면 (s1개를 통한 값) > (s2개를 통한 값) + g2 - g1 이 성립한다.

편의상 g2 - g1 = k라고 하면 위의 식은 (s1개를 통한 값) > (s2개를 통한 값) + k가 된다.

 

(답) * 2^(s1 + s2)의 값은 다음과 같다

-> \(ans(s1, s2, k) =\sum_{i=0}^{s1}\sum_{j=0}^{s2}{C(s1, i)* C(s2, j)*(i>j+k)}\)

위 식을 통해 다음 사실을 알아낼 수 있다.

-> \(ans(s1, s2, k - 1) - ans(s1, s2, k) = \sum_{i=0}^{s1}\sum_{j=0}^{s2}{C(s1, i)* C(s2, j)*(i=j+k)}\)

저 값은 꽤나 익숙한데, 조금 식변형을 가하면

-> \(\sum_{i=0}^{s1}{C(s1, i)*C(s2, i-k)} =\sum_{i=0}^{s1}{C(s1, s1-i)*C(s2, i-k)=C(s1+s2, s1-k)}\)

 

위의 값을 통해서 다음 사실을 알아낼 수 있다.

\(ans(s1, s2, k) = ans(s1, s2, k + 1)+C(s1+s2, s1-k-1)=...=\sum_{i=0}^{s1-k-1}{C(s1 + s2, i)}\)

이때 s1 + s2는 총 은의 개수와 동일하므로 항상 일정한 값이다.

따라서 모든 \(\sum_{i=0}^{x}C(s1 +s2, i)\)를 미리 계산해두면, 이 값을 통해서 답을 구할 수 있다.

 

사실 결론을 알고 또 보면 애초에 다르게 생각할 수 있다.

(s1개를 통한 값) > (s2개를 통한 값) + k가 성립하므로

s1 - (s1개를 통한 값) > (s2개를 통한 값) + k이고, s1 - k > (s1 + s2개를 통한 값)이 된다.

 

G. MST with Matching

 

일단 3가지를 의심하고 있었다.

-> N = 20 정도이니 비트마스킹?

-> MCMF를 통한 그래프 설계?

-> MST의 활용 버전이니 MST와 마찬가지로 일종의 그리디?

MCMF는 아무래도 아닌거 같아서 기각했다.

 

처음 비트마스킹을 생각했던 형태는 다음과 같다.

예를 들어 원래 있던 그래프에서 점을 하나씩 떼어낸다고 생각해보자.

매번 leaf가 되는 점을 떼어낸다고 생각하면, 이미 이 점이 matching이 되지 않았다면, matching을 시키면서 뗄 수 있다.

따라서 (이미 떼어짐), (떼어지지 않았고 matching이 이미 됨), (떼어지지 않았고 matching 안 됨)으로 만들 수 있다.

근데 이러면 상태 수가 무려 3^N가지나 되고, MST의 그리디적인 특징도 사용할 수 없다.

 

그러면 적당히 2색 색칠을 한다고 생각하면 어떻게 될까?

예를 들어서 비트마스킹을 했을 때 무조건 0인 자리와 1인 자리만 연결되도록 하는 것이다.

이러면 maximum matching의 횟수가 min((0의 개수), (1의 개수))로 제한되긴 하지만, 고정되지는 않는다.

-> 반례로는 1 - 2, 3 - 1, 4 - 1, 5 -2, 6 - 2와 같은 형태의 그래프가 있다.

그렇기 때문에 MST를 어떻게 만드느냐에 따라 matching 횟수가 달라지고, 답을 계산하기 어렵다.

 

그러면 이제 비트마스킹이 정해지면 maximum matching의 횟수가 무조건 정해져야 함을 느낄 수 있다.

Matching이 되는 애들을 미리 정한다고 가정하자.

그러면 이론적으로는 matching의 횟수는 (matching이 되는 개수) / 2이므로 고정된다.

MST를 만들 때 matching이 되지 않는 애들끼리는 연결 시킬 수 없다.

-> 만일 matching되지 않는 애들끼리 연결된다면, 이 둘을 그냥 matching 시켜버릴 수 있으므로 모순

하지만 여전히 이게 maximum matching인지는 알 수 없다.

-> 반례로는 1 - 2 - 3 - 4에 대해 2, 3이 masking되어 있더라도 실제로는 2개의 matching이 가능하다.

-> 생각해본 또 다른 조건이 a - b가 어떤 matching이라면 a, b에 동시에 unmatched가 붙을 수 없다

-> 다만 이러면 그리디하게 MST를 만들 수 없고, 동시에 여전히 maximum을 보장할 수 없다.

 

흠... 그래서 풀이를 열어보니...

쾨니그의 정리로 인해서 maximum matching은 minimum vertex cover와 동일하다.

그렇기 때문에 vertex cover가 될 애들을 비트마스킹을 해주면 된다.

이들이 실제로 minimum일 필요는 없다. 어차피 그러면 더 작은 숫자에서 될 것이기에.

아무튼 이런 식으로 매칭의 횟수가 정해지고, 쉽게 MST를 만들 수 있다.