[Codeforces] Edu Round 145 후기

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

 

 

A. Garland

문제 : 모든 전구를 켜는데 필요한 최소 횟수 출력

 

조건 : 같은 종류의 전구를 이전에 활성/비활성 했을 경우 해당차례에 선택 불가

 

전구가 모두 같은 종류 일 경우 : 불가능(-1)

전구하나만 다른 종류일 경우 : 6 [aaab : b - a - b - a - b - a]

그 외 : 4

aabb : a - b - a - b

abcc : a - c - b - c

abcd : a - b - c - d

 

 

B. Points on Plane

문제 : n개의 물건을 좌표평면에 올렸을 때 원점으로부터 거리들의 최댓값이 최소가 될 때의 최댓값 출력

 

조건 : 임의의 두 물체 맨해튼 거리는 항상 2 이상이어야 한다. (유클리디안 X)

 

2가지 경우로 나누어 보면 쉽게 풀 수 있다.

거리들의 최댓값을 x라 했을 때

x가 짝수 : (0,0)로 시작 (2x,2y) -> x[0] = 1, x[2] = 9, x[4] = 25 ...

x가 홀수 : (±1,±1)로 시작(±1+2x,±1+2y) -> x[1] = 4, x[3] = 16, x[5] = 36 ...

즉 n이 1개일 때부터 최댓값(x)을 보면

(n,x) = (1,0), (2,1), (3,1), (4,1), (5,2), (6,2), (7,2), (8,2), (9,2), (10,3), (11,3) ...

즉 x = sqrt(n-1) 의 값을 나타낸다.

 

이때 주의 사항은 n의 값이 10^18까지 나올 수 있으므로

(long long)sqrt(n-1)을 할 경우 오차의 발생으로 틀리게 된다.

따라서 안정적인 이분탐색등을 사용하여 계산해 주면 된다.

//long long형 제곱근
long long sqrt(long long n) {
	if (n <= 1) return n;
	long long lo = 0, hi = n;
	while (lo <= hi) {
		long long mid = (lo + hi) / 2;
		if (mid > n / mid)
		{
			hi = mid - 1;
		}
		else {
			lo = mid + 1;
		}
	}
	return hi;
}

 

 

C. Sum on Subarrays

문제 : n개의 원소를 갖는 배열 이 있을 때 k 개의 원소의 합이 양수인 부분 배열을 갖는 배열 출력

 

조건 : 각 원소의 범위는 -1000에서 1000까지 가능하다.

주의사항 : 0은 양수도 음수도 아니다.

 

풀이에 다양한 방법이 있겠지만 다음과 같은 방법을 사용하였다.

우선 n=5, k=7이라고 가정했을 때 5칸의 배열을 다음과 같이 만들어준다.

(-1,-2,-3,-4,-5)

 

첫 번째부터 순회하며 k값이 0보다 클경우에만 수행한다.

k=7 -> 6 = (-1+2,-2,-3,-4,-5) = (1,-2,-3,-4,-5)  = 1개

k=6 -> 5 = (1+3,-2,-3,-4,-5) = (4,-2,-3,-4,-5) = 2개

k=5 -> 4 = (4+4,-2,-3,-4,-5) = (8,-2,-3,-4,-5) = 3개

k=4 -> 3 = (8+5,-2,-3,-4,-5) = (13,-2,-3,-4,-5) = 4개

k=3 -> 2 = (13,-2+3,-3,-4,-5) = (13,1,-3,-4,-5) = 5개

k=2 -> 1 = (13,1+4,-3,-4,-5) = (13,5,-3,-4,-5) = 6개

k=1 -> 0 = (13,5+5,-3,-4,-5) = (13,10,-3,-4,-5) = 7개

 

위와 같은 방법으로 계산할 경우 조건에 맞는 배열을 구 할 수 있다.

 

 

D. Binary String Sorting

문제 : 주어진 이진배열을 조작하여 오름차순을 만들 때의 비용의 최솟값 출력

 

조작 1 : 연속한 두 원소를 1000000000001의 비용으로 치환할 수 있다.

조작 2 : 임의의 원소를 1000000000000의 비용으로 삭제할 수 있다.

 

해당배열을 첫 번째부터 순차적으로 보며 다음과 같이 수행한다.

해당 위치보다 왼쪽에 있는 0은 제거할 필요가 없다.

해당 위치보다 오른쪽에 있는 1은 제거 할 필요가 없다.

즉 제거해야 되는 개수를 구해준다.

 

해당위치가 1인 경우 제거 대상에서 임시로 제외한다.

다음위치가 0인 경우 제거 대상에서 임시로 제외한다.

 

해당위치보다 다음위치가 더 작을 경우 교환을 통해 교체해 준다.

이렇게 차례대로 구한 비용들의 최솟값을 출력한다.

 

 

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