AtCoder Regular Contest #138

Daiwa Securities Co. Ltd. Programming Contest 2022 Spring（AtCoder Regular Contest 138） - AtCoder

 

 

ARC라 그런지 참 어렵다.

 

 

A. Larger Score

 

A - Larger Score

 

 

\( n \)길이의 sequence \( A \)가 주어진다.

 

\( A \)의 score는 앞에서 \( K \)개만큼의 원소들의 합이라 하자.

 

인접한 두 원소의 위치를 바꾸는 operation이 가능하다.

 

초기에 주어진 \( A \)의 score를 \( s \)라 했을 때, score를 \( s + 1 \) 이상으로 만들기 위한 최소한의 opreation 횟수를 구하여라.

 

불가능하다면 -1.

 

 

결국 \( A_i < A_j \) ( \( 1 \leq i \leq k, k + 1 \leq j \leq n \) ) 을 만족하는 \( i, j \)에 대해 min( \( j - i \) )를 구해주면 된다.

(더 큰 수를 \( k \)개의 term에 넣어준다 <=> 더 작은 수를 \( k \)개의 term에서 제외시킨다)

 

\( k + 1 \)번째부터 \( n \)번째까지의 원소들의 값과 위치를 priority queue에 넣어준다.

 

\( k \)부터 \( 1 \)까지 iteration하며 priority queue에서 원소들을 하나씩 뽑아내며 \( A_i < A_j \)를 만족한다면 \( j - i \)의 최솟값을 계속해서 계산하여 준다.

 

priority queue 대신 sorted array를 사용해도 된다.

 

 

 

B. 01 Generation

 

B - 01 Generation

 

 

빈 sequence \( x \)를 0과 1로만 이루어진 \( n \) 길이의 sequence \( A \)로 만드려고 한다.

 

다음과 같은 opreation을 할 수 있다.

 

1. \( x \)를 flip한다. (0 -> 1, 1 -> 0) 이후 \( x \)의 맨 앞에 0을 붙인다.

 

또는

 

2. \( x \)의 끝에 0을 붙인다.

 

operation을 \( N \)번하여 \( x \)를 \( A \)로 만들 수 있는지 구하여라.

 

 

backtracking을 이용해 \( A \)를 빈 sequence로 만들어보자. 

 

먼저, operation을 반대로 바꿔보자.

 

1. \( A \)가 맨 앞에 0을 가지고 있는 경우 0을 없애고 \( A \)를 flip 시켜준다.

 

또는

 

2. \( A \)가 끝에 0을 가지고 있는 경우 0을 없앤다.

 

A에 operation 2를 할 수 있는 경우 operation 2를 해주고 operation 1을 할 수 있는 경우에는 operation 1을 해준다.

 

\( A \)가 빈 sequence가 되기 전 두 operation 모두 불가능하다면 불가능하다.

 

이러한 greedy 한 방식이 가능한 이유는 operation 1과 2가 모두 가능할 때 2를 해주는 것이 나중에라도 1을 하는 것에 지장을 주지 않기 때문이다.

 

근데 생각해보니 할수있는대로 아무거나 다 해도 괜찮을 것 같다.

 

 

 

C. Rotate and Play Game

 

C - Rotate and Play Game

 

 

\( N \) 개의 카드가 1부터 \( N \)까지 indexing 되어 있다.

 

\( i \) 번째 카드는 \( A_i \)라는 수가 적혀있다.

 

\( N \)은 짝수이다.

 

Snuke와 Mr. Min은 돌아가며 자신의 turn을 가진다. Snuke가 먼저 turn을 가진다.

 

Snuke는 자신의 turn에 아무 카드나 한 장 가져갈 수 있다.

 

Mr. Min은 자신의 turn에 index가 가장 작은 카드 한 장을 가져갈 수 있다.

 

\( N / 2 \) 개의 카드를 각자 가져간 후, 각자의 점수는 가져간 카드들에 적힌 수의 합이 된다.

 

당신은 Snuke의 광팬이라 Snuke의 점수를 최대로 만들고 싶어 한다.

 

다음과 같은 operation을 한 번 할 수 있다.

 

- \( k \) ( \( 0 \leq k \leq N - 1 \) )를 선택한다. 그리고 \( k \)만큼 카드를 왼쪽으로 shifting 할 수 있다.

( 카드 1, 2, ... , N는 수 \(  A_{k + 1}, A_{k + 2}, ..., A_N, A_1, ..., A_k \)를 가진다. )

 

Snuke의 점수를 최대로 만드는 \( k \)를 찾으시오.

 

 

\( N \) 개의 수 중 가장 큰 수 \( N / 2 \) 개를 Snuke가 선택하도록 만들면 된다.

 

array를 하나 만들어 큰 수 \( N / 2 \) 개중 하나의 자리일때는 -1을, 작은 수 \( N / 2 \)개중 하나의 자리일 때에는 1을 넣어준다.

 

그런 다음 누적합을 계산해준다.

 

\( k \) 번 shifting 했을 때 Snuke가 큰 수 \( N / 2 \) 개를 선택 가능한 조건은 \( k \)만큼 shifting 한 시작점에서의 모든 누적 값이 0과 같거나 커야 한다.

 

그렇기 때문에 누적합 배열에서 가장 작은 값의 위치를 찾는다.

( \( N / 2 \) 개의 큰 수가 \( N / 2 \)개의 작은 수보다 가장 많을 때이다.)

 

그리고 가장 작은 값의 다음번째부터 게임이 진행될 수 있도록 하면 된다.

(큰 수들이 많고 작은 수들이 적은 구간을 뒤로 민다고 생각하면 된다.)

 

 

 

D. Differ by K bits

 

D - Differ by K bits

 

양의 정수 \( N \)과 \( K \)가 주어진다.

 

다음의 조건을 만족하는 0부터 \( 2^N - 1 \)의 수를 가지고 있는 순열 \( P_0, P_1, ..., P_{2^N - 1} \)가 존재하는지를 구하여라.

 

- 모든 \( i \) ( \( 0 \leq i \leq 2^N - 1 \) )에 대해 \( P_i \)와 \( P_{i + 1 \text{ mod } 2^N} \) 이 정확히 이진수 표현으로 \( K \) 개의 bit가 달라야 한다.

 

 

먼저 \( K \)가 짝수일 때는 불가능하다.

 

\( K \) 개의 bit를 계속 바꿨을 때 동일한 parity를 가진 수만 만들어낼 수 있기 때문이다.

 

 

\( K \)가 \( N \) 이상일 때에도 명백히 불가능하다.

 

 

남은 경우들은 solution을 제시함으로써 가능하다는 것을 보일 것이다.

 

먼저, 1인 bit가 \( K \) 개인 \( N \)-bit \( N \) 개를 만든다.

( \( z_1, z_2, ..., z_N \), distinct)

 

그런 다음 \( N \)-bit gray code \( 2^N \) 개를 만든다.

( \(a_0, a_1, ..., a_{2^N - 1} \), adjacent 한 원소들은 한 bit만 다르다 )

( \( i ^ (i >> 1) \) 이런 식으로 구하던데 어떤 원리인지 찾아봐야겠다 )

 

그리고 \( b_i \)를 다음과 같이 정의한다.

 

\( b_i = z_{i1} \oplus z_{i2} \oplus ... \) ( \( i1, i2, ... \)는 \( a_i \)에서 1인 bit의 자리 )

 

이때 인접한 원소들을 비교했을 때 조건을 만족한다.

 

\( b_{i - 1} \oplus b_i = z_k \) ( \( i < 2^N \), bit가 하나만 차이 나므로 )

 

xor 하였을 때 bit가 다른 경우 1이 된다. \( z_k \)의 경우 1의 개수가 \( K \) 개이므로 조건을 만족한다.