Codeforces Round #738 (Div. 2)

https://codeforces.com/contest/1559

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

codeforces.com

바로 이전 라운드인 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$ 의 간선이 존재하는 경우를 찾아주면된다. 너무 당연한 것인데 한번 틀린 후 이상한 $S C C +$ 위상정렬 $+ D P$ 풀이를 짜느라 시간을 버렸다. 도저히 이건 아니다 싶어서 겨우 정풀로 돌아왔다.

시간복잡도 : $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

풀이

$g c d$ 조건이 없다면 $K n a p s a c k D p$ 로 쉽게 해결할 수 있다. 그러면 어떻게하면 $g c d$ 의 조건을 생각하지 않고 무지성으로 $k n a p s a c k D p$ 를 박을 수 있을까? 포함배제의 원리를 이용해 이를 해결할 수 있다.

$\begin{aligned} | ⋃_{i = 1}^{n} A_{i} | & = \sum_{i = 1}^{n} | A_{i} | - \sum_{i, j : 1 \leq i < j \leq n} | A_{i} \cap A_{j} | \\ + \sum_{i, j, k : 1 \leq i < j < k \leq n} | A_{i} \cap A_{j} \cap A_{k} | - \dots + {(- 1)}^{n - 1} | A_{1} \cap \dots \cap A_{n} | \end{aligned}$

라는 식은 집합에서 기본이 된다. 여기서 각 집합들을 $A_{i}$ 는 i의 배수들로 이루어진 정답의 개수( $g c d$ 조건 제외)를 대입하면 답을 얻을 수 있다. 소인수의 개수가 홀수 개인 것들은 빼주고 짝수는 더한다. 그리고 제곱수가 약수로 존재하는 것들은 계산에 포함하지 않는다. 이것은 $M o b i u s f u n c t i o n$ 의 정의와 동일하기 때문에 그대로 구현하면 된다.

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

최종적으로 $1$ 부터 $M$ 까지 $d$ 를 이터레이팅시키고 이 합이 $⌊ \frac{M}{d} ⌋$ 이하가 되는 경우를 $K n a p s a c k D p$ 로 구해주면된다. $K n a p s a c k D p$ 를 $M$ 번하면 $O (N M^{2})$ 이 아니냐 할 수 있는데 이는 $h a r m o n i c$ $l e m m a$ 에 의해 $O (N M l o g M)$ 이 된다.

시간 복잡도 : $O (N M l o g M)$

전체 코드

#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;
}

'Codeforces' 카테고리의 다른 글

Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2) (0)	2021.11.29
Codeforces Round #757 (Div. 2) (0)	2021.11.28
Codeforces Round #741 (Div. 2) (1)	2021.09.02
Codeforces Round #739 (Div. 3) (0)	2021.08.19
Codeforces Round #737 (Div. 2) (0)	2021.08.11

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

amsminn

Codeforces Round #738 (Div. 2)

A. Mocha and Math

B. Mocha and Red and Blue

C. Mocha and Hiking

D1. Mocha and Diana (easy version)

D2. Mocha and Diana (easy version)

E. Mocha and Stars

'Codeforces' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

Codeforces Round #738 (Div. 2)

A. Mocha and Math

B. Mocha and Red and Blue

C. Mocha and Hiking

D1. Mocha and Diana (easy version)

D2. Mocha and Diana (easy version)

E. Mocha and Stars

'Codeforces' 카테고리의 다른 글

'Codeforces' Related Articles

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역