[CodeForces] #905 (Div.3) A~F 업솔빙

안녕하세요 Gliver 입니다.

이번 글은 코드포스 #905 (Div.3) 에 대해 업솔빙하는 글입니다.

 

 

 

 

A. Morning

단순 구현 문제로, 버튼을 누르는 횟수와 이동하는 횟수를 구해서 출력하면 된다.

 

 

 

 

 

B. Chemistry

개인적으로 조금 복잡하게 생각한 문제이다.

 

팰린드롬을 만들 수 있는 경우는 다음 두 가지 상황으로 제한할 수 있다.

• 모든 문자의 개수가 짝수개인 경우
• 하나의 문자의 개수가 홀수개이고, 나머지 모든 문자의 개수가 짝수개인 경우

 

따라서, 문자열을 적절히 제거하여 홀수개인 문자가 1개 이하가 되도록 만들 수 있으면 된다.

이는, 홀수개인 문자의 개수에서 $k$를 뺀 값이 1 이하 이면 된다는 의미이다.

 

 

 

 

 

C. Raspberries

모든 원소의 곱이 $k$로 나누어 떨어지도록 하는 연산의 최소 횟수를 구하는 문제이다.

$k$ 는 2, 3, 4, 5 중에 하나이므로, 문제를 쉽게 해결할 수 있다.

 

$k$가 소수(prime number)인 경우(2, 3, 5)에는 해당 수의 배수를 무조건 만들어야 한다.

$k$가 4인 경우는 2의 배수 2개를 만들거나 4의 배수를 만들면 된다.

 

 

 

 

 

D. In Love

현재 상황에서 겹치지 않는 쌍이 존재하는지를 묻는 문제이다.

 

시작점의 좌표가 끝점의 좌표보다 큰 경우가 존재한다면, 해당 두 쌍은 겹치지 않는다.

따라서, 시작점의 최대값 > 끝점의 최소값 인 경우에는 적어도 하나의 겹치지 않는 쌍이 존재한다.

 

 

 

 

 

E. Look Back

이 문제는 다음과 같은 사실을 만족한다.

• arr[i] > arr[i+1] 인 쌍이 존재한다면 arr[i+1]에 연산을 1회 이상 시행해야 한다.
• 인덱스 i를 기준으로 i 이전의 원소들이 non-decreasing 상태를 만족하면, [1, i] 구간은 연산을 시행할 필요가 없다.

 

위의 사실을 이용하면, 첫 원소부터 시작하여 arr[i] <= arr[i+1] 이 되게끔 arr[i+1]에 최소 연산을 시행해 주면 문제를 해결할 수 있다.

원소에 2를 곱하는 형식으로 구현하면 매우 큰 수가 나오므로 배열의 원소에 2를 곱하는 방식이 아닌 다른 방식의 처리가 필요하다.

 

원소에 2를 곱하는 형식이 아닌 원소에 연산을 한 횟수를 저장하는 형식으로 문제를 해결할 수 있다.

어떤 원소 $a$에 연산을 $p$번 하게 되면 $a \cdot 2^{p}$의 형태로 나타낼 수 있다.

따라서, $a, b, p$가 정해진 상태에서 $a \cdot 2^{p} \leq b \cdot 2^{q}$를 만족하는 $q$의 최소값을 구할 수 있다.

 

 

 

 

 

F. You Are So Beautiful

이 문제는 이해하는 데 시간이 좀 걸렸다.

 

다음의 조건을 만족하는 $[l, r]$ 쌍의 개수를 구하면 되는 문제이다.

• $b = [a_l, \ a_{l+1} \, \ \cdots \ , \ a_{r-1}, \ a_r]$은 기존의 배열 $a$에서 유일한 subsequence(부분 문자열)이어야 한다.
  (여기서 subsequence는 연속일 필요는 없다)

예를 들어, a = [2, 3, 2, 3] 인 경우를 살펴보자.

l=0, r=1 인 경우
b = [2, 3] 이며, [a[0], a[1]]을 제외한 [a[0], a[3]]인 경우도 [2, 3]이 되므로 l=0, r=1인 경우는 조건을 만족하지 않는다.

l=0, r=2인 경우
b = [2, 3, 2] 이며, [a[0], a[1], a[2]]를 제외한 어떠한 subsequence도 [2, 3, 2]가 되지 못하므로 조건을 만족한다.

 

$b = [a_l, \ a_{l+1} \, \ \cdots \ , \ a_{r-1}, \ a_r]$ 가 조건을 만족하는 경우는 아래의 조건을 만족하는 경우다.

• 인덱스 $l$ 이전에 $a_l$과 같은 값이 존재하지 않는다.
• 인덱스 $r$ 이후에 $a_r$과 같은 값이 존재하지 않는다.

따라서, $a_l$은 처음으로 등장한 값이어야 하며, $a_r$은 마지막으로 등장한 값이어야 한다.

등장하는 모든 값에 대해 첫 인덱스와 마지막 인덱스를 매칭시키면 빠르게 모든 쌍을 구할 수 있다.
(누적 합 배열을 만들어 처리하면 $O(n)$에 모든 쌍을 구할 수 있다)