Codeforces Round #628 (Div. 2)

by Kimcoding on 2020-03-16 17:34

in Codeforces

D번이 아쉽네요…

아직 왜 틀리는지 몰라서 추후에 풀게 되면 게시글 마지막에 추가하겠습니다

왜 틀리지…ㅠㅠ

A. EhAb AnD gCd

A - EhAb AnD gCd

알고리즘

수학

GCD + LCM을 구하는 문제입니다.

GCD, LCM을 구할 필요없이 1과 X의 GCD는 1이고, LCM은 X입니다.

그러므로 입력 X에 대해서 1과 X-1의 GCD + LCM = X 입니다.

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define vi vector <int>
#define vvi vector <vi>
#define ll long long
#define vll vector <ll>
#define vvl vector <vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ep emplace
#define fs first
#define sd second
#define mod 998244353
#define EPS 1e-9
using namespace std;

int main() {
	FIO;
	int t; cin >> t; while (t--) {
		int x; cin >> x;
		cout << 1 << ' ' << x - 1 << '\n';
	}
	return 0;
}

B. CopyCopyCopyCopyCopy

B - CopyCopyCopyCopyCopy

알고리즘

해싱
구현

입력받은 배열을 N번 뒤에 붙일수 있기 때문에

입력받은 배열의 숫자들을 다 부분 수열에 추가할 수 있지만 중복제거를 해야합니다.

중복 제거를 하는 방법은 많겠지만 숫자 범위가 1~10억이므로 map을 이용하여 해싱을 했습니다.

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define vi vector <int>
#define vvi vector <vi>
#define ll long long
#define vll vector <ll>
#define vvl vector <vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ep emplace
#define fs first
#define sd second
#define mod 998244353
#define EPS 1e-9
using namespace std;

int main() {
	FIO;
	int t; cin >> t; while (t--) {
		int n; cin >> n;
		map <int, int> m;
		FOR(i, 1, n) {
			int x; cin >> x;
			m[x]++;
		}
		cout << (int)m.size() << '\n';
	}
	return 0;
}

C. Ehab and Path-etic MEXs

C - Ehab and Path-etic MEXs

알고리즘

트리
그리디

리프 노드와 이어지는 간선에 0, 1, 2를 배치하게 되면 모든 경로는 리프 노드 중 두 개만을 포함할 수 있기 때문에 MEX(a,b)가 0,1,2 중 하나의 값이 나옵니다.

그러므로 리프노드와 이어지는 간선에 0부터 차례대로 배치하고 나머지는 아무거나 배치해도 MEX는 0,1,2 중에 나오기 때문에 답이 될 수 있습니다.

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define vi vector <int>
#define vvi vector <vi>
#define ll long long
#define vll vector <ll>
#define vvl vector <vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ep emplace
#define fs first
#define sd second
#define mod 998244353
#define EPS 1e-9
using namespace std;

int main() {
    FIO;
    int n; cin >> n;
    vi in(n + 1), ans(n + 1, -1);
    vector <pii> v(n + 1);
    FOR(i,1,n - 1){
        int a, b; cin >> a >> b;
        v[i] = {a,b};
        in[a]++, in[b]++;
    }
    int cnt = 0;
    FOR(i,1,n - 1){
        if(in[v[i].fs] == 1 || in[v[i].sd] == 1)
            ans[i] = cnt++;
    }

    FOR(i,1,n - 1)
        cout << (ans[i] != -1 ? ans[i] : cnt++) << '\n';
    return 0;
}