[2020-09-17] Codeforces Round 626 (Div.1)

AB는 빨리 잘 풀었는데 C를 한참 고민하고 못 풀었다. 이제 정확도, 속도는 어느 정도 돌아온 것 같다. 이제 업솔빙으로 못푸는 문제의 컷을 높이는게 필요할 듯. 문제를 다양하게 풀어보자..

A. Unusual Competitions

(는 +1, )는 -1로 두고 값이 음수로 내려가는 시점부터 0이 되는 순간까지 구간의 길이를 모두 더해주면 된다. 이러한 구간은 전부 조정이 필요한데 마지막에 합이 0이 됐으면 잘 조정해서 음수가 아예 나오지 않게 만들어줄 수 있기 때문이다.

B. Present

가장 작은 수에 해당하는 비트부터 순서대로 0,1,2,3..., b로 번호를 붙여보자. 덧셈을 했을 때 어떤 x번 비트의 값에 영향을 줄 수 있는 건 0...x번 비트까지다(즉, x+1번 비트 이후는 필요가 없다).

 

여기서 x번 비트가 1인 경우와 x번 비트가 0인 경우를 나눠서 생각해보자. 어떤 두 수 a, b에 대해 다음 세 가지 경우 중 하나가 만족되는 경우 두 수를 더했을 때 x번 비트의 값은 1이 된다.

1. a의 x번 비트가 1, y의 x번 비트가 1인 경우: a와 b의 0..x-1번 비트까지의 값을 더했을 때 2^x 이상이어야 한다.

2. a의 x번 비트가 0, y의 x번 비트가 1인 경우: a와 b의 0..x-1번 비트까지의 값을 더했을 때 2^x 미만이어야 한다.

3. a의 x번 비트가 0, y의 x번 비트가 0인 경우: a와 b의 0..x-1번 비트까지의 값을 더했을 때 2^x 이상이어야 한다.

 

따라서, x번 비트가 0인 것과 1인 것을 나눈 후 0..x-1번 비트까지의 값만 취한 것을 별개의 두 배열로 관리한다. 이 두 배열을 정렬하고 나면 위에서 적은 0..x-1번 비트까지 값 더했을 때 2^x 이상 / 미만이 되는 쌍의 개수를 이분 탐색을 통해 쉽게 찾을 수 있다. 이렇게 구한 쌍을 통해서 각 비트마다 결과적으로 1이 되는게 홀수개인지 / 짝수개인지를 잘 구분해서 계산해주면 된다. 시간복잡도는 O(NlogNlogX). X = (배열에 나올 수 있는 수 최대)

C. Instant Noodles

대충 이런게 답 아닐까? 생각한게 진짜 답이었다.. 아 이런 건 어케 푸는지 진짜 모르겠어.. 뭔가 그럴듯한 전략을 생각한 다음 증명을 해야하는데 증명을 제대로 하지를 못하다보니 증명 단계에서 막혀서 그 방법이 옳은지 증명을 못하고, 너무 많은 시간을 또 쓸 수는 없다보니 이것저것 고민만 하다 결국 문제를 못 풀게 된다.

 

풀이는 다음과 같다.

 

우선 임의의 정점 v에 대해, "v가 선택되면 u도 선택되고, v가 선택되지 않으면 u도 선택되지 않을 수 밖에 없는" 정점의 집합을 전부 하나로 묶어서 생각하자. 어차피 하나 선택하면 나머지도 다 선택되니 이렇게 하나의 컴포넌트로 묶어서 생각할 수 있다. 이렇게 컴포넌트로 묶은 후 각 컴포넌트의 수 합을 V(c)라고 하자. 모든 c에 대해 V(c)의 gcd를 취한 것이 곧 답이 된다.

 

일단 각 컴포넌트는 독립적으로 선택할 수 있으므로 V(c)의 gcd를 취하는것까지는 합리적이다. 이 다음에는 각각의 컴포넌트들을 선택하거나 / 하지 않거나를 통해 합을 바꿀 수 있는데, 이걸 gcd(a, b, a + b) 꼴이라고 생각하면 gcd(a, a + b) = gcd(a, b)이고 gcd(b, a + b) = gcd(a, b)이므로 이와 비슷한 과정을 거쳐 식을 줄이면 결국은 하나짜리 컴포넌트들 전체에 대한 gcd (gcd(a,b,c,d,e,...)) 꼴로 환원할 수 있다. 그러면 결국 모든 V(c)의 gcd와 값이 같아지므로 이게 곧 정답이 된다. 이 비슷한 생각을 했는데 대회 마지막에 시도라도 해볼걸 그랬다. 확신이 없는 풀이를 아예 시도도 하지 않는게 대회에서의 내 성적을 저조하게 만드는 큰 원인인 것 같다. 좀 안 될 것 같아도 모르겠으면 에라 모르겠다 일단 트라이하자 같은 것도 좀 필요한 듯.