이분탐색(2) - 차집합, 멀티버스Ⅱ, 합이 0

jemin0619 2024. 2. 22. 17:11

https://www.acmicpc.net/problem/1822

1822번: 차집합

첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소

www.acmicpc.net

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int aa,bb;
ll a[500003];
ll b[500003];
vector<ll> ans;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>aa>>bb;
    for(int i=0;i<aa;i++) cin>>a[i];
    for(int i=0;i<bb;i++) cin>>b[i];
    sort(a,a+aa);
    sort(b,b+bb);
    for(int i=0;i<aa;i++){
        if(!binary_search(b,b+bb,a[i])){
            ans.push_back(a[i]);
        }
    }
    cout<<ans.size()<<'\n';
    for(int i=0;i<(int)ans.size();i++) cout<<ans[i]<<' ';
    return 0;
}

https://www.acmicpc.net/problem/18869

18869번: 멀티버스 Ⅱ

M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍

www.acmicpc.net

erase를 쓰지 않고 중복 제거를 해서 좀 더러운데 동작은 잘 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int m,n; //우주 m개 행성 n개(1~n)
int a[103][10003]; //i번 우주, j번 행성
int b[103][10003];
vector<int> arr[103];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>m>>n;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
            if(arr[i].empty()||arr[i][j-1]!=a[i][j]) arr[i].push_back(a[i][j]);
        }
    }

    for(int i=0;i<m;i++) sort(arr[i].begin(),arr[i].end());

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            int idx = lower_bound(arr[i].begin(),arr[i].end(),a[i][j])-arr[i].begin();
            a[i][j]=idx;
        }
    }
    int ans=0;
    for(int i=0;i<m-1;i++){
        for(int j=i+1;j<m;j++){
            bool isSame=true;
            for(int k=0;k<n;k++){
                if(a[i][k]!=a[j][k]){
                    isSame=false;
                    break;
                }
            }
            if(isSame) ans++;
        }
    }
    cout<<ans;
    return 0;
}

https://www.acmicpc.net/problem/3151

3151번: 합이 0

Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다.

www.acmicpc.net

코드를 짜다가 중복되는 수가 나올 때의 처리를 고민했는데 고민할 필요가 없었다. 그냥 upper bound와 lower bound범위를 현재까지 더한 값 다음번 인덱스부터 시작하게 하면 고려하지 않아도 됐다.

#include <bits/stdc++.h>
using namespace std;

int n;
int a[10003];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    long long ans=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            auto ub = upper_bound(a + j + 1, a + n, -a[i] - a[j]);
            auto lb = lower_bound(a + j + 1, a + n, -a[i] - a[j]);
            ans += ub - lb;
        }
    }
    cout<<ans;
    return 0;
}