codeforces #585 div2 B - The Number of Products (전처리, 구현)

https://codeforces.com/contest/1215/problem/B

B번이지만 신기한 전처리를 사용해서 풀 수 있어서 리뷰

 

<설명>

길이가 n인 0이 아닌 정수의 배열에서, 연속된 부분 수열의 곱이 음수인 것의 개수와 양수인 것의 개수를 출력하는 문제다.

ex) 1 2 -3 4의 경우 6 4을 출력해야 한다.

 

<풀이>

0.

음수인 것의 개수를 cnt_n 이라고 한다면 양수인 것의 개수는 n*(n+1)/2 - cnt_n 이 될 것이다.

 

1.

음수가 나오는 인덱스를 1 base로 벡터에 넣어준다. (그 후 벡터가 비어있으면 cnt_n은 0이다)

마지막으로 계산의 편의를 위해 n+1도 벡터에 넣어준다.

 

예1)

예를들어 n이 4이고 벡터에 3 4가 들어있다면 배열에서의 배치는+ + - +이다.  

 

곱이 음수인 부분수열 a[l..r]을 고르는 경우의 수를 생각해 보면, 인덱스 1,2,3중에 하나를 l로 선택하고 인덱스 3,4중에 하나를 r로 선택하는 경우의 수, 즉, 3*2가 cnt_n이 된다.

 

예2)

예를들어 n이 9이고 벡터에 2 5 7 10이 들어있다면 배열에서의 배치는 + - + + - + - + + + 이다.

 

부분수열에 음수가 홀수개 들어있는 상황을 모두 고려해야 한다. 벡터를 벡터크기-2(마지막에 임의로 n+1을 넣어줬기 떄문)까지 순회하면서 생각해보자.

 

1~2 중 하나를 l로 선택하고 2~4 중 하나를 r로 선택하는 경우의 수를 cnt_n에 더해준다.

 

1~2 중 하나를 l로 선택하고 7~9 중 하나를 r로 선택하는 경우의 수를 cnt_n에 더해준다. (세 음수를 모두 포함하는 경우)

(다음으로 순회.....)

 

위와 같은 논리를 코드로 구현한 건 다음과 같다.

//idx : 벡터, 벡터 맨 처음에 0, 맨 끝에 n+1이 추가된 버전임

ll cnt_n = 0;
for (int i = 1; i < idx.size() - 1; i++) {
	ll prev = idx[i-1], l = idx[i];
	int j = i;
	do {
		ll next = idx[j+1];
		ll r = idx[j];
		cnt_n += (l - prev) * (next - r);

		j += 2;
	} while (j <= idx.size() - 2);
}

하지만 이 코드로 구현한다면 시간 초과가 난다. 음수가 매우 많을 경우 O(n^2)이기 때문.

 

위 예시에서 이렇게 바꿔 생각할 수 있다.

 

1~2 중 하나를 l로 선택하는 경우 * (2~4 중 하나를 r로 선택하는 경우 + 7~9 중 하나를 r로 선택하는 경우)

 

(2~4 중 하나를 r로 선택하는 경우 + 7~9 중 하나를 r로 선택하는 경우) 이부분을 O(1)에 가져올 수 있도록 전처리 해주면 된다.

 

 

 

2.

하지만 위와 같이 전처리를 하려면 머리가 매우 아프다. 벡터를 뒤에서부터 순회하는 것으로 풀이를 바꿔 생각해보자.

 

(1~2 중 하나를 l로 선택하는 경우 + 6~7 중 하나를 ' l '로 선택하는 경우) * 7~9 중 하나를 r로 선택하는 경우

 

이렇게 벡터의 순회를 뒤에서 부터 한다면, 전처리할 부분이 좀 더 직관적? 으로 변한다.

 

벡터에서 인덱스가 홀수번 만큼 떨어진 영역 - 짝수번 만큼 떨어진 영역 꼴이다. 

 

빨간색으로 표시된 부분 * (파란색으로 표시된 부분) 을 벡터를 뒤에서부터 순화하며 모두 처리해주면 된다.

// idx : 벡터, 이건 맨 앞에 0 없음
bool flag = true;
ll pre[MAX] = { 0 };
pre[0] = idx[0];
for (int i = 1; i < idx.size(); i++) {
	pre[i] = (flag ? -idx[i] : idx[i]) + pre[i-1]; //구간 합 비스무레
	flag = !flag;
}

ll cnt_n = 0;
for (int i = idx.size() - 2; i >= 0; i--) 
	cnt_n += (idx[i+1] - idx[i]) * abs(pre[i]);
	

 

윗부분이 전처리 구간이고, 밑부분이 cnt_n을 구하는 구간이다. O(n)에 돌아간다.

 

 

 

 

<생각>

B번치곤 어려웠다. 푸는데 50분 이상 쓴거같다 ㅜㅜ. 

editorial 보면 양수인 경우를 구해서 전체에다 빼던데, 설명이 뭔가 지리멸렬하다.