Codeforces Round #766 (Div. 2)

https://codeforces.com/contest/1627

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

b치고 좀 어려운 놈이 있었고, c에 그래프 + 구성적, d는 쉬운 정수론... 바람직한 셋이었다.

이번 셋을 잘풀어서 1854 퍼포먼스를 뽑았는데 기분이 좋다.

---

A. Not Shading

Tag : 무지성

 

풀이

(r, c)가 B라면 0, 같은 행 또는 열에 B가 존재한다면 1 아니면 2이다. 

전체에 B가 하나도 없다면 -1을 출력하면 된다.

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'
 
using namespace std;
using ll = long long;
 
void solve() {
    int n, m, r, c; cin >> n >> m >> r >> c;
    vector<vector<char>> v(n + 1, vector<char>(m + 1));
    int f = 0;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin >> v[i][j], f |= v[i][j] == 'B';
    if(f) {
        if(v[r][c] == 'B') cout << 0 << endl;
        else {
            int C = 0;
            for(int i=1; i<=n; i++) C |= v[i][c] == 'B';
            for(int j=1; j<=m; j++) C |= v[r][j] == 'B';
            if(C) cout << 1 << endl;
            else cout << 2 << endl;
        }
    } else cout << -1 << endl;
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
   // freopen("input.txt", "r", stdin);
 
    int tc = 1;
    cin >> tc;
    while(tc--) {
        solve();
    }
}

---

B. Not sitting

Tag : constructive

 

풀이

max(꼭짓점과의 거리)가 최소인 점들을 차례로 채우는 전략이 항상 이득이다.

 

전체코드

By amsminn, contest: Codeforces Round #766 (Div. 2), problem: (B) Not Sitting, Happy New Year!, #, Copy
#include "bits/stdc++.h"
#define endl '\n'
 
using namespace std;
using ll = long long;
 
void solve() {
    int n, m; cin >> n >> m;
    vector<tuple<int, int, int>> v;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            int t = max(abs(1 - i) + abs(1 - j), abs(1 - i) + abs(m - j));
            t = max(t, abs(n - i) + abs(1 - j));
            t = max(t, abs(n - i) + abs(m - j));
            v.push_back({t, i, j});
        }
    }
    sort(v.begin(), v.end());
    for(auto &[x, i, j] : v) cout << x << ' ';
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
//    freopen("input.txt", "r", stdin);
 
    int tc = 1;
    cin >> tc;
    while(tc--) {
        solve();
    }
}

---

C. Not Assigning

Tag : constructive

 

풀이

인접한 간선 한개 또는 두개의 가중치 합이 소수이려면 차수가 3이상인 정점이 존재하면 안된다.

소수 3개 중 2개를 고르는 모든 경우에서 그 합이 소수인 것은 존재하지 않는다.

그래서 선형 트리의 경우만이 답이 존재하는데, 이 때 2와 아무 소수 하나를 골라서 번갈아 배치해주면 된다.

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'
 
using namespace std;
using ll = long long;
 
void solve() {
    int n; cin >> n;
    vector<pair<int, int>> edge(n - 1);
    vector<int> degree(n + 1);
    for(auto &[i, j] : edge) {
        cin >> i >> j;
        degree[i]++;
        degree[j]++;
    }
    for(int i=1; i<=n; i++) {
        if(degree[i] >= 3) {
            cout << -1 << endl;
            return;
        }
    }
    vector<vector<pair<int, int>>> v(n + 1);
    for(int i=0; i<n-1; i++) {
        v[edge[i].first].push_back({edge[i].second, i});
        v[edge[i].second].push_back({edge[i].first, i});
    }
    int w[2] = {2, 3};
    vector<int> ans(n - 1);
    function<void(int, int, int)> dfs = [&](int x, int p, int color)->void{
        for(auto &[i, j] : v[x]) if(i != p) {
            ans[j] = w[color ^ 1];
            dfs(i, x, color ^ 1);
        }
    };
    for(int i=1; i<=n; i++) {
        if(degree[i] == 1) {
            dfs(i, 0, 0);
            break;
        }
    }
    for(int i=0; i<n-1; i++) cout << ans[i] << ' ';
    cout << endl;
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
//    freopen("input.txt", "r", stdin);
 
    int tc = 1;
    cin >> tc;
    while(tc--) {
        solve();
    }
}

---

D. Not Adding

Tag : number theory

 

풀이

부분수열의 gcd 중 k가 존재한다면 k를 만드는 연산이 가능하다.

k마다 k의 배수를 모두 gcd해보고 이것이 k가 된다면 k는 만들 수 있다.

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'
 
using namespace std;
using ll = long long;
 
int n, ans = 0;
int cnt[1010101];
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
//    freopen("input.txt", "r", stdin);
 
    cin >> n; int mx = 0;
    for(int i=1; i<=n; i++) {
        int x; cin >> x;
        mx = max(mx, x);
        cnt[x]++;
    }
    for(int i=1; i<=mx; i++) {
        int g = 0;
        for(int j=i; j<=mx; j+=i) {
            if(cnt[j]) g = gcd(g, j);
        }
        if(g == i) ans++;
    }
    cout << ans - n << endl;
}