[AtCoder] ABC304

A - 3:12

가장 어린 나이를 찾고, 시계방향으로 돌면서 이름을 출력하면 된다.

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#define MINF 0x7f7f7f7f
#define INF 300000000000001
#define MOD 10007
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, ll> pil;
typedef pair<pii, int> piii;
typedef pair<piii, int> piiii;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> plll;
typedef pair<pll, string> plls;
vector<pair<string, int>> v;

void init() {
    int n;
    cin >> n;
    int mini = 1e9;
    int idx;
    for (int i=0; i<n; i++) {
        string s;
        int age;
        cin >> s >> age;
        v.push_back({s, age});
        if (age < mini) {
            mini = age;
            idx = i;
        }
    }
    for (int i=idx; i<n; i++) {
        cout << v[i].X << '\n';
    }
    for (int i=0; i<idx; i++) {
        cout << v[i].X << '\n';
    }
}		

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	init();
}

B - 7:21

N을 입력받고 케이스에 따라 처리하면 되는 문제다.

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#define MINF 0x7f7f7f7f
#define INF 300000000000001
#define MOD 10007
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, ll> pil;
typedef pair<pii, int> piii;
typedef pair<piii, int> piiii;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> plll;
typedef pair<pll, string> plls;
vector<pair<string, int>> v;

void init() {
    int N;
    cin >> N;
    if (N <= 1000 - 1) {
        cout << N;
    } else if (N <= 10000 - 1) {
        cout << (N / 10) * 10;
    } else if (N <= 100000 - 1) {
        cout << (N / 100) * 100;
    } else if (N <= 1000000 - 1) {
        cout << (N / 1000) * 1000;
    } else if (N <= 10000000 - 1) {
        cout << (N / 10000) * 10000;
    } else if (N <= 100000000 - 1) {
        cout << (N / 100000) * 100000;
    } else if (N <= 1000000000 - 1) {
        cout << (N / 1000000) * 1000000;
    }
}		

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	init();
}

C - 16:08

1번 사람이 바이러스가 걸렸을때, 엄청 오랜 시간이 지났을때 바이러스 걸린 사람을 찾는 문제다.
각 사람간 거리가 D 이하이면 바이러스가 옮긴다고 볼 수 있다. 그러므로 거리가 D 이하일 경우의 그래프 탐색을 진행한 후 방문한 사람은 Yes를, 아닌 사람은 No를 출력하면 된다.

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#define MINF 0x7f7f7f7f
#define INF 300000000000001
#define MOD 10007
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, ll> pil;
typedef pair<pii, int> piii;
typedef pair<piii, int> piiii;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> plll;
typedef pair<pll, string> plls;
bool visited[2010] = {false};
vector<int> adj[2010];
vector<pii> v;


void dfs(int curr) {
    for (auto next: adj[curr]) {
        if (visited[next]) continue;
        visited[next] = true;
        dfs(next);
    }
}

void init() {

    int N, D;
    cin >> N >> D;
    for (int i=0; i<N; i++) {
        int x, y;
        cin >> x >> y;
        v.push_back({x, y});
    }
    visited[0] = true;

    bool flag = true;
    
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            if (i == j) continue;
            int dist = pow(v[i].X - v[j].X, 2) + pow(v[i].Y - v[j].Y, 2);
            
            if (D * D < dist) continue;
            adj[i].push_back(j);
            adj[j].push_back(i);
        }
    }
    
    dfs(0);

    for (int i=0; i<N; i++) {
        if (visited[i]) cout << "Yes" << '\n';
        else cout << "No" << '\n';
    }
}		

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	init();
}

D - 업솔빙

[Atcoder] ABC304 :: D - A Piece of Cake

E - 45:23

그래프 G가 주어질때 K개의 [x, y]가 모두 연결되지 않는 그래프를 good 그래프라고 부른다.
이때 Q개의 쿼리가 들어오고 [x, y] 노드를 연결할때, good 그래프를 만족하는 상황인지 구해야 한다.

매번 탐색하는건 당연히 비효율적이니, 노드를 집합의 관점으로 바라보자. 그리고 K개의 관계를 전부 set에 때려박자.
만약 애초부터 good이 안되는 경우라면 무조건 no를 출력하면 되고, good이 될 수도 있다면 Q로 입력받은 [x, y]가 set에 들어있는지 확인해보자. 만약 set에 들어있다면 good 그래프가 아니므로 no를, 없다면 무조건 good 그래프이므로 yes를 출력하면 된다.

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#define MINF 0x7f7f7f7f
#define INF 300000000000001
#define MOD 10007
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, ll> pil;
typedef pair<pii, int> piii;
typedef pair<piii, int> piiii;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> plll;
typedef pair<pll, string> plls;
int par[200010];
int n, m, k, q;
set<pii> st;
vector<int> adj[200010];


int find(int start) {
    if (start == par[start]) return start;
    return par[start] = find(par[start]);
}

void uni(int x, int y) {
    x = find(x);
    y = find(y);
    if (x < y) par[y] = x;
    else par[x] = y;
}

void init() {
    cin >> n >> m;
    for (int i=0; i<200010; i++) par[i] = i;
    for (int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        uni(x, y);
    }

    bool flag = false;
    cin >> k;
    for (int i=0; i<k; i++) {
        int x, y;
        cin >> x >> y;
        x = find(x);
        y = find(y);
        st.insert({min(x, y), max(x, y)});

        if (x == y) flag = true;
    }

    cin >> q;
    for (int i=0; i<q; i++) {
        int x, y;
        cin >> x >> y;
        x = find(x);
        y = find(y);
        if (flag) cout << "No" << '\n';
        else {
            if (st.find({min(x, y), max(x, y)}) != st.end()) {
                cout << "No" << '\n';
            } else {
                cout << "Yes" << '\n';
            }
        }
    }
}		

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	init();
}