출처: https://cses.fi/problemset/task/1662 

문제 설명

Given an array of n integers, your task is to count the number of subarrays where the sum of values is divisible by n.

입력 

The first input line has an integer n: the size of the array.

The next line has n integers a_1,a_2,…,a_n: the contents of the array.

출력 

Print one integer: the required number of subarrays.

입력 예

5
3 1 2 7 4

출력 예

1

제약조건

  • 1 <= n <= 2x10^5
  • - 10^9 <=  a_i <= 10^9

문제 풀이 내용

배열의 입력값을 modulo 연산을 해서 더한 값을 저장한다. 이 값들은 입력하기 전에 한번더 modulo 연산을 하도록 하고, 음수인 경우는 양수가 되도록 한다. 이렇게 만들어진 값들을 map에 입력해서, 이 합의 배열의 차가 0이 되는 경우의 수를 센다. 

프로그램 내용

더보기 
...
    vector <long> num_arr(nNum, 0);
    vector <long> sum_arr(nNum+1, 0);

    for(int idx=0; idx < nNum; ++idx)
        cin >> num_arr[idx];
        sum_arr[idx+1] = (sum_arr[idx] + num_arr[idx])% nNum;
        if ( sum_arr[idx+1] < 0)
            sum_arr[idx+1] = (sum_arr[idx+1]+nNum) % nNum;
        else
            sum_arr[idx+1] %= nNum;

    long long ar_count = 0;
    map <int, int> r_map;
    r_map[0] = 1;

    for(int idx=0; idx < nNum; ++idx)
        auto au_it = r_map.find(sum_arr[idx+1]);
        if (au_it != r_map.end())
            ar_count += au_it->second;
        r_map[sum_arr[idx+1]]++;
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 3. Dynamic Programming  (0) 2019.10.09
CSES 2. Array Division (1085)  (0) 2019.10.09
CSES 2. Subarray Sums II (1661)  (0) 2019.10.09
CSES 3. Dice Combinations (1633)  (0) 2019.10.09
CSES 8. Minimal Rotation (1110)  (0) 2019.10.09

출처: https://cses.fi/problemset/task/1661

문제 설명

Given an array of n integers, your task is to count the number of subarrays having sum x.

입력 

The first input line has two integers n and x: the size of the array and the target sum x.

The next line has n integers a_1,a_2,…,a_n : the contents of the array.

출력 

Print one integer: the required number of subarrays.

입력 예

5 7
2 -1 3 5 -2

출력 예

2

제약조건

  • 1 <= n <= 2x10^5
  • −10^9 <= x, a_i <= 10^9

문제 풀이 

배열을 입력 받아서, 그 값들을 누적하고, 이렇게 만들어진 합들을 key 로 하는 map을 만든다. 

pre_sum[i] == tSum or pre_sum - tSum == pre_sum[j] 인 경우가 우리가 찾는 sub-array가 된다.

이런 경우들을 세서 출력한다.

프로그램 내용

더보기 
...
    vector <long> num_arr(nNum);
    vector <long long> sum_arr(nNum+1,0);

    for(int idx=0; idx < nNum; ++idx)
        cin >> num_arr[idx];
        sum_arr[idx+1] = sum_arr[idx] + num_arr[idx];

    map <long long, int> m_map;
    m_map[0] = 1;

    for (int idx=0; idx < nNum; ++idx) /// update map with array pre-sum
        m_map[sum_arr[idx+1]]++;

    long long answer = 0;
    for (int idx=0; idx < nNum; ++idx) 
        answer += m_map[sum_arr[idx+1] - tSum]; /// if pre_sum == tSum or diff of pre_sum == tSum
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Array Division (1085)  (0) 2019.10.09
CSES 2. Subarray Divisibility (1662)  (0) 2019.10.09
CSES 3. Dice Combinations (1633)  (0) 2019.10.09
CSES 8. Minimal Rotation (1110)  (0) 2019.10.09
CSES 2. Maximum Subarray Sum II (1644)  (0) 2019.10.08

출처: https://cses.fi/problemset/task/1633

문제 설명

Your task is to count the number of ways to construct sum n by throwing a dice one or more times. Each throw produces an outcome between 1 and 6.

For example, if n=3, there are 4 ways:

  • 1+1+1 
  • 1+2 
  • 2+1 
  • 3

입력  

The only input line has an integer n.

출력 

Print the number of ways modulo 10^9+7.

입력 예

3

출력 예

4

제약조건

1 <= n <= 10^6

문제 풀이 

주사위를 한번 던져서 나올 수 있는 수는 1~6까지 6가지 경우가 있으므로, 어떤 수 N을 만들기 위해서, 그 전까지 나왔던 경우의 수 (N-1) ~ (N-6)까지 합이 N을 만들 수 있는 경우의 수가 된다.

초기 조건으로 0~5까지 6개의 경우를 입력하고, 6 이상인 경우는 더해서 modulo 연산을 하고,  N이 1~5 인 경우는 초기 조건에서 출력한다.

프로그램 내용

더보기 
...
    vector<long> dp(6, 0);

    /// dp build up n < 6,
    dp[0] = 1; /// init
    dp[1] = 1;  /// dp[0]
    dp[2] = 2;  /// dp[0] + dp[1]
    dp[3] = 4;  /// dp[0] + dp[1] + dp[2]
    dp[4] = 8;  /// dp[0] + dp[1] + dp[2] + dp[3]
    dp[5] = 16; /// dp[0] + dp[1] + dp[2] + dp[3] + dp[4]

    for (int i = 6; i <= n; i++)
        dp[i] = (dp[i-6] + dp[i-5] + dp[i-4] + dp[i-3] + dp[i-2] + dp[i-1]) % 1000000007; 

...

 

Dynamic Programming ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Subarray Divisibility (1662)  (0) 2019.10.09
CSES 2. Subarray Sums II (1661)  (0) 2019.10.09
CSES 8. Minimal Rotation (1110)  (0) 2019.10.09
CSES 2. Maximum Subarray Sum II (1644)  (0) 2019.10.08
CSES 2. Movie Festival II (1632)  (0) 2019.10.07

출처: https://cses.fi/problemset/task/1110

문제 설명

A rotation of a string can be generated by moving characters one after another from beginning to end. For example, the rotations of acab are acab, caba, abac, and baca.

Your task is to determine the lexicographically minimal rotation of a string.

입력 

The only input line contains a string of length n. Each character is one of a–z.

출력

Print the lexicographically minimal rotation.

입력 예

acab

출력 예

abac

제약조건

1 <= n <=10^6

문제 풀이 내용

Booth algorithm (link) 을 구현해서 제일 빠른 문자열이 시작하는 위치를 계산한다.

입력 문자열을 2개 연결하고, 계산한 위치부터 원래 입력받은 문자열 길이만큼 출력한다.

프로그램 내용

더보기 
/// https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation
/// Booth algorithm

int booth_search(string str)
{
    string str_work = str + str;    /// Concatenate string to it self to avoid modular arithmetic

    int N = str_work.size();

    vector<int> f(N);            ///  Failure function
    f[0] = -1;

    int k = 0;                   /// Least rotation of string found so far

    for(int j=1; j < N; j++)
    {
        char sj = str_work[j];
        int i = f[j-k-1];
        while ( i != -1 && sj != str_work[k+i+1])
        {
            if ( sj < str_work[k+i+1])
                k = j - i - 1;
            i = f[i];
        }
        if (sj != str_work[k+i+1])
        {
            if ( sj < str_work[k])
                k = j;
            f[j-k] = -1;
        }
        else
            f[j-k] = i+1;
    }

    return k;
}

int main() {
...
	int move_size = booth_search(str_in);
	string str_work = str_in + str_in;
	string out = str_work.substr(move_size, str_in.size());
...

 

String Algorithms( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Subarray Sums II (1661)  (0) 2019.10.09
CSES 3. Dice Combinations (1633)  (0) 2019.10.09
CSES 2. Maximum Subarray Sum II (1644)  (0) 2019.10.08
CSES 2. Movie Festival II (1632)  (0) 2019.10.07
CSES 2. Subarray Sums I (1660)  (0) 2019.10.03

출처: https://cses.fi/problemset/task/1644

문제 설명

Given an array of n integers, your task is to find the maximum sum of values in a contiguous subarray with length between a and b.

입력 

The first input line has three integers n, a and b: the size of the array and the minimum and maximum subarray length.

The second line has n integers x_1,x_2,…,x_n: the array values.

출력 

Print one integer: the maximum subarray sum.

입력 예

8 1 2
-1 3 -2 5 3 -5 2 2

출력 예

8

제약조건

  • 1 <= n <= 2x10^5
  • 1 <= a <= b<= n
  • −10^9 <= x_i <= 10^9

문제 풀이 내용

입력을 받으면서, prefix sum을 계산한다. 특정한 구간 array[a] ~ array[b]의 합은 presum[b+1] - presum[a]를 통해서 구할 수 있다. subarray 길이에 따라서 값을 계산하도록 한다. 처음 알고리즘에서는 길이의 차가 5000이 넘어가면 제한시간에 걸렸다.

알고리즘 수정

prefix sum을 이용해서 읽어 들이면서, prefix sum의 위치가 a 보다 크면 multiset 에 prefix sum 값을 입력하고, 위치가 b 보다 커지면, 그 값들은 multiset에서 제외 시킨다. 부분합을 관리하는 방법은 queue, deque, priority queue 를 사용할 수도 있다.

프로그램 내용

더보기 
...
    vector <long long> num_array(nNum);
    long long sum_array[nNum+1] = {0};

    long long num_max= -1e18;
    long long best = -1e18, sum = -1e18;

    sum_array[0] = 0;

    for (int idx = 0; idx < nNum; ++idx)
        cin >> num_array[idx];
        sum_array[idx+1] = num_array[idx] + sum_array[idx];
        num_max = max(num_max, num_array[idx]);

... /// N^2 
	for (int width=minW; width<= maxW; ++width)
        if (width == 1)
            best = num_max;
        else
            int left=0, right= width;
            long long tsum=sum;
            for (int idx = 0; idx <= nNum - width ; ++idx)
                tsum = sum_array[right] - sum_array[left];
                sum = max(sum, tsum);
                left++;
                right++;

            best = max(best, sum);
...

 

 수정한 프로그램

더보기 
...
    maxW++; /// boundary

    vector <long long> num_array(nNum+1, 0);

    multiset <long long> sum_set;

    long long best = -1e18;

    for (int idx = 1; idx <= nNum; ++idx)
        cin >> num_array[idx];
        num_array[idx] += num_array[idx-1]; /// pre-sum update

        if ( idx - minW >= 0) /// window check
            sum_set.insert(num_array[idx-minW]);

        if ( idx - maxW >= 0) /// window check - too big
            sum_set.erase(sum_set.find(num_array[idx-maxW]));

        if ( sum_set.size()) /// check maximum
            best = max(best, num_array[idx]-*sum_set.begin());
...

 

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 3. Dice Combinations (1633)  (0) 2019.10.09
CSES 8. Minimal Rotation (1110)  (0) 2019.10.09
CSES 2. Movie Festival II (1632)  (0) 2019.10.07
CSES 2. Subarray Sums I (1660)  (0) 2019.10.03
CSES 2. Nearest Smaller Values (1645)  (0) 2019.10.03

출처: https://cses.fi/problemset/task/1632

문제 설명

In a movie festival, n movies will be shown.  movie club consists of k members, who will be all attending the festival.

You know the starting and ending time of each movie. What is the maximum total number of movies the club members can watch entirely if they act optimally?

입력 

The first input line has two integers n and k: the number of movies and club members.

After this, there are n lines that describe the movies. Each line has two integers aa and bb: the starting and ending time of a movie.

출력

Print one integer: the maximum total number of movies.

입력 예

5 2
1 5
8 10
3 6
2 5
6 9

출력 예

4

제약조건

  • 1 <= k <= n <= 2x10^5
  • 1 <= a <= b <= 10^9

문제 풀이 내용

입력받은 영화 시작시간과 끝나는 시간을 이용해서, (영화시간, 시작/끝, 영화순서) 를 영화시간을 기준으로 정렬한다. 영화시작시간이면 클럽 맴버를 보내고, 끝나는 시간이면 본 영화수를 증가시키고, 영화 보고 있는 클럽 맴버수를 감소 시킨다.  

프로그램 내용

더보기 
...
    vector <tuple<int, int>> m_time;

    for(int idx=0; idx < n_movie; ++idx)
        cin >> start_time >> end_time ;
        m_time.push_back({end_time, start_time});

    sort(m_time.begin(), m_time.end(), greater<tuple<int, int>>());

    vector<tuple<int, bool, int>> m_schedule(2*n_movie);

    for (int idx = 0; idx < n_movie; ++idx)
        tie(end_time, start_time) = m_time[idx];
        m_schedule[2*idx] = {start_time, 0, idx};
        m_schedule[2*idx + 1] = {end_time, 1, idx};

    sort(m_schedule.begin(), m_schedule.end());

    set <int> c_movie;
    int ct_member=0;
    int ct_movie=0;

    for (int idx=0; idx < 2*n_movie; ++idx)
        int m_time, m_idx;
        bool flag;
        tie(m_time,flag,m_idx) = m_schedule[idx];

        if(!flag) /// flag == 0, movie start time -> club member see
            c_movie.insert(m_idx);
            ct_member++;
        else if( c_movie.count(m_idx)) /// movie end,
            c_movie.erase(m_idx);
            ct_member--;
            ct_movie++;

        if ( idx < 2*n_movie -1 && get<0>(m_schedule[idx+1]) == m_time)
            continue;

        if (ct_member > n_member) /// can not exceed max member
            c_movie.erase(c_movie.begin());
            ct_member--;
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 8. Minimal Rotation (1110)  (0) 2019.10.09
CSES 2. Maximum Subarray Sum II (1644)  (0) 2019.10.08
CSES 2. Subarray Sums I (1660)  (0) 2019.10.03
CSES 2. Nearest Smaller Values (1645)  (0) 2019.10.03
CSES 2. Sum of Four Values (1642)  (0) 2019.10.02

출처: https://cses.fi/problemset/task/1660

문제 설명

Given an array of n positive integers, your task is to count the number of subarrays having sum x.

입력  

The first input line has two integers n and x: the size of the array and the target sum x.

The next line has n integers a_1,a_2,…,a_n: the contents of the array.

출력  

Print one integer: the required number of subarrays.

입력 예

5 7
2 4 1 2 7

출력 예

3

제약조건

  • 1 <= n <= 2x10^5
  • 1 <= x, a_i <= 10^9

문제 풀이 내용

배열의 값들을 더해가다가, 원하는 값보다 크거나 같아지면 제일 앞쪽 값을 삭제한다. 이때 값이 같은 경우 카운터를 기록해서 출력한다.  

프로그램 내용

더보기 
...
    vector <int> num_arr(nNum);

    int ar_count = 0;
    int ids=0;
    int ar_sum = 0;
    for(int idx=0; idx < nNum; ++idx)
        int temp;
        num_arr[idx] =  temp;
        ar_sum += num_arr[idx];
        while(ar_sum >= tSum)
            if (ar_sum == tSum) ar_count++;
            ar_sum -= num_arr[ids++];
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Maximum Subarray Sum II (1644)  (0) 2019.10.08
CSES 2. Movie Festival II (1632)  (0) 2019.10.07
CSES 2. Nearest Smaller Values (1645)  (0) 2019.10.03
CSES 2. Sum of Four Values (1642)  (0) 2019.10.02
CSES 2. Sum of Three Values (1641)  (0) 2019.10.02

출처: https://cses.fi/problemset/task/1645

문제 설명

Given an array of n integers, your task is to find for each array position the nearest position to its left having a smaller value.

입력 

The first input line has an integer n: the size of the array.

The second line has n integers x_1,x_2,…,x_n: the array values.

출력

Print n integers: for each array position the nearest position with a smaller value. If there is no such position, print 0.

입력 예

8
2 5 1 4 8 3 2 5

출력 예

0 1 0 3 4 3 3 7

제약조건

  • 1 <= n <= 2x10^5 
  • 1 <= x_i <= 10^9

문제 풀이 내용

stack에 작은 값의 위치를 기록한다. 기록된 작은 값의 위치의 값과 새로운 입력을 비교해서 작으면 위치를 출력한다. 새로운 입력의 값이 가장 지금까지 입력중에 가장 작으면 0, 아니면 기록하는 위치를 갱신한다. 출력하는 값은 배열 값이 아니라, 배열 위치이므로 출력할때는 +1을 해준다.

프로그램 내용

더보기 
...
    vector <long> in_num;

    for(int idx=0; idx < nNum; ++idx)
        int temp;
        in_num.push_back(temp);

    stack<int, vector<int>> num_stack;

    for(int idx = 0 ; idx < nNum; ++idx) 
        while(!num_stack.empty() && in_num[num_stack.top()] >= in_num[idx]) 
            num_stack.pop();

        if(num_stack.empty()) 
            cout << "0 " ; 
        else 
            cout << num_stack.top()+1 << " ";

        num_stack.push(idx);
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Movie Festival II (1632)  (0) 2019.10.07
CSES 2. Subarray Sums I (1660)  (0) 2019.10.03
CSES 2. Sum of Four Values (1642)  (0) 2019.10.02
CSES 2. Sum of Three Values (1641)  (0) 2019.10.02
CSES 2. Reading Books (1632)  (0) 2019.10.02

출처: https://cses.fi/problemset/task/1642

문제 설명

You are given an array of n integers, and your task is to find four values (at distinct positions) whose sum is x.

입력 

The first input line has two integers n and x: the array size and the target sum.

The second line has n integers a_1,a_2,…,a_n: the array values.

출력 

Print four integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

입력 예

8 15
3 2 5 8 1 3 2 3

출력 예

2 4 6 7

제약조건

  • 1 <= n <= 1000
  • 1 <= x, a_i <= 10^9

문제 풀이 내용

서로 다른 배열의 원소 2개의 합으로 새로운 배열을 만든다. 그러면 배열에서 2개의 합으로 원하는 수를 만드는 문제로 바꿀 수 있다. (참고) 다만, 원래 배열에서 4개의 원소가 달라야 하는 조건을 확인해야 한다.

프로그램 내용

더보기 
...
    vector <tuple <long, int, int> > num_arr;

    for(int idx=0; idx < nNum; ++idx)
        int temp;
        in_num.push_back(temp);

    for(int idx=0; idx < nNum-1; ++idx)
        for(int id = idx+1; id < nNum ; ++ id)
            num_arr.push_back(make_tuple(in_num[idx]+in_num[id], idx+1, id+1));

    sort(num_arr.begin(), num_arr.end());

    int id = 0, idx = num_arr.size()-1;
    while( id < idx )
        long a, b, c, d, e, f;
        tie(a, b, c) = num_arr[id];
        tie(d, e, f) = num_arr[idx];
        long k = a+d;

        if (k == tSum)
            if ( b == e || c == f)
                break;
            else
                cout << b << " " << c << " " << e << " " << f << endl;
        else if ( k < tSum) id++;
        else idx--;
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Subarray Sums I (1660)  (0) 2019.10.03
CSES 2. Nearest Smaller Values (1645)  (0) 2019.10.03
CSES 2. Sum of Three Values (1641)  (0) 2019.10.02
CSES 2. Reading Books (1632)  (0) 2019.10.02
CSES 2. Factory Machines (1620)  (0) 2019.10.01

출처: https://cses.fi/problemset/task/1641

문제 설명

You are given an array of n integers, and your task is to find three values (at distinct positions) whose sum is x.

입력 

The first input line has two integers n and x: the array size and the target sum.

The second line has n integers a_1,a_2,…,a_n : the array values.

출력

Print three integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

입력 예

4 8
2 7 5 1

출력 예

1 3 4

제약조건

  • 1 <= n <= 5000
  • 1 <= x, a_i <= 10^9

문제 풀이 

첫번째 수를 고정하고, 필요한 수에서 그 수만큼을 빼내면, n-1 배열에서 2개의 합으로 (x - a_i)를 만드는 문제가 된다. 참고

프로그램 내용

더보기 
...
    vector <pair <long, long> > num_arr;

    for(int idx=0; idx < nNum; ++idx)
        int temp;
        num_arr.push_back({temp, idx+1});

    sort(num_arr.begin(), num_arr.end());

    for (int a=0; a < nNum-2; ++a)
        int b = a+1 , c = nNum-1;
        int ttSum = tSum - num_arr[a].first;
        while( b < c )
            int k = num_arr[b].first + num_arr[c].first;

            if (k == ttSum)
                cout << num_arr[a].second << " " << num_arr[b].second << " " << num_arr[c].second << endl;
            else if ( k < ttSum) b++;
            else c--;
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Nearest Smaller Values (1645)  (0) 2019.10.03
CSES 2. Sum of Four Values (1642)  (0) 2019.10.02
CSES 2. Reading Books (1632)  (0) 2019.10.02
CSES 2. Factory Machines (1620)  (0) 2019.10.01
CSES 2. Room Allocation (1164)  (0) 2019.10.01

+ Recent posts

티스토리툴바