Codeforces Round #779 (Div. 2)

씹덕 + 컨셉 세터가 등장하여 상당히 불안했으나 문제들 자체는 마음에 들었다.

물론 문제들을 매우 빨리 풀었기 때문에 (24분 이후로 0솔) 그런 것일 수도 있다.

대부분의 풀이가 너무 간단하여 증명을 곁들여보도록 노력하자.

 

https://codeforces.com/contest/1658

 

A. Marin and Photoshoot

 

-> 모든 두 남자 사이에는 여자가 두 명 이상 존재하여야 한다.

-> 따라서 00이 있으면 사이에 두 명을, 010이 있으면 사이에 한 명을 추가해주면 된다.

 

B. Marin and Anti-coprime Permutation

 

-> 2를 제외하면 1~n 까지의 수들이 결코 1~n에 한 번 더 곱해진다고 모두 그 수의 배수가 될 수 없다.

-> 심지어 n이 홀수라면, 반드시 홀수인 i * p_i 가 존재한다.

-> 따라서 n은 짝수여야 하며, (n / 2)! * (n / 2)! 이다.

 

C. Shinju and the Lost Permutation

 

-> 1은 반드시 하나 존재하며 (제일 큰게 제일 앞으로) 그 이후로 값은 1 넘게 증가할 수 없다.

-> 위의 조건을 만족하면 permutation을 만들 수 있음을 보이자.

-> c가 증가하는 포인트들마다 위에서부터 큰 숫자들을 부여해주고, 남는 숫자들은 사이에 아무렇게나 끼운다.

 

D1. 388535

 

-> x로 xor연산을 하기 전과 한 후에 개수가 바뀐 비트가 있다면 x는 반드시 그 비트를 포함한다.

-> [l, r] 사이에 켜진 비트의 개수와 꺼진 비트의 개수가 같다면, x는 그 비트를 가지든 말든 상관이 없다.

pf) 특정한 i번째 비트에서 [L, R]에서 켜진 비트와 꺼진 비트가 같다면,

-> 특정한 수 J에 대하여 J ^ (1 << i) 또한 반드시 함께 [L, R]에 존재한다. (L = 0이므로)

-> 이때 이 수들에 (1 << i)에 대해 xor계산을 해도 똑같이 j와 j ^ (1 << i)이기에 x는 i번째 비트와 무관하다.

 

D2. 388535

 

-> 위와 달리 j가 존재한다고 꼭 j ^ (1 << i)가 존재하는 것이 아니다.

-> 하지만 존재하지 않을 수도 있는 j는 오직 L과 R이기 때문에, 이 성질을 이용하여 쉽게 X를 구할 수 있다.

https://codeforces.com/contest/1658/submission/151195406

 

E. Gojou and Matrix Game

 

-> 이 게임에서 이기는 방법부터 생각해내야 한다.

-> 제일 큰 수부터 탐색하여, 자신과 거리가 K 이상인 점들 중에 승리 표시가 있는 점이 없으면, 그 점도 승리점이다.

pf)

1) 만일 어떤 점이 위의 성질을 만족한다면, 상대방은 무조건 나보다 작은 지점에 수를 놓아야한다.

-> 내가 다시 위의 점에 수를 놓는다면, 이 과정이 영원히 반복되어 내가 승리한다.

2) 만일 어떤 점이 위의 성질을 만족하지 않는다면, 상대방은 나보다 큰 승리 지점에 수를 놓을 것이다.

-> 내가 어떤 수를 놓든 간에 상대방은 자신이 놓은 승리 지점에 회귀할 것이므로 내가 패배한다.

 

-> 위의 내용을 판단할 때 2dseg를 생각했다. (MLE) (Tourist는 2dfenwick로 통과)

-> |x - x1| + |y - y1|의 값이 결국  (x + y) - (x1 + y1)이거나 (x - y) - (x1 - y1)이라는 사실로 쉽게 판단 가능

https://codeforces.com/contest/1658/submission/151192479

 

F. Juju and Binary String

 

-> 당연히 m의 길이에 같은 비율의 1이 있을 때 그 1의 개수가 정수가 아니라면 불가능.

-> 일단 정수라고 하자.

-> string에 대해 특정 지점 i 부터 그 이후로 m개의 char에 대한 1의 개수를 a_i라 하자.

-> a_i의 평균이 결국 m개에 필요한 1의 길이이며 a_i의 증감은 그래봤자 1이다.

-> 따라서 반드시 a_i가 필요한 1의 개수와 동일한 i가 있다.

-> 만일 m + i < n이라면 1개의 구간으로 가능하며, 그것이 아니라면 맨 앞과 맨 뒤를 잘라 두 구간으로 가능