[Codeforces] Round 860 Div.2 후기

대회링크 : https://codeforces.com/contest/1798

 

 

A. Showstopper

문제 : A배열 원소의 최댓값 = A배열의 마지막 원소값, B배열 원소의 최댓값 = B배열의 마지막 원소값 가능판단

 

조건 : A, B의 같은 위치의 원소는 서로 교환이 가능하다.

 

A와 B의 마지막 원소중 큰 값을 p, 작은 값을 q 라고 했을 때

조건에 의해서 그 이전의

같은 위치의 원소중 작은 값은 q보다 작거나 같아야 하고

같은 위치의 원소중 큰 값은 p보다 작거나 같아야 한다.

 

순차적으로 보면서 A, B의 크기를 비교해 교환 후에 마지막 원소보다 큰 값이 있는지 비교한다.

마지막 원소보다 큰 값이 있을 경우에는 문제의 조건을 만족시킬 수 없다.

 

불가능 ex)

A : 1 1 2 2 1 1 2

B : 1 2 1 2 1 2 1

===========

A : 1 1 1 2 1 1 1

B : 1 2 2 2 1 2 2

 

A의 4번째 원소가 마지막원소 보다 크기 때문에 불가능하다.

 

 

B. Three Sevens

문제 : 1일부터 m일까지 매일 열리는 복권의 예상 당첨자 출력

 

조건1 : 복권에 당첨 된 사람은 그 이후에 다시 복권을 구매하지 않는다.

조건2 : 매일 하루에 한명씩 복권을 구매한 사람중 한명은 당첨된다.

 

해당일자에 구매한 사람의 목록을 저장 해 둔다.

마지막 날 부터 거꾸로 돌아오며 다음과 같이 수행한다.

 

조건1에 의하여 당첨 하였을 경우 복권을 재구매 하지 않기 때문에

set을 이용하여 당첨후보로 선택했는지의 여부를 기록해둔다.

 

m일의 구매자를 순회하며 구매한 기록이 없을 경우 set에 넣고 후보에 등록한다.

(m 일의 경우 그 이후에 구매한 사람이 없으므로 무조건 후보에 등록된다)

 

m-1일의 구매자를 순회하며 set에 없을 경우 set에 넣고 후보로 등록한다.

m-2일의 구매자를 순회하며 set에 없을 경우 set에 넣고 후보로 등록한다.

...

2일의 구매자를 순회하며 set에 없을 경우 set에 넣고 후보로 등록한다.

1일의 구매자를 순회하며 set에 없을 경우 set에 넣고 후보로 등록한다.

 

위의 과정을 통해 예상되는 당첨자를 추려낼 수 있다.

 

C. Candy Store

문제 : 물품을 진열장에 올렸을 때 필요한 가격표의 개수

 

물품의 낱개 가격과 개수를 주어준다.

 

조건1 : 물품의 개수를 n으로 묶을 수 있을 경우 묶음으로 판매 할 수 있다.

조건2 : 그 이전과 같은 가격의 상품일 경우 가격표가 추가적으로 필요하지 않다.

 

물품 A의 개수와 가격을 a1, b1이라고 하고

물품 B의 개수와 가격을 a2, b2 라고 하고

물품 A, B의 물품 총가격을 s1 = a1*b1, s2 = a2*b2 라고 하면

 

다음과 같은 경우 하나의 가격표로 묶을 수 있다.

GCD(s1, s2) % LCM(b1, b2) = 0

 

묶을 수 있는 경우

GCD = GCD(s1, s2)가 되고

LCM = LCM(b1, b2)가 된다.

 

묶을 수 없는 경우

필요한 가격표가 하나 추가 되고

GCD = s2이 되고

LCM = b2가 된다.

 

이제 물품 C가 있다고 하면 위에서 계산한 GCD, LCM 값을 s1, b1으로 사용하여 계산하면 된다.

 

 

D. Shocking Arrangement

문제 : 주어진 배열의 원소를 재배치 했을 때 부분배열의 절댓값이

원소의 가장큰 값과 작은 값의 차이보다 작을 경우가 있을 때 그러한 배열 출력

 

조건 : 모든 원소의 합은 0 임이 보장된다.

 

모든 원소의 합이 0 이므로 불가능한 경우는

주어진 배열의 원소가 모두 0인 경우 부분배열의 값(0) 이 모두 차이(0) 과 같으므로 불가능 하다.

 

그 외의 상황에선 항상 만족하는 배열을 만들 수 있다.

누적합을 이용하며 시작은 0으로 한다.

 

누적합의 값이 0이상인 경우에는 음수의 원소를 하나 더해준다. 없을 경우 남아있는 0을 출력해준다.

누적합의 값이 0미만인 경우에는 양수의 원소를 하나 더해준다. 없을 경우 남아있는 0을 출력해준다.

 

이 때 누적합은 항상 (최댓값-최솟값)의 차이 이내에 존재하게 된다.

 

 

E,F. 아직 실력 부족으로 접근하지 못하였다.