Round #725 (Div. 3)

A. Stone Game

https://codeforces.com/contest/1538/problem/A

Problem - A - Codeforces

관심있게 봐야하는건 1과 n의 위치이다. 

부수는 방법은 세가지

1) 왼쪽부터 가장 먼 1 또는 n까지

2) 오른쪽부터 가장 먼 1 또는 n까지

3) 왼쪽부터 제일 가까운 1 또는 n까지 + 오른쪽부터 제일 가까운 1 또는 n까지

위 세 가지 중 하나가 답이 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 2147483647;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int a[101] = { 0, };

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		int MAX = -1, MIN = 101;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			if (a[i] == 1) MIN = i;
			else if (a[i] == n) MAX = i;
		}
		if (MIN > MAX) swap(MIN, MAX);

		cout << min({MAX, (n - MIN + 1), MIN + (n - MAX + 1)}) << '\n';
	}
	return 0;
}

---

B. Friends and Candies

https://codeforces.com/contest/1538/problem/B

Problem - B - Codeforces

캔디를 정확하게 나눠야 하므로 캔디의 합이 n으로 나누어 떨어지는지 확인해준다.

나누어 떨어진다면 평균보다 높은 것의 개수만 세주면 된다.

시간 복잡도는 \(O(n)\)

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int a[200001] = { 0, };

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		int ans = n;
		ll sum = 0;

		for (int i = 0; i < n; i++) {
			cin >> a[i];
			sum += a[i];
		}
		if (sum % n != 0) {
			cout << -1 << '\n';
			continue;
		}
	    for(int i = 0 ; i < n; i++) if(a[i] <= sum / n) ans--; // n에서 평균보다 작거나 같은 것을 빼준다
		cout << ans << '\n';
	}
	return 0;
}

---

C. Number of Pairs

https://codeforces.com/contest/1538/problem/C

Problem - C - Codeforces

 시간 복잡도가 \(O(n^2)\)이면 TLE에 걸리게 된다.

 시간 복잡도를 줄이기 위해 이분 탐색을 사용한다. 이분 탐색을 위해 배열을 sort해준 후, lower_bound와 upper_bound를 이용해 답을 구해주었다.

 

 찾아야하는 조건을 \(a[i]\)를 기준으로 바꿔보면 \(a[j]\)는 \(l - a[i] <= a[j] <= r - a[i]\)를 만족시키는 \(a[j]\)를 찾아주면된다.

 

 따라서 \(i < j\)임을 고려했을 때, \(a[i + 1], a[i+2], ... , a[n]\) 중 에서 \(l - a[i] <= a[j] <= r - a[i]\)를 만족시키는 가장 작은 인덱스를 lower_bound를 통해 구해주고(= low), upper_bound를 통해 \(r - a[i]\)를 초과하는 수 중 가장 작은 인덱스(=high)를 구해주자. 

 

 결국 답은 \(i, low <= j < high)\)를 만족시켜야 하기 때문에 모든 \(i\)에 대해서 (high - low)구해서 합해주면 된다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

ll num[200001] = { 0, };

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int T;
	cin >> T;
	while (T--) {
		ll n, l, r;
		ll ans = 0;
		cin >> n >> l >> r;
		for (int i = 0; i < n; i++) {
			cin >> num[i];
		}
		sort(num, num + n);
		for (int i = 0; num[i] < r && i < n; i++) {
			int low = lower_bound(num + i + 1, num + n, max(0LL, l - num[i])) - num;
			int high = upper_bound(num + i + 1, num + n, r - num[i]) - num;

			ans += (high * 1LL - low);
		}

		cout << ans << '\n';
	}
	return 0;
}

---

D. Another Problem About Dividing Numbers

https://codeforces.com/contest/1538/problem/D

Problem - D - Codeforces

두 수 \(a, b\)를 소인수분해하여 몇 개의 소수로 이루어져 있는지 확인하는게 키워드다.

\(k\)가 소수의 개수 합보다 작거나 같으면 항상 k번 만에 두 수를 같게 만들 수 있다.

단, \(k\)가 1일 때는 예외적으로 \(a, b\)가 서로 다른 수이면서 배수 관계인지 확인해주어야한다.

\(k\)가 1일 땐 서로 다르면서 배수 관계일 때만 같게 만들 수 있기 때문.

 

참고로 소인수 분해할 때

int num, div = 2;
while(num != 1){
	if(num % div == 0) num /= div;
    else{
    	if(div % 2 == 0) div++;
        else div += 2;
    }
}

이렇게 구하면 TLE에 걸린다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int T;
	cin >> T;
	while (T--) {
		int a, b, k;
		cin >> a >> b >> k;
		
		ll cnt = 0;

		int cp = a;
		for (int i = 2; i * i  <= cp; ++i) {
			while (cp % i == 0) {
				cp /= i;
				cnt++;
			}
		}
		if (cp > 1) cnt++;

		cp = b;
		for (int i = 2; i * i <= cp; ++i) {
			while (cp % i == 0) {
				cp /= i;
				cnt++;
			}
		}
		if (cp > 1) cnt++;
		
		if (k == 1) {
			if (a != b && ((a % b == 0) || (b % a == 0))) cout << "YES\n";
			else cout << "NO\n";
		}
		else if (k <= cnt) cout << "YES\n";
		else cout << "NO\n";

	}
	return 0;
}

---