Codeforces Round #694 (Div. 2)

문제 링크

codeforces.com/contest/1471

 

 

A. Strange Partition

 

문제

n개의 정수 배열 a와 정수 x가 주어진다.

원하는 만큼 배열 안에 인접한 원소 두 개를 합쳐 하나로 만들 수 있다. 만약 이 작업을 하면 배열의 원소는 -1씩 줄어든다.

배열의 아름다움이란 배열의 각 원소를 주어진 정수 x로 나눈 후, 올림 한 값들을 더하여 나타내는데,

적당히 작업을 하여, 배열의 아름다움의 최소값과 최댓값을 나타내라.

 

풀이 1

나누고 몫을 올림 한다는 것은 원소가 많을 때 이득입니다.

만약 배열 내 원소 k가 있다고 하면, k는 두 가지 경우로 나뉩니다.

 

1) k가 x로 나누어 떨어지는 경우 : 이 경우 합치나 더하나 차이가 없습니다.

2) k가 x로 나누어 떨어지지 않는 경우 : 이 경우 나머지가 존재하여 올림이 가능해집니다. 따라서 (k / x)의 결과에 +1을 더한 값이 해당 원소의 아름다움입니다.

 

그런데, 배열의 원소가 여러 개일 때 2번의 케이스의 경우는 나머지가 상쇄될 수 있습니다.

이 문제에서는 반드시 나머지가 나오는 원소를 x로 나눠야 값이 커지는데, 나머지가 없어져버리면 손해인 것이죠.

 

따라서 최솟값은 그냥 모든 배열의 원소를 더 하고, x로 나누고 올림 한 값

최댓값은 각각의 원소를 x로 나누고 올림 하여 더한 값이 됩니다.

소스 코드 1

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--)
	{
		int n; cin >> n;
		int x; cin >> x;
		vector<int>v(n);
		for (int i = 0; i < n; i++) cin >> v[i];
		ll sum = 0;
		for (int i = 0; i < n; i++) sum += v[i];
		ll min_ans = 0, max_ans = 0;
		if (sum % x == 0) min_ans = sum / x;
		else min_ans = (sum / x) + 1;
 
		for (int i = 0; i < n; i++)
		{
			if (v[i] % x == 0) max_ans += (v[i] / x);
			else max_ans += (v[i] / x) + 1;
		}
		cout << min_ans << " " << max_ans << "\n";
	}
	return 0;
}

 

B. Strange List

 

문제

n개의 정수를 담은 배열 a와 정수 x가 주어집니다.

특정 배열 원소 q에 대해서, 만약 q가 x로 나누어 떨어지면, (q/x) 값을 가진 x개의 복사본을 배열 끝에 추가하고

q를 다음 칸으로 옮깁니다. 만약 q가 x로 나누어 떨어지지 않는 순간, 로봇은 멈추게 됩니다.

로봇이 멈출 때, 배열의 총합을 구하시오

 

풀이 1

핵심은 크게 두 가지입니다.

첫 번째, q가 x로 나누어 떨어질 때, 복사본을 추가하는데 그 복사본의 합은 q값과 같습니다.

두 번째, 복사본을 추가할 때, 배열의 순서는 크게 달라지지 않습니다. 만약 a의 복사본을 a`이라 할 때

배열 [a, b, c]가 모두 복사될 때 배열은 [a, b, c, a`,b`,c`]로, 기존 배열의 순서가 바뀌진 않습니다.

 

이제 로봇이 멈출 타이밍을 계산해야 합니다.

로봇이 멈출 타이밍은 q가 x로 나누어 떨어지지 않을 때이므로, q가 x로 나누어 떨어지지 않을 때를 구하기 위해서는 배열의 모든 원소에 대해 더 이상 나누어 떨어지지 않을 때까지 x를 몇 번 나눌 수 있는지 계산하면 됩니다.

만약 예제 [4,6,8,2]가 있을 때 위와 같은 계산을 하면 [2, 1, 3, 1]이 됩니다. (2*2, 2*3, 2*2*2, 2)

 

여기서 가장 작은 원소는 1입니다. 아까 두 번째 핵심에 의해 배열의 순서가 달라지지 않기 때문에 로봇이 그대로 움직이면 6과 관련된 원소에서 멈추게 될 것입니다.

 

그런데, 원소가 1이므로 한 바퀴는 돌게 됩니다. 한 바퀴를 돈 다는 의미는 첫 번째 핵심에 의해서 배열의 합이 x2 된다는 의미로 이어지게 됩니다.

따라서 한 바퀴를 돈 후 배열의 총합은 40이 됩니다.

 

여기서 멈춰야 할 부분은 "6"과 연관이 있기 때문에, "6" 앞 원소들은 또 한 바퀴를 돈 셈이 됩니다.

따라서 앞 원소들을 더하면 총합은 44가 됩니다.

소스 코드 1

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int div_cnt[100010];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--)
	{
		memset(div_cnt, 0, sizeof(div_cnt));
		ll n, x;
		cin >> n >> x;
		vector<ll>v(n);
		ll sum = 0;
		for (int i = 0; i < n; i++) cin >> v[i];
		for (int i = 0; i < n; i++) {
			int tmp = 0;
			ll num = v[i];
			sum += v[i];
			while (num % x == 0) {
				tmp++;
				num /= x;
			}
			div_cnt[i] = tmp;
		}
		int min_idx = 0, min_cnt = 987654321;
		for (int i = 0; i < n; i++) {
			if (div_cnt[i] < min_cnt) {
				min_cnt = div_cnt[i];
				min_idx = i;
			}
		}
		ll ans = 0;
		ans += (sum * (min_cnt + 1));
		for (int i = 0; i < min_idx; i++) ans += v[i];
		cout << ans << "\n";
	}
	return 0;
}

 

C. Strange Birthday Party

 

문제

n명의 사람들에게 선물을 모두 나누어주고자 합니다.

사람들의 고유 번호는 k, 선물의 고유 번호는 c이고, 선물은 총 m개로 이루어져 있습니다.

이때 선물을 나누어 주는 방법은 두 가지가 있습니다. 

1. i번째 사람은 고유 번호 k 이하 인덱스의 선물을 가져갈 수 있습니다.

2. 선물 대신 현찰을 줄 수도 있습니다..! (선물 배열의 인덱스 k 값)

 

풀이 1

그리디 하게 풀긴 했는데 제대로 증명은 못하겠네요.. 풀이 과정을 설명드리면

i번째 사람이 가질 수 있는 선물은 c[k] (현금) or k-th 이하의 c배열의 원소 값이 됩니다.

이때 주목할 것은, 선물은 중복으로 가져갈 수 없지만, 현금은 중복으로 가져갈 수 있다는 점입니다.

즉, 선물은 유한하기 때문에 c[k]값이 큰 사람은 선물을 가져가는 편이 이득일 확률이 높습니다.

 

따라서 각 사람들마다 (c[k], k) 로 저장을 한 후, 내림차순으로 정렬해줍니다.

이때, k는 오름차순으로 정렬하는 것이 유리한데, 만약 c[k]가 같은 사람 a, b가 있을 때 순서가

(c[k], 2) (c[k], 1) 로 내림차순이면, 첫 번째 사람이 1을 가져가면 두 번째 사람은 선물을 가져가지 못하기 때문입니다.

 

따라서 이 과정을 그리디 하게 선물을 가져갈지, 현금을 가져갈 지 선택해주면 됩니다. 이때 c는 오름차순으로 입력되어서 주기 때문에 귀찮은 작업을 할 필요가 없어지겠네요.

소스 코드 1

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
bool comp(pair<int, int>i, pair<int, int>j) {
	if (i.first == j.first) {
		return i.second < j.second;
	}
	return i.first > j.first;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--)
	{
		int n, m;
		cin >> n >> m;
		vector<int>k(n), c(m);
		for (int i = 0; i < n; i++) {
			int tmp;
			cin >> tmp;
			k[i] = tmp - 1;
		}
		for (int i = 0; i < m; i++) cin >> c[i];
		vector<pair<int, int> >v(n);
		for (int i = 0; i < n; i++) {
			v[i] = { c[k[i]], k[i] };
		}
		sort(v.begin(), v.end(), comp);
		int ptr = 0;
		ll sum = 0;
 
		for (int i = 0; i < n; i++) {
			if (ptr >= n) {
				sum += v[i].first;
				continue;
			}
			if (ptr <= v[i].second) {
				if (c[ptr] < v[i].first) {
					sum += c[ptr];
					ptr++;
				}
				else {
					sum += v[i].first;
				}
			}
			else {
				sum += v[i].first;
			}
		}
		cout << sum << "\n";
	}
	return 0;
}