[알고리즘] Codeforces Round #772 (Div. 2)

이번에 4솔을 하여 민트로 복구할 수 있었다.

코드포스가 있던날 백준, 앳코더도 함께 진행해서 좀 힘든하루였다.(백준 4시간, 앳코더 1시간, 코드포스 2시간..)

세자리수 진입

A - Min Or Sum [Solved!]

배열 $a$에서 서로 다른 원소 $a_i, a_j$를 뽑아 $a_i|a_j = x|y$를 만족하면서 $a_i = x, a_j = y$인 연산을 반복할 때 가능한 배열의 합의 최솟값을 찾는 문제이다.

 

$x = a_i|a_j, y = 0$으로 두면 위 조건을 만족한다.

이 연산을 반복해서 하나의 원소에 적용하면 결국 배열은 $a_1|a_2| \dots | a_n, 0,0, \dots , 0$모양이 될 것이다.

이 때가 최소가 된다.

 

B - Avoid Local Maximums [Solved!]

배열의 값들이 주어졌을 때 수를 최소한으로 변경하여 길이가 1인 극댓값을 없애는 문제이다.

 

배열을 돌며 극대가 언제인지를 저장한다.

예를들어 배열이 $(1,2,1,2,1)$인경우 $(0,1,0,1,0)$으로 저장한다.

그 후 저장된 배열을 돌면서 $1,0,1$인 부분의 인덱스를 $i-1, i, i+1$이라고 하면 $a_i=max(a_{i+1}, a_{i-1})$로 대체한다.

한번 더 저장된 배열을 돌면서 $1$인 부분의 인덱스를 $i$라고 하면 $a_i=max(a_{i+1}, a_{i-1})$로 대체한다.

이 경우 변경을 최소로 할 수 있고 길이가 1인 극댓값을 없앨 수 있다.

단, $i=1, i=n$인경우 예외처리를 해줘야 한다.

 

C - Differential Sorting [Solved!]

배열에서 세 원소 $a_x,a_y,a_z (x<y<z)$를 뽑아 $a_x=a_y-a_z$로 바꾸는 연산을 여러번 반복하여 배열을 비내림차순(이하 오름차순)으로 만들 수 있는지 구하는 문제이다.

연산 사용 횟수는 최소일 필요는 없다.

 

이미 오름차순이라면 더 연산을 수행할 필요가 없으므로 $0$을 출력한다.

언제나 뒤의 두개의 원소를 이용하여 앞의 원소를 변경하는 것이므로 가장 뒤 2개의 수는 변경될 수 없다.

즉 가장 뒤 2개의 수가 내림차순이라면 답을 구할 수 없으므로 $-1$을 출력한다.

또한 가장 마지막 수가 음수라면 $a_x = a_y-a_z > a_y$가 되므로 이 경우 역시 답을 구할 수 없다.

그리고 인접한 값은 같아도 된다.

그래서 모든 값을 $a_{n-1}-a_n$으로 대체하면 조건을 만족하는 답이 나온다.

연산 횟수가 최소일 필요가 없어서 가능한 정답

 

D - Infinite Set [Solved!]

배열 $a$가 주어지고 다음 조건을 만족하는 수들이 무한집합 $S$에 들어가 있다.

1. $x = a_i$

2. $x = 2y+1$  $(y \in S)$

3. $x = 4y$  $(y \in S)$

이 때 $S$의 원소 중에 $2^p$보다 작은 원소의 개수를 $10^9+7$로 나눈 나머지를 출력하는 문제이다.

 

정해는 잘 모르겠고 오로지 관찰에 의존해 해결한 문제이다. (백준 10350번같이..)

2번조건은 홀수를 만들고 3번조건은 짝수를 만든다.

이 말은 하나의 생성원으로 같은 수를 두 번 만들 수 없다는 것이다.

그리고 배열원소를 생성원으로 하여 다른 배열 원소를 만들 수 있다면 그 배열의 원소를 지운다.

예를들어 배열이 $(5, 20)$이라면 $20$은 $5$를 이용해 생성할 수 있으므로 배열을 $5$로 만든다.

이는 $20$을 역연산하면서 찾을 수 있다. (홀수일 경우 $\frac{y-1}{2}$, 짝수일 경우 $\frac{y}{4}$)

그 후 $5$로 만들 수 있는 모든 수를 전개해 보았다.

${5, 11, 20, 23, 41, 44, 47, 80, 83, 89, 92, 95, \dots}$

그리고 $2$의 제곱수보다 작은 수 단위로 끊어 보았다.

${5,| 11,| 20, 23,| 41, 44, 47,| 80, 83, 89, 92, 95,| \dots}$

놀랍게도 개수가 피보나치 수열을 이룬다.

${1, 1, 2, 3, 5, ...}$

답은 피보나치 수열의 누적합 형태일 것이니 누적합을 구한다.

그리고 생성원을 $x$라 하고 $t$를 $x < 2^t$인 가장 작은 값으로 정의하면 $min(p-t+1,0)$번째 누적합을 구하면 된다.

$t$는 로그를 사용하거나 직접 연산하여 $O(log x)$시간에 구할 수 있다.

 

 

 

조금만 더 열심히 하면 블루에 갈 수 있을 것 같다.

지금같은 페이스로 3솔을 빠르게 해결하는 것으로 충분한 것 같다.

 

Codeforce learn by codeforces.

이건 정말 맞는말이다.

코드포스에 익숙해지니 문제 푸는 방법이 눈에 보이기 시작한다.