ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 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:

    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";
    }

    댓글 0

Designed by Tistory.