-
cf 585div2 B. The Number of Products알고리즘 문제/math 2019. 9. 18. 02:37반응형
You are given a sequencea1,a2,…,ana1,a2,…,anconsisting ofnnnon-zero integers (i.e.ai≠0ai≠0).
You have to calculate two following values:
- the number of pairs of indices(l,r)(l,r)(l≤r)(l≤r)such thatal⋅al+1…ar−1⋅aral⋅al+1…ar−1⋅aris negative;
- the number of pairs of indices(l,r)(l,r)(l≤r)(l≤r)such thatal⋅al+1…ar−1⋅aral⋅al+1…ar−1⋅aris positive;
Print two integers — the number of subsegments with negative product and the number of subsegments with positive product, respectively.
이 문제는 대회당시 풀지 못 했다. Div2 B번에서 꺾이다니 크흑 .. 문제태그엔 구현, 조합론 이 달려있다.
나는 수학적 능력은 정말 떨어지는 듯 ..접근방식은 다음과 같다.
1. 모든 구간의 수는 n*(n+1)이다.
2. 만약 구간 곱이 양수인 임의의 구간들의 집합을 A라 하자.
3. 곱이 음수인 임의의 구간들의 집합을 B라 할 때 의 크기 |B|는 다음과 같다. |B| = n*(n+1) - |A|.이 때, 우리는 |A|의 크기만을 구하는 것을 구현할 수 있다.
|A|의 크기를 구하는 방법은 다음과 같다.
순열 a를 순회하면서, 현재까지 곱이 음수인지 양수인지 체크한다. 만약 음수면 |A| += cnt2 를 하고, 양수이면 |A| += cnt1 을 수행한다.
cnt 는 현재까지의 element 를 더한 것이고, cnt1 과 cnt2는 음수 양수 state에 따라 증가 하고, ansP에 toggle 되어 더해진다.
#include <iostream> using namespace std; int a[(int)2e5]; int main () { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n ; for (int i=0; i<n; i++) cin >> a[i]; long long ansP =0; int cnt1 =0, cnt2 =0; int bal = 0; for (int i=0; i<n; i++) { if ( bal % 2 == 0) cnt1++; else cnt2++; if (a[i] <0) bal++; if ( bal%2 == 0) ansP += cnt1; else ansP += cnt2; } cout << ((long long)n)*(n+1)/2 - ansP << " " << ansP <<"\n"; }
반응형'알고리즘 문제 > math' 카테고리의 다른 글
중국인의 나머지 정리 (0) 2019.10.20 cf 585div2 B. The Number of Products (0) 2019.09.18 삼각형의 면적 구하기, 백준 2166 다각형의 면적 (0) 2019.03.20 백준 1081 합 (0) 2019.03.09 codeforces 1060C Maximum Subrectangle (0) 2018.12.13 908C New Year and Curling (0) 2017.12.31