Codeforces Round #727 (Div. 2) ABCD 풀이

 

A. Contest Start

 

문제 및 풀이

 

예외처리를 좀 해줘야하는.. 코드는 간단한 사칙연산 문제입니다.

그럼에도 불구하고.. 저도 끝까지 못맞추고, 1000점 tag가 달린 걸 보니 A번치고 어려운 문제라고 볼 수 있겠네요.

 

문제 요약을 하자면, n명의 사람이 있고 각 사람은 t 기간동안 대회에 참가합니다. 다만 각 사람이 대회를 시작하는 시점이 모두 다른데, 1 ~ n 명의 사람은 각각 x, 2x, ..., nx 에 대회를 시작하게 됩니다.

이 때, 어떤 사람 i가 대회가 끝났을 때 시점으로 대회를 진행중인 또는 대회를 지금 시작할 사람의 수를 "불만족" 이라고 합니다.

모든 참여자의 불만족 합을 구하는 문제입니다.

 

이 문제는 주어지는 변수 n, t, x 에 따라 몇 가지 경우의 수가 있습니다.

 

1. x가 t보다 큰 경우

각 사람의 대회 시작 간격이 대회 기간보다 긴 경우입니다. 이 때는 불만족이 등장할 수 없기 때문에 답은 0입니다.

 

2. n이 (t / x) 보다 크거나, 같은 경우

설명하기 전에 (t/x)가 등장한 이유는 테스트 케이스를 몇 개 그려보면 알 수 있습니다.

 

이런 모양일 경우, 첫 번째 참가자의 불만족은 (t/x)만큼이 됩니다. 하지만 모든 참가자의 불만족이 (t/x)는 아니고,

뒤에 (t/x) 명의 참가자가 없을 경우부터는 (t/x) - 1, (t/x) - 2, ..., 1, 0 으로 불만족이 감소하게 되겠죠.

따라서 정답은 (t / x) * (n - (t / x)) + (1 ~ (t/x - 1) 의 합) 이 됩니다.

 

 

3. n이 (t/x) 보다 작은 경우

문제는 이 부분입니다. 만약 입력으로 n = 9, x = 1, t = 10 이 들어온다면, (t/x)는 과감히 버려야합니다.

 

이 경우 정답은 (n * (n - 1)) / 2 가 됩니다.

 

 

소스 코드(.cpp)

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

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin>>t;
	while(t--) {
		ll n, x, k;
		cin>>n>>x>>k;
		ll ans = 0;
		
		ll cnt = n - (k / x);
		if(cnt < 0){
			cout<<n * (n - 1) / 2 <<"\n";
			continue;
		}
		
		ans += cnt * (k / x);
		
		ll num = (k / x);
		num--;
		
		if(num > 0){
			ans += (num * (num + 1)) / 2;
		}
		
		cout<<ans<<"\n";
	}
	return 0;
}

 

 

B. Love Song

 

문제 및 풀이

 

간단한 부분합 문제입니다.

기존 문자열을 이용해 a는 1번 반복, b는 2번 반복, ... , z는 26번 반복시켜 다른 문자열을 만드는데

문제에서 질문은 기존 문자열의 구간 (l, r) 이 주어지면, 다른 문제열에서 이 구간은 길이가 얼마나 되는가? 를 묻는 문제입니다.

 

우선 입력 조건 중 질문의 수는 max 10만이고, 기존 문자열의 길이도 max 10만입니다.

만약 이 문제를 질문이 들어올 때마다 구간을 찾고, 그 구간을 순회하며 길이를 더해서 구한다고 했을 때 발생할 최대 시간 복잡도는

 O(10만 ^ 2) 으로 시간초과입니다.

 

하지만 이를 부분합으로 생각해보면, 

어떤 구간 (l, r) 의 바뀐 문자열의 길이 합을 구하고 싶을 때

(1, r) 의 바뀐 문자열 길이에 (1, l-1) 의 바뀐 문자열 길이를 빼주면 (l, r) 구간을 바로 구할 수 있습니다. 

 

따라서 미리 psum[i] = (1, i) 까지의 바뀐 문자열 길이를 저장해두면 각 질문마다 O(1) 시간이 걸려 풀 수 있습니다.

 

참고로 psum[i] = psum[i-1] + (s[i] - 'a' + 1) 로 계산한다면 미리 O(n) 시간에 모두 계산 가능합니다.

 

 

소스 코드(.cpp)

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

ll psum[100010];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n,q;
	cin>>n>>q;
	
	string s; cin>>s;
	
	for(int i=1; i<=n; i++){
		psum[i] = psum[i - 1] + s[i-1] - 'a' + 1;
	}
	
	for(int i=0; i<q; i++) {
		int l, r;
		cin>>l >> r;
		cout<<psum[r] - psum[l-1]<<"\n";
	}
	return 0;
}

 

 

C. Stable Groups

 

문제 및 풀이

 

정렬 문제입니다.

어떤 그룹 내에서 모든 인원의 차이가 x 이하라면, 이 그룹은 "stable" 하다고 합니다.

n명의 학생의 번호가 주어졌을 때, 모든 학생을 "stable" 그룹에 넣고, 그 그룹의 수가 최소가 되도록 해야합니다.

다만, k명의 학생을 임의의 번호로 추가할 수 있습니다. 

 

이 문제는 우선, 오름차순 정렬 후 모든 i에 대해서 a[i + 1] - a[i] 의 거리를 구합니다.

만약 이 거리가 x 보다 크다면, a[i], a[i+1]은 각각 다른 그룹이 됩니다.

또한 a[i] ~ a[i + 1] 사이에 학생을 추가해 같은 그룹을 만들 수도 있습니다.

 

따라서 미리 a[i+1] - a[i] > x 를 만족하는 a[i + 1], a[i] 의 차를 일단 배열에 넣어둡니다.

 

모두 순회했다면, x보다 큰 차이를 저장한 배열을 오름차순 정렬 후 짧은 거리부터 필요한 학생을 추가해 그룹을 합쳐줍니다.

만약 거리가 5이고 x가 2라면, 2명을 추가하는 방식으로요 (어떤 그룹인지는 상관없습니다)

이를 k가 0일 때까지 반복하면, 정답은 거리 배열의 크기 + 1 이 됩니다.

 

소스 코드(.cpp)

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

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n, k, x;
	cin>>n>>k>>x;
	
	vector<ll>v(n);
	for(int i=0; i<n; i++) cin>>v[i];
	sort(v.begin(), v.end());
	
	ll groups = 1;
	
	vector<ll>dist;
	
	ll idx = v[0];
	
	for(int i=1; i<n; i++) {
		if(v[i] - idx > x){
			dist.push_back(v[i] - idx);
			groups++;
		}
		idx = v[i];
	}
	
	sort(dist.begin(), dist.end());
	
	//주어진 k로 얼마나 격차를 좁힐 수 있는가?
	ll minus = 0;
	idx = 0;
	while(k > 0 && idx < dist.size()) {
		ll num = dist[idx] / x;
		if(dist[idx] % x == 0) num--;
		
		if(k >= num){
			k -= num;
			minus++;
		}
		else break;
		idx++;
	}
	cout<<groups - minus<<"\n";
	return 0;
}

 

D. PriceFixed

 

문제 및 풀이

 

n개의 상품에 대한 정보 ai, bi가 주어집니다.

ai는 필요한 i번 째 제품 수 (사야 할 개수)

bi는 i번째 제품을 할인 받기 위해 구매해야하는 총 제품의 수 입니다.

 

이 문제도 정렬을 통해 풀 수 있습니다.

 

우선 자명한 사실은 다음과 같습니다.

1. 상품의 가격은 2 또는 1 (할인 받은 경우) 두 가지 밖에 없다.

2. 어떤 상품을 할인 받아 살 수 있다면, 그 상품은 조건 고려 없이 사는 것이 이득이다. (1 조건에 의해 최저 가격)

3. 어떤 상품도 할인 받아 살 수 없다면, 가장 어려운 조건을 가진 상품을 사는 것이 가장 낫다. (bi가 가장 높은 상품)

 

이 사실을 계속 고려해 투 포인터를 이용하면 되는데, 우선 투 포인터를 하기 전에 정렬부터 해야합니다.

정렬 기준은 bi (할인 받기 위한 제품의 수) 로 어떤 차순이든 정렬을 한 후 (내림차순이라 가정)

가장 왼쪽(최대), 오른쪽(최소) 를 포인터로 잡습니다.

 

그 후 위에 쓴 사실을 이용해 투 포인터처럼 left <= right 일 때까지 계속 조건을 돌리면 됩니다.

다만 3번 사실에서 가장 어려운 조건을 가진 상품을 ai만큼 다 사지 않고, 만약 사던 중 "가장 쉬운 조건"을 만족한다면 right 포인터로 넘어가 해당 상품을 싹쓰리해주는 것이 포인트입니다.

 

소스 코드(.cpp)

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

bool check[100010];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin>>n;
	
	vector<pair<ll, ll> >v(n);
	
	for(int i=0; i<n; i++){
		ll ai, bi;
		cin>>ai>>bi;
		v[i] = {bi, ai};
	}
	
	sort(v.begin(), v.end(), greater<pair<ll, ll> >() );
	
	ll items = 0; //현재 구매한 item 수
	int left = 0, right = n - 1;
	
	ll ans = 0;
	
	while(left <= right) {
		//1. 만약 right의 수가 items 보다 작거나 같다면, 모두 사들인다.
		if(v[right].first <= items) {
			ans += v[right].second;
			items += v[right].second;
			right--;
			continue;
		}
		
		//2. 만약 1번 상황이 되지 않는다면, 제 가격에 상품을 산다.
		//2-1. 만약 left의 수를 다 채우기 전에 right의 수보다 같거나 많게 된다면
		if(items + v[left].second > v[right].first) {
			//그 차이만큼만 상품을 구매한 후 right 물품을 모두 구매한다.
			ans += 2 * (v[right].first - items);
			v[left].second -= v[right].first - items;
			items = v[right].first;
			continue;
		}
		//2-2. left의 수를 다 채워야한다면
		items += v[left].second;
		ans += 2 * (v[left].second);
		left++;
	}
	
	cout<<ans<<"\n";
	return 0;
}