PS Diary #2

CSES. Bit Inversions

  set by hasing, data structure

  $x_1$부터 $x_n$까지 중에 $x_i \neq x_{i-1}$인 $i$들을 저장해서 $i_{0}, ... , i_{k}$라고 하자 $($단, $i$중에는 0과 $n$은 반드시 포함해서 $i_{0} = 0, i_{k} = n$임$)$. 그럼 우리가 구하고자 하는 정답은 아래처럼 표현됨. $$\max_{1\leq j \leq k}{(i_j -i_{j-1})}$$ 이걸 $log$시간 안에 처리할 수 있기만 하면 $O(m\log{n})$에 가능. 이를 위해 set을 이용할 수 있음. 각 쿼리마다 업데이트 할 때 자신의 인덱스나 자신 - 1의 인덱스가 이미 set 안에 들어 있다면 제거 후 인덱스 끼리의 차를 업데이트해서 집어넣어주면 됨. 그중 최대를 각 쿼리마다 출력해주면 정답임. 이때 인덱스끼리의 차가 중복이 될 수도 있으니 차를 저장하는 set은 multiset으로 함.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;

set<int> indices;
multiset<int> diff;
string bits;
int n,m;

void modify(const int &x){
    if(x == 0 || x == n) return;
    auto it = indices.find(x);
    if(it != indices.end()){
        int a = *next(it), b = *prev(it);
        diff.insert(a-b);
        diff.erase(diff.find(a-*it));
        diff.erase(diff.find(*it-b));
        indices.erase(it);
    } else {
        indices.insert(x);
        it = indices.find(x);
        int a = *next(it), b = *prev(it);
        diff.erase(diff.find(a-b));
        diff.insert(a-x);
        diff.insert(x-b);
    }
}

int main(){
    fastio;
    cin>>bits;
    n = bits.size();
    indices.insert(0);
    indices.insert(n);
    for(int i=1;i<n;i++){
        if(bits[i] != bits[i-1]) indices.insert(i);
    }
    for(auto it=indices.begin();next(it)!=indices.end();it++){
        diff.insert(*next(it)-*it);
    }
    
    cin>>m;
    for(int i=0;i<m;i++){
        int x; cin>>x;
        modify(x-1);
        modify(x);
        auto it = diff.end();
        cout<<*(--it)<<" ";
    }
}

 

 

 

BOJ 22860. 폴더 정리 $($small$)$

 dfs, set by hasing

 이 문제는 그냥 생각나는대로 구현함. $N,M \leq 10^3$밖에 안돼서 가지치기 안하고 dfs로만 구현해도 $O(MN)$에 가능함. graph를 unordered map형태로 저장하는 것과 파일 방문 처리, 경로에서 마지막 파일 혹은 폴더 추출해내는 것만 잘 구현해주면 문제 없음

 

#include <bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
typedef pair<string,bool> psb;
typedef vector<psb> vsb;

unordered_map<string,vsb> graph;
unordered_map<string,bool> isVisited;
vector<string> files;
int N,M;

void init(){
    for(string f : files) isVisited[f] = false;
}

pair<int,int> dfs(string data){
    if(graph[data].empty()) return {0,0};
    
    int fileNum = 0, fileTypeNum = 0;
    for(psb p : graph[data]){
        if(p.second){
            pair<int,int> q = dfs(p.first);
            fileTypeNum += q.first;
            fileNum += q.second;
        } else {
            if(isVisited[p.first]) {
                fileNum ++;
                continue;
            }
            isVisited[p.first] = true;
            fileTypeNum ++;
            fileNum ++;
        }
    }
    return make_pair(fileTypeNum, fileNum);
}

int main(){
    fastio;
    cin>>N>>M;
    for(int i=0;i<N+M;i++){
        string s1, s2; cin>>s1>>s2;
        bool C; cin>>C;
        graph[s1].push_back(make_pair(s2,C));
        if(!C) files.push_back(s2);
    }
    
    int Q; cin>>Q;
    while(Q--){
        init();
        string directory; cin>>directory;
        string goal = "";
        for(int i=0;i<directory.size();i++){
            if(directory[i] == '/') goal = "";
            else goal += directory[i];
        }
        pair<int,int> p = dfs(goal);
        cout<<p.first<<" "<<p.second<<'\n';
    }
}

 

 

CodeForces Round 995. Best Price

 sorting, binay search, greedy

문제를 관찰하다보면 그리디적으로, 경계 값에 놓인 $($a또는 b인$)$ 수가 항상 최선의 가격이 되는 것을 알 수 있음. 그래서 탐색 범위를 먼저 $2n$으로 줄일 수 있음. 그럼 $O(n)$만에 가능한 가격들을 모두 탐색 가능한 것이니 log 시간안에 negative reviews 개수랑 얻는 수익을 계산할 수 있으면 답을 계속 업데이트 해주며 찾을 수 있음. 이는 약간의 수학적인 사고를 이용하면 정렬을 하고 이분탐색을 통해 알 수 있다는 것을 깨닫게 됨. 전체적인 시간복잡도는 $O(t\times n)$임.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int nmax = 2e5;
 
int n,k;
ll a[nmax + 10], b[nmax + 10];
 
void solve(){
    sort(a,a+n);
    sort(b,b+n);
    ll ans = 0;
    for(int i=0;i<n;i++){
        ll price = a[i];
        int idx1 = lower_bound(b,b+n,price) - b;
        int idx2 = lower_bound(a,a+n,price) - a;
        ll peopleWhoBuyNum = n - idx1;
        ll nrNum = peopleWhoBuyNum - (n - idx2);
        if(nrNum > k) continue;
        ans = max(ans, peopleWhoBuyNum * price);
    }
    
    for(int i=0;i<n;i++){
        ll price = b[i];
        int idx1 = lower_bound(b,b+n,price) - b;
        int idx2 = upper_bound(a,a+n,price) - a;
        ll peopleWhoBuyNum = n - idx1;
        ll nrNum = peopleWhoBuyNum - (n - idx2);
        if(nrNum > k) continue;
        ans = max(ans, peopleWhoBuyNum * price);
    }
 
    cout<<ans<<"\n";
}
 
int main(){
    cin.tie(0)->ios::sync_with_stdio(0);
    int t; cin>>t;
    while(t--){
        cin>>n>>k;
        for(int i=0;i<n;i++) cin>>a[i];
        for(int i=0;i<n;i++) cin>>b[i];
        solve();
    }
}

 

 

CodeForces Round 994. Easy Demon Problem

math, binary search

차근차근 수학적으로 접근하면 풀이가 보였음. $n,m \leq 2\times 10^5$이고 $q \leq 5 \times 10^4$이라서 $O(nq)$ 혹은 $O(mq)$로만 짜도 시간초과가 남. 먼저 a배열의 숫자들의 합을 $S_1$, b배열의 숫자들의 합을 $S_2$라고 하자. 이때 배열 M의 숫자의 총합은 $S_1 \times S_2$가 자명함. 여기서 $(r,c)$에 대해 문제에서 주어진 시행을 한 경우 전체 숫자들의 총합은 $S_1\times S_2 - a[r] \times S_2 - b[c] \times S_1 + a[r]\times b[c]$가 됨. 이를 조금만 정리해보면 $(a[r] - S_1)(b[c] - S_2)$라는 것을 알 수 있음. 그리고 이 값이 $x$가 되도록 하는 $(r,c)$가 존재한다면 "YES"이고 존재하지 않는다면 "NO"임. $A[i] = a[i] - S_1, B[i] = b[i] - S_2$인 배열 A,B를 생각해보면 문제는 $A[r]\times B[c] = x$인 $(r,c)$를 찾는 것으로 바뀜. 이때 모든 값이 정수이므로 쉬운 부정방정식 형태로 나타나지고 $A[r],B[c]$는 모두 $x$의 약수임. 따라서 약수 쌍들을 모두 탐색하는 시간복잡도는 많아야 $O(\sqrt{x})$이므로 log 시간 안에 이 쌍들이 존재하는지 확인할 수 있다면 $O(q(\log{}{MN})\sqrt{x})$만에 처리할 수 있음. 이것은 이분탐색을 이용하거나 편하게 set에 저장해놓고 찾으면 됨.

#include <bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
typedef long long ll;
const int nmax = 2e5;

ll n,m,q,S1=0,S2=0;
ll a[nmax + 10], b[nmax + 10];
set<ll> InA, InB;

void solve(ll x){
    int absol = x > 0 ? x : -1*x;
    if(absol == 0){
        auto it1 = InA.find(0), it2 = InB.find(0);
        if(it1 != InA.end() || it2 != InB.end()) cout<<"YES"<<"\n";
        else cout<<"NO"<<"\n";
    } else {
        for(ll d=1;d*d<=absol;d++){
            if(absol % d != 0) continue;
            ll d1 = d, d2 = x / d;
            ll D1 = -1*d, D2 = x / D1;
            auto it1 = InA.find(d1), it2 = InB.find(d2);
            if(it1 != InA.end() && it2 != InB.end()){
                cout<<"YES"<<"\n";
                return;
            }
            it1 = InB.find(d1), it2 = InA.find(d2);
            if(it1 != InB.end() && it2 != InA.end()){
                cout<<"YES"<<"\n";
                return;
            }
            it1 = InA.find(D1), it2 = InB.find(D2);
            if(it1 != InA.end() && it2 != InB.end()){
                cout<<"YES"<<"\n";
                return;
            }
            it1 = InB.find(D1), it2 = InA.find(D2);
            if(it1 != InB.end() && it2 != InA.end()){
                cout<<"YES"<<"\n";
                return;
            }
        }
        cout<<"NO"<<"\n";
    }
}

int main(){
    fastio;
    cin>>n>>m>>q;
    for(int i=0;i<n;i++) {
        cin>>a[i];
        S1 += a[i];
    }
    for(int i=0;i<m;i++) {
        cin>>b[i];
        S2 += b[i];
    }
    
    for(int i=0;i<n;i++) InA.insert(a[i] - S1);
    for(int i=0;i<m;i++) InB.insert(b[i] - S2);
    
    while(q--){
        ll x; cin>>x;
        solve(x);
    }
}