Round #919 Div. 2 - 2sol

https://codeforces.com/contest/1920

Dashboard - Codeforces Round 919 (Div. 2) - Codeforces

 

A - Satisfying Constraints

입력으로 a k 가 주어졌을 때, 아래 조건을 만족하는 k의 개수 구하는 문제

1. 1 x: k >= x
2. 2 x: k <= x
3. 3 x: k != x 

x의 범위가 10^9이므로 배열을 만드는 것은 무리이고,

1 ~ 10^9을 모두 탐색하기에는 시간이 부족하다.

그러므로 1 x 입력 중 가장 큰 것을 g, 2 x 입력 중 가장 작은 값을 l로 저장하고,

 g <= k <= l를 만족하며 3 x 입력에서 나온 x를 제거해주면 된다. 

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n, t, a, x; cin >> t;
    while(t--){
        vector<int>e;
        int g=-1, l=2147483647, ans=0;
        cin >> n;
        while(n--){
            cin >> a >> x;
            if(a==1) g=max(g,x);
            else if(a==2) l=min(l, x);
            else e.push_back(x);
        }
        ans=l-g+1;
        for(auto p : e) if(p>=g && p<=l) ans--;
        cout << max(0,ans) << "\n";
    }
}

 

---

 

B - Summation Game

Alice는 수열의 원소의 합을 최대로하기 위해 수열에서 필요없는 원소를 제거하고,

Bob은 수열의 원소의 합을 최소로하기 위해 수열의 어떤 수를 음수로 바꾼다.

 

Bob은 무조건 가장 큰 수를 음수로 바꿀 것이고, 본인이 바꿀 수 있는 최대한으로 바꿀 것이다.

Alice는 Bob이 바꿀 수를 미리 제거해야하는데, 얼만큼 제거해야하는지를 묻는 문제이다.

그래서 누적 합으로 접근하여 문제를 해결했다.

먼저 Bob이 가장 큰 원소들을 음수로 바꾸었을 때의 수열의 합을 계산하여 디폴트로 구해준다.

이후 Alice가 양수였을 때 가장 큰 원소를 제거하고, Bob이 다음으로 큰 수를 음수로 바꾸었을 때의 합을 계산하여

이를 Alice가 제거할 수 있는 횟수까지 반복한다.

최종적으로 합이 가장 큰 경우를 출력해주면 된다.

#include <iostream>
#include <algorithm>
using namespace std;
int dp[200001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, t, k, x, ans, res; cin >> t;
    while(t--){
        res=0;
        cin >> n >> k >> x;
        for(int i=0; i<n; i++){
            cin >> dp[i];
            res+=dp[i];
        }
        sort(dp, dp+n);
        int cur=1, prev=1;
        while(x--) {
            res-=(dp[n-cur]*2);
            cur++;
        }
        ans=res;
        while(k--){
            res+=dp[n-prev];
            if(n>=cur) res-=(dp[n-cur]*2);
            cur++, prev++;
            ans=max(ans,res);
        }
        cout << ans << "\n";
    }
}

 

---

 

C - Partitioning the Array

수열이 주어졌을 때, 수열을 부분수열로 나눈다.

나누는 조건은 부분수열의 각 원소를 M으로 나누었을 때의 나머지를 새로운 수열로 만드는데,

만든 새로운 수열이 모두 일치하면 카운트를 하나 증가시킨다.

 

임의의 두 정수 x, y에 대해

x % M == y % M 을 만족한다면 (x - y) % M = 0을 만족한다.

이를 확장하여

A1 % M == A1+k % M

A2 % M == A2+k % M

A3 % M == A3+k % M

...

이런식으로 진행하는데,

mod M 이므로 gcd((A1 - A1+k), (A2 - A2+k), (A3 - A3+k) ... )의 값이 1이 아닌 수라면

해당 부분 수열을 만족하게 된다.

#include <iostream>
using namespace std; 
int gcd(int x, int y){
    return y ? gcd(y, x%y) : x;
}
int main(){
    int t, n; 
    cin >> t;
    while(t--){
        cin >> n;
        int* arr=new int[n];
        for (int i=0; i<n; i++) cin >> arr[i];
        int ans=0, res;
        for(int i=1; i<=n; i++){
            if(n%i==0){
                res=0;
                for(int j=0; j+i<n; j++){
                    res=gcd(res, abs(arr[i+j]-arr[j]));
                }
                if(res!=1) ans++;
            }
        }
        cout << ans << "\n";
    }
}

해당 문제는 웰노운이라고 한다.