AtCoder Regular Contest #137

망했다.

 

왤캐 못하지,,

 

AtCoder Regular Contest 137 - AtCoder

 

 

A. Coprime Pair

 

A - Coprime Pair

 

\( 1 \leq L < R \leq 10^{18} \)을 만족하는 \( L \)과 \( R \)이 주어졌을 때, \( L \leq x < y \leq R \)을 만족하고 gcd(\( x \), \( y \)) = 1 인 \( x \), \( y \) 중 \( y - x \)의 최댓값을 구하시오.

 

 

\( x \)는 \( L \)부터, \( y \)는 \( R \)부터 시작하여 주어진 조건을 만족하며 gap이 최소가 되는 \( x \), \( y \)를 구하면 된다.

 

그냥 이렇게 풀면 되겠지 하면서 풀었는데 editorial을 보니 이런 증명을 미리 본 게 아닌 이상 현실적으로 contest 중에 증명해서 푸는 건 거의 불가능할 듯.

 

 

 

B. Count 1's

 

B - Count 1's

 

0과 1로 이루어진 \( N \) 사이즈의 sequence가 있다.

 

contiguous subsequence를 골라 원소들을 flip 할 수 있다. (0 -> 1, 1 -> 0, 안 해도 됨)

 

이러한 operation을 최대 한 번할 수 있을 때, 1의 개수의 값이 될 수 있는 경우의 수는 무엇인가.

 

 

contiguous subsequence를 골랐을 때, (1의 개수 - 0의 개수)가 최대가 되는 경우와 (0의 개수 - 1의 개수)가 최대가 되는 경우를 찾는다.

 

이때, 각각 subsequence에서의 (1의 개수 - 0의 개수)와 (0의 개수 - 1의 개수)를 \( cnt_{10} \), \( cnt_{01} \)이라 하자.

 

original sequence의 1의 개수를 \( k \)라 했을 때, 1의 개수의 값의 범위는 [\( k - cnt_{10} \), \( k + cnt_{01} \)] 가 된다.

 

따라서 답은 \( cnt_{10} + cnt_{01} \) 이 된다.

 

 

 

C. Distinct Numbers

 

C - Distinct Numbers

 

\( N \) 크기의 sequence \( A \) 가 있으며, 모든 element들은 distinct 하다.

( 0 \( \leq \) \( A_1 \) < \( A_2 \) < ... < \( A_n \) \( \leq \) \( 10^9 \) )

 

Alice와 Bob은 게임을 할 것이다.

 

Alice가 먼저 시작하여 번갈아가면서 turn을 가진다.

 

각자는 자신의 turn에 element 하나를 골라 그보다 작으며 0보다는 같거나 큰, 다른 원소들과 distinct 한 수로 바꾼다.

 

자신의 turn이 돌아왔을 때, 이러한 operation을 하지 못하는 상황이라면 지게 된다.

 

sequence가 주어졌을 때, 누가 이기는지를 구하라.

 

 

먼저, 어떤 element가 \( N \) 보다 작다면, 그 수는 더 이상 바꿀 수 없다는 것은 자명하다.

 

이때, 경우를 나누어보자.

 

 

만약 \( A_{N - 1} + 2 \leq A_N \) 이라면, Alice는 무조건 이긴다.

 

\( A_N \)을 \( A_{N - 1} \)보다 작게 만들었을 때 그 이후 turn을 가지는 사람이 이긴다고 가정하자.

 

그러면 Alice는 \( A_N \)를 \( A_{N - 1} + 1 \)로 바꾸면 이긴다.

(Bob은 \( A_N \)을 \( A_{N - 1} \)보다 작은 수로 바꾸어야 한다. 만약 바꿀 수 있는 수가 없다면 그 자체로 Bob이 지는 상황이다.)

 

반대로 가정한다면, Alice는 \( A_N \)을 \( A_{N - 1} \)보다 작은 수로 바꾸면 된다.

(만약 \( A_{N - 1} \)보다 작은 수 중 바꿀 수 있는 수가 없다면 \( A_N \)을 \( A_{N - 1} + 1 \) 로 바꾼 후 Bob이 바꿀 수 있는 수는 없다.) 

 

 

만약 \( A_N = A_{N - 1} + 1 \) 이라면 어떻게 될까.

 

\( A_N \)을 옮겨 \( A_{N - 2} + 2 \leq A_{N - 1} \)을 만족하도록 만든다면 위의 상황이므로 Alice는 지게 된다.

 

따라서 sequence의 뒷부분 수들이 연속되도록 만드는 결정을 내릴 수밖에 없다.

(지금 안 채워도 어차피 언젠가는 채워야 한다.)

 

결국 sequence의 max값이 1씩 줄어든다고 볼 수 있다.

 

따라서 \( A_N - N + 1 \) 이 홀수라면 Alice가 이기고 짝수라면 Bob이 이긴다.

 

 

 

D. Prefix XORs

 

D - Prefix XORs

 

크기 \( N \)인 sequence가 있다.

 

\( M \)번 다음과 같은 operation을 하려고 한다.

 

모든 \( i \) ( 1 \( \leq \) \( i \) \( \leq \) \( N \) ) 에 대해서, 동시에, \( A_i \)를 \( A_1 \oplus A_2 \oplus ... \oplus A_i \)로 바꾼다.

 

\( k \)번 ( 0 < k \( \leq \) \( M \) ) 의 operation 후 \( A_N \)을 구하시오.

 

 

파스칼 삼각형 형태로 \( A_i \)가 얼마나 \( \oplus \) 되었는지 나타난다.

 

따라서 \( A_N \)에 \( A_i \)는 \( {}_{k - 1}C_{N - i} \) 만큼 xor 된다

 

당연히 홀수면 하나 xor 되고 짝수면 없어질 것이다.

 

이제 저 값을 어떻게 계산하느냐가 문제인데, 그냥 각 factorial을 소인수분해 했을 때의 2의 계수를 전처리해주고

분자 분모의 2의 계수를 비교해서 남는지 안남는지를 계산하면 될 것 같다.

 

editorial에서는 Lucas's theorem에 의해 \( (N - i) \)와 \( k - 1 \)의 binary representation의 1의 위치가 모두 다르면 홀수라고 한다.

 

 

알고보면 쉬울지는 몰라도 이걸 저 시간안에 어떻게 캐치해서 푸는건지...

 

진짜 밥만먹고 문제만 풀었나 싶다.