Codeforces Round #738 (Div. 2)

https://codeforces.com/contest/1559

Dashboard - Codeforces Round #738 (Div. 2) - Codeforces

바로 이전 라운드인 737에 이어 또 블루 퍼포먼스가 나왔다. 그덕에 민트를 달성하게 되었고 너무 행복하다. 

그리고 내가 처음으로 모든 문제를 업솔빙한 div2 라운드이다.

---

A. Mocha and Math

Tag : Bitsmasks, Math

 

풀이

부분 수열중에 부분 수열의 모든 원소를 bitwise and 한 결과의 최소를 구하는 문제인데, and를 하면 작아지면 작아지지 커지는 경우는 없기 때문에 모든 원소를 bitwise and 해주면된다.

 

시간복잡도 : \(O(N)\)

 

전체 코드

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        vector<int> v(n); for(auto &i : v) cin >> i;
        ll ans = v[0];
        for(int i = 1; i<n; i++) ans &= v[i];
        cout << ans << endl;
    }
}

---

B. Mocha and Red and Blue

Tag : Greedy

 

풀이

여는 괄호와 닫는 괄호를 번갈아주는 것이 항상 최선이다. 

 

시간복잡도 : \(O(|S|)\)

 

전체 코드

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
 
void solve(){
    int n; cin >> n;
    string s; cin >> s;
    string t;
    if(s.size()>1 and s[1]=='R') t += 'B';
    if(s.size()>1 and s[1]=='B') t += 'R';
    if(s.size()==1){
        if(s[0]=='?') t += 'B';
        else t += s[0];
    }
    for(int i = 1; i<s.size(); i++){
        if(s[i]!='?') t += s[i];
        else if(t.back() == 'R') t += 'B';
        else t += 'R';
    }
    cout << t << endl;
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int t; cin >> t;
    while(t--){
        solve();
    }
}

---

C. Mocha and Hiking

Tag : Constructive, Graph Theory

 

풀이

\(N->N+1\)의 간선이 존재하는 경우, \(N+1->1\)의 간선이 존재하는 경우, \(i->N+1\)과 \(N+1->i+1\)의 간선이 존재하는 경우를 찾아주면된다. 너무 당연한 것인데 한번 틀린 후 이상한 \(SCC +\)위상정렬\(+DP\) 풀이를 짜느라 시간을 버렸다. 도저히 이건 아니다 싶어서 겨우 정풀로 돌아왔다.

 

시간복잡도 : \(O(N)\)

 

전체 코드

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
 
void solve(){
    int N; cin >> N;
    vector<int> in(N + 2), out(N + 2);
    for(int i = 1; i<=N; i++){
        int x; cin >> x;
        if(x == 0) out[i]=1;
        else in[i]=1;
    }
    if(out[N]==1){
        for(int i = 1; i<=N+1; i++) cout << i << ' ';
        cout << endl;
        return;
    }
    if(in[1]==1){
        cout << N + 1 << ' ';
        for(int i = 1; i<=N; i++) cout << i << ' ';
        cout << endl;
        return;
    }
    for(int i = 1; i<=N-1; i++){
        if(out[i] and in[i+1]){
            for(int j = 1; j<=i; j++) cout << j << ' ';
            cout << N + 1 << ' ';
            for(int j = i + 1; j<=N; j++) cout << j << ' ';
            cout << endl;
            return;
        }
    }
    cout << -1 << endl;
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int t; cin >> t;
    while(t--){
        solve();
    }
}

---

D1. Mocha and Diana (easy version)

Tag : Constructive, DSU, Greedy

 

풀이

\(\binom{N}{2}\)개의 간선을 모두 돌아보며 간선의 양 끝점이 서로 다른 집합에 속하면 연결한다. 

 

시간 복잡도 : \(O(N^2)\)

 

전체 코드 

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
 
struct DSU{
    vector<int> pa;
    void init(int n){
        pa.resize(n + 1);
        for(int i = 1; i<=n; i++) pa[i]=i;
    }
    int find(int a){
        if(a == pa[a]) return a;
        else return pa[a] = find(pa[a]);
    }
    int check(int a, int b){ return find(a) == find(b); }
    void merge(int a, int b){ pa[find(b)]=find(a); }
};
 
void solve(){
    int N,m1,m2; cin >> N >> m1 >> m2;
    DSU A, B;
    A.init(N + 1), B.init(N + 1);
    for(int i = 1; i<=m1; i++){
        int a, b; cin >> a >> b;
        A.merge(a,b);
    }
    for(int i = 1; i<=m2; i++){
        int a, b; cin >> a >> b;
        B.merge(a,b);
    }
    int ans = 0;
    vector<pair<int,int>> edge;
    for(int i = 1; i<=N; i++){
        for(int j = i + 1; j<=N; j++){
            if(A.check(i,j)==0 and B.check(i,j)==0) A.merge(i,j), B.merge(i,j),ans++,edge.pb({i,j});
        }
    }
    cout << ans << endl;
    for(auto &[i,j] : edge) cout << i << ' ' << j << endl;
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int tc=1;
//    cin >> tc;
    while(tc--){
        solve();
    }
}

---

D2. Mocha and Diana (easy version)

Tag : Constructive, DSU, Greedy

 

풀이

\(\binom{N}{2}\)개의 간선을 모두 돌아보기에는 \(N\)제한이 커졌다. 일단 두 포레스트에서 모두 1과 다른 집합에 있는 정점들을 1과 이어준다. 그 후 한 포레스트에서는 1번과 같은 집합, 반대 포레스트에서는 그렇지 않은 것들끼리 이어주면된다. small to large니 뭐니하면서 뇌절하다 대회가 끝났다.. 좀 많이 아쉬운 문제다.

 

시간 복잡도 : \(O(N)\)

 

전체 코드 

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
 
struct DSU{
    vector<int> pa;
    void init(int n){
        pa.resize(n + 1);
        for(int i = 1; i<=n; i++) pa[i]=i;
    }
    int find(int a){
        if(a == pa[a]) return a;
        else return pa[a] = find(pa[a]);
    }
    int check(int a, int b){ return find(a) == find(b); }
    int merge(int a, int b){
        a = find(a), b = find(b);
        if(a==b) return 0;
        pa[b]=a;
        return 1;
    }
};
 
void solve(){
    int N,m1,m2; cin >> N >> m1 >> m2;
    DSU A, B;
    A.init(N + 1), B.init(N + 1);
    for(int i = 1; i<=m1; i++){
        int a, b; cin >> a >> b;
        A.merge(a,b);
    }
    for(int i = 1; i<=m2; i++){
        int a, b; cin >> a >> b;
        B.merge(a,b);
    }
    vector<pair<int,int>> v;
    for(int i = 1; i<=N; i++){
        int a=A.find(1), b=A.find(i), c=B.find(1), d=B.find(i);
        if(a==b or c==d) continue;
        A.merge(a,b); B.merge(c,d);
        v.pb({1,i});
    }
    vector<int>x,y;
    for(int i = 1; i<=N; i++){
        int a=A.find(1), b=A.find(i), c=B.find(1), d=B.find(i);
        if(a!=b) x.pb(b), A.merge(a,b);
        if(c!=d) y.pb(d),B.merge(c,d);
    }
    cout << v.size()+min(x.size(),y.size()) << endl;
    for(auto &[i,j]:v) cout<<i<<' '<<j<<endl;
    for(int i = 0; i<min(x.size(),y.size()); i++) cout<<x[i]<<' '<<y[i]<<endl;
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int tc=1;
//    cin >> tc;
    while(tc--){
        solve();
    }
}

---

E. Mocha and Stars

Tag : Constructive, DSU, Greedy

 

풀이

\(gcd\)조건이 없다면 \(KnapsackDp\)로 쉽게 해결할 수 있다. 그러면 어떻게하면 \(gcd\)의 조건을 생각하지 않고 무지성으로 \(knapsackDp\)를 박을 수 있을까? 포함배제의 원리를 이용해 이를 해결할 수 있다. 

 

\begin{aligned}\\{\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\&{}\qquad +\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ +\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|\end{aligned}

라는 식은 집합에서 기본이 된다. 여기서 각 집합들을 \(A_i\)는 i의 배수들로 이루어진 정답의 개수(\(gcd\) 조건 제외)를 대입하면 답을 얻을 수 있다. 소인수의 개수가 홀수 개인 것들은 빼주고 짝수는 더한다. 그리고 제곱수가 약수로 존재하는 것들은 계산에 포함하지 않는다. 이것은 \(Mobius function\)의 정의와 동일하기 때문에 그대로 구현하면 된다. 

 

또는 \(\sum_{i|d}\mu(i)\)는 d가 1일 때를 제외하면 모두 0이기 때문에 이를 이용할 수도 있다. 이는 생각보다 증명하기 쉽다. 이 풀이 또한 결국엔 같은 형태로 바뀐다. 

 

최종적으로 \(1\)부터 \(M\)까지 \(d\)를 이터레이팅시키고 이 합이 \(\lfloor{\frac{M}{d}}\rfloor\)이하가 되는 경우를 \(KnapsackDp\)로 구해주면된다. \(KnapsackDp\)를 \(M\)번하면 \(O(NM^2)\)이 아니냐 할 수 있는데 이는 \(harmonic\) \(lemma\)에 의해 \(O(NMlogM)\)이 된다.

 

시간 복잡도 : \(O(NMlogM)\)

 

전체 코드 

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
 
int mu[101010];
 
void init() {
    mu[1] = 1;
    for (int i = 1; i <= 100000; i++)
        for (int j = i + i; j <= 100000; j += i)
            mu[j] -= mu[i];
}
 
int N, M;
int L[55],R[55];
ll dp[101010], sum[101010];
ll ans = 0;
const ll MOD = 998244353;
 
ll cnt(int g){
    int m=M/g;
    dp[0]=1;
    for(int i=1;i<=m;i++)dp[i]=0;
    for(int i=1;i<=N;i++){
        int l=(L[i]+g-1)/g,r=R[i]/g;
        if(l>r) return 0;
        sum[0]=dp[0];
        for(int j=0;j<=m;j++) sum[j]=(dp[j]+sum[j-1])%MOD;
        for(int j=0;j<=m;j++){
            dp[j]=0;
            if(j-l>=0) dp[j]=(dp[j]+sum[j-l])%MOD;
            if(j-r-1>=0) dp[j]=(dp[j]-sum[j-r-1]+MOD)%MOD;
            dp[j]%=MOD;
        }
    }
    ll ret=0;
    for(int i=1;i<=m;i++) ret=(ret+dp[i])%MOD;
    return ret;
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    init();
    cin>>N>>M;
    for(int i=1;i<=N;i++) cin>>L[i]>>R[i];
    for(int i=1;i<=M;i++) ans=(ans+mu[i]*cnt(i)+MOD)%MOD,ans%=MOD;
    cout<<ans<<endl;
}