Atcoder Beginner Contest 206 (ABC 206) 풀이

 

 

블루가 되었다

 

 

A. Maxi-Buying

 

단순 계산 문제이다. 

N을 입력받고, 1.08*N을 정수단위로 올림 했을 때 206과 대소 비교하는 문제이다. 

 

#include<bits/stdc++.h>
using namespace std;
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	double n; cin >> n;
	n *= 1.08;
	int ans = (int)n;
	if (ans == 206) cout << "so-so";
	else if (ans < 206) cout << "Yay!";
	else cout << ":(";
}

 

 

B. Savings

 

1부터 k까지의 합이 N이상이 되는 가장 작은 k를 구하는 문제이다.

N이 최대 10억이므로 k = 1부터 확인하면서 k*(k+1)/2 ≥ N인지 확인하면 된다.

 

#include<bits/stdc++.h>
using namespace std;
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n; cin >> n;
	for (int i = 1; ; i++) {
		if (i * (i + 1) / 2 >= n) {
			cout << i;
			break;
		}
	}
}

 

 

C. Swappable

 

N개의 원소로 이루어진 수열 A가 주어질 때, A[i] != A[j]인 (i, j) 쌍의 개수를 구하는 문제이다. 

map을 이용하여 같은 값을 갖는 원소의 개수를 저장한 뒤, 현재 값의 개수와 나머지 원소의 개수의 곱의 합을 구하면 된다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n; cin >> n;
	map<int, int> mp;
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		mp[a]++;
	}
	ll ans = 0;
	for (auto [a, b] : mp) {
		ans += 1LL * b * (n - b);
	}
	cout << ans / 2;
}

 

 

D. KAIBUNsyo

 

N개의 원소로 이루어진 수열 A가 주어질 때, A를 팰린드롬으로 만들기 위한 최소 연산 횟수를 구하는 문제이다.

연산은 다음과 같다. "수열에 존재하는 모든 x 값을 y로 바꾼다" 

양끝에서부터 A[i]와 A[n+1-i]가 일치하는지를 확인하고, 일치하지 않는다면 반드시 둘 중 하나는 변경시켜주어야 한다. 

이때, 어느것으로 바꿔주어도 동일한 이득을 취할 수 있다. 

현재 값이 어떤 값으로 변경되었는지는 union-find를 이용하여 빠르게 찾을 수 있다. 

 

#include<bits/stdc++.h>
using namespace std;

int a[202020];
int P[202020];
int find(int a) {
	return P[a] == a ? a : P[a] = find(P[a]);
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n; cin >> n;
	for (int i = 1; i <= 200000; i++) P[i] = i;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int ans = 0;
	for (int i = 1; i <= n / 2; i++) {
		int k1 = find(a[i]);
		int k2 = find(a[n + 1 - i]);
		if (k1 != k2) {
			P[k1] = k2;
			ans++;
		}
	}
	cout << ans;
}

 

 

E. Divide Both

 

L, R (L ≤ R)이 주어질 때, L이상 R 이하인 x, y에 대해서, gcd(x, y) ≠ 1, x, y 를 만족하는 x, y 쌍의 수를 구하는 문제이다. 

조금 복잡하게 풀었는데, 먼저 i = L ~ R을 순서대로 보면서 i보다 크고, i와 서로소가 아니면서 i의 배수가 아닌 수의 개수를 구하는 방식이다. 

i를 소인수분해하여 i에 포함된 소인수만 모아서 집합을 만든 뒤, '집합의 부분집합으로 만들 수 있는 모든 곱의 배수'들의 개수를 구한다. 

예를 들어 i = 60이면, 60 = 2*2*3*5이므로 {2, 3, 5}에서 i+1 ~ R범위에 있는 2의 배수, 3의 배수, 5의 배수의 개수를 더하고, 2*3의 배수, 3*5의 배수, 2*5의 배수를 빼고, 2*3*5의 배수는 더하는 방식으로 포함 배제의 원리를 이용한다. 

 

모든 부분집합을 구하는 방식은 비트마스킹을 이용한다. 

 

#include<bits/stdc++.h>
#define sz(x) (int)x.size()
#define pb push_back
using namespace std;
using ll = long long;

int prime[1001];
vector<int> P;
int l, r;
ll sol(vector<int>& fac, int i) {
	ll res = 0;
	for (int sub = (1 << sz(fac)) - 1; sub; sub = (sub - 1) & (1 << (sz(fac))) - 1) {
		int val = 1;
		int cnt = 0;
		for (int j = 0; j < sz(fac); j++) {
			if ((1 << j) & sub) {
				val *= fac[j];
				cnt++;
			}
		}
		if (val != 1) {
			int k = r / val - i / val;
			if (cnt % 2) res += k;
			else res -= k;
		}
	}
	return res;
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	for (int i = 2; i <= 1000; i++) {
		if (prime[i] == 0) {
			P.pb(i);
			for (int j = 2; j * i <= 1000; j++) {
				prime[i * j] = 1;
			}
		}
	}
	ll ans = 0;
	cin >> l >> r;
	for (int i = max(2, l); i < r; i++) {
		int k = i;
		vector<int> fac;
		int idx = 0;
		for (int i = 0; i < sz(P); i++) {
			if (k == 1) break;
			if (k % P[i] == 0) {
				fac.pb(P[i]);
				while (k % P[i] == 0) k /= P[i];
			}
		}
		if (k > 1) fac.pb(k);
		ans += sol(fac, i);
		ans -= r / i - 1;
	}
	cout << ans * 2;
}

 

 

F. Interval Game 2

 

대회중에 풀지 못한 문제이다. 딱 봐도 게임이론 문제 같은데, 아직 스프라그 그런디 정리에 대해서 잘 숙지되지 않아서 문제 읽자마자 포기했다. 

우선 에디토리얼을 따라서 코드를 한번 작성해봤는데, 그런디 정리에 대해서 공부할 필요가 있을 것 같다. 

 

#include<bits/stdc++.h>
#define ini(x, y) memset(x, y, sizeof(x));
using namespace std;

int n, L[101], R[101], dp[101][101];
int grundy(int l, int r) {
	if (l >= r) return 0;
	int& ret = dp[l][r];
	if (ret != -1) return ret;
	vector<bool> chk(101);
	for (int i = 1; i <= n; i++) {
		if (L[i] >= l && R[i] <= r) chk[grundy(l, L[i]) ^ grundy(R[i], r)] = true;
	}
	for (int i = 0; ; i++) {
		if (!chk[i]) {
			ret = i;
			break;
		}
	}
	return ret;
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> L[i] >> R[i];
		}
		ini(dp, -1);
		if (grundy(1, 100)) cout << "Alice\n";
		else cout << "Bob\n";
	}
}