cf 585div2 B. The Number of Products

반응형

You are given a sequencea1,a2,…,ana1,a2,…,anconsisting ofnnnon-zero integers (i.e.ai≠0ai≠0).

You have to calculate two following values:

1. 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;
2. 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