Round #727

A. Contest Start

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

Problem - A - Codeforces

까다로웠던 A문제. 

수평선에\( 0, x, 2x, 3x, ... nx\) 에 사람들이 서있다고 미리 가정하자.

\([0, t]\)안에 x가 몇명이 있을까 ? == t / x

그렇다면 어떤 사람의 좌표\((a)\)에서 \((a + t)\)까지, 즉 \([a, a + t]\)안에 항상 \( t / x\)명의 사람이 존재? 답은 X.

제일 끝에 있는 사람\((nx)\)부터 생각해보면 t칸안에 있는 사람 0명

\((n - 1)x\)부터 t칸안에 있는 사람 1명

\((n - 2)x)\)부터 t칸안에 있는 사람 2명 , ...

 

 다시 표현해보면,

\(0\) - \(t / x\)

\(x\) - \(t / x\)

\(2x\) - \(t / x\)

...

\((n - 2)x\) - \(2\)

\((n - 1)x\) - \(2\)

\(nx\) - \(2\)

 

\(0\)부터 \((n - ( t / x) - 1)x\)에 있는 사람까지는 \(t / x\)명이 아직 할 일을 끝마치지 못한 상태

+

\((n - (t / x))x\)부터 \(nx\)까지 \((t / x - 1), (t / x - 2) , ... 1, 0\)명이 할 일을 끝마치지 못한 상태

\(= (n - (t / x)) * ( t / x ) + ( t / x ) * ( t / x - 1) / 2 \)

가 답이 되는 줄 알고 제출했다가 못풀었다.

 한가지 예외가 있는데, \(n < t / x\)가 되는 경우에는 \(n, n - 1, ... , 1\)을 계산해주어야한다.

 

 결국, \( max(0, (n - (t / x)) * t / x) + min( n * ( n - 1), ( t / x ) * ( t / x - 1)) / 2\)가 답이 된다.

#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--) {
		ll n, x, t;
		cin >> n >> x >> t;
		ll cnt = t / x;
		ll ans = min( n * (n - 1), (cnt) * (cnt - 1)) / 2 + max(0LL, cnt * (n - cnt));
		
		cout << ans << '\n';
	}
	return 0;
}

---

B. Love Song

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

Problem - B - Codeforces

 구간 합으로 해결했다.

 각 알파벳 별로 \( [l, r]\)안에 몇 개가 존재하는지 구간 합을 이용하여 \(O(1)\)에 찾아주면 나머지 계산은 쉽게 할 수 있다. 

 구간 합을 구하는 과정의 시간 복잡도 \(O(n)\)

 구간 합을 통해 q개의 결과를 구하는 시간 복잡도 \(O(1 * q)\)

 n과 q의 범위가 같기 때문에 시간 복잡도는 \(O(n + q) = 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 dp[27][100001] = { 0 , };

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, q;
	string str;
	cin >> n >> q >> str;

	// 구간 합
	for (int i = 1; i <= n; i++) dp[str[i - 1] - 'a' + 1][i]++;
	for (int i = 1; i <= 26; i++) {
		for (int j = 1; j <= n; j++) {
			if(dp[i][j] == 1) dp[i][j] = dp[i][j - 1] + 1;
			else dp[i][j] = dp[i][j - 1];
		}
	}

	for (int i = 0; i < q; i++) {
		int l, r;
		cin >> l >> r;
		int ans = 0;
		for (int alp = 1; alp <= 26; alp++) {
			ans += (dp[alp][r] - dp[alp][l - 1]) * alp;
		}
		cout << ans << '\n';
	}
	return 0;
}

---

C. Stable Groups

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

Problem - C - Codeforces

 

 두 그룹이 있을 때 몇 명의 학생을 추가해야 한 그룹으로 만들 수 있을까 ? 

 작은 수가 모인 그룹 1, 큰 수가 모인 그룹 2가 있다고 가정하자.

 두 그룹을 묶으려면 그룹 1의 가장 큰 수와 그룹 2의 가장 작은 수의 차에 따라 필요한 학생의 수가 결정된다.

 두 수의 차를 \(dif\)라고 하면

\(dif <= x \)일 땐, 필요한 학생 수 0

\(x < dif <= 2x \)일 땐, 필요한 학생 수 1

\(2x < dif <= 3x \)일 땐, 필요한 학생 수 2

인 것으로 보아 필요한 학생 수는 \(\lceil\frac{dif}{x}\rceil - 1\)임을 알 수 있다.

 

 결국 우리가 구해야 할 것은 두 그룹을 묶는데 필요한 학생 수를 구하고, 주어진 \(k\)명의 학생으로 greedy하게 최대한 많은 그룹을 합쳐주면 된다. 

 

 나의 풀이법은 처음 \(n\)개의 학생들이 각자 한 그룹을 유지한다고 가정하였다. (\(n\)개의 그룹으로 시작)

 이후 정렬된 학생들의 차를 구하여 배열\(dif\)에 저장하고 \(dif\)를 오름차순으로 정렬시켜준다. (이렇게 되면 배열 \(dif\)의 원소의 개수는 \(i - 1\)이 된다.)

 

 이제 \(dif\)안에는 두 그룹을 묶는데 필요한 학생의 수가 오름차순으로 정렬되어 저장되어있고, 우리는 \(k\)가 양수인동안 greedy하게 \(k\)를 사용하여 두 그룹을 묶어주면 \(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; }
 
ll a[200001] = { 0, };
ll dif[200001] = { 0, };
 
int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	ll n, k, x, tmp;
	cin >> n >> k >> x;
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n);
	for (int i = 1; i < n; i++) dif[i - 1] = max(0LL ,(a[i] - a[i - 1] - 1LL) / x);
	sort(dif, dif + n - 1);
 
	ll ans = n;
	for (int i = 0; i < n - 1; i++) {
		if (k >= dif[i]) {
			k -= dif[i];
			ans--;
		}
	}
 
	cout << ans << '\n';

	return 0;
}

---

 

D. PriceFixed

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

Problem - D - Codeforces

 

 핵심은 할인을 최대한 많이 받으면서 물건을 구매해야한다. 그렇다면 할인받는데 필요한 구매 개수가 각각 2, 8개인 물건이 있다고 가정하자. 어떤 물건부터 사는게 할인에 유리할까 ? 당연히 8개를 사야 할인 받을 수 있는 물건을 먼저 사고 2개 짜리를 할인 받는게 유리할 것이다. 이 아이디어가 맞다면 투 포인터로 해결할 수 있을 것이다.

 

 할인받는데 필요한 구매 개수를 \(b\)라고 하고, \(b\)를 기준으로 오름차순 정렬을 하자.

 포인터 하나는 배열의 가장 앞, 다른 하나는 가장 뒤로 설정하고 while문으로 출발해보자.

 while문에서 할 일은 간단하다. 앞에 있는 상품을 할인 받을 수 있을 만큼 뒤에서부터 물건을 구매한다. 뒤쪽 물건 구매가 끝나면, 앞쪽으로 넘어와서 할인받을 수 있는 물건들은 모조리 다 사버린다. 더이상 할인을 받을 수 없다면, while문 처음으로 돌아가 같은 과정을 반복한다. 

 

 투포인터로 해결하기 때문에 시간복잡도는 \(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; }

pair<ll, ll> p[100001] = { {0, 0}, };


int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> p[i].second >> p[i].first;
	sort(p, p + n);
    
	int start = 0, end = n - 1;
	ll buy = 0; // 지금까지 구매한 물건의 수
	ll ans = 0;
	while (start <= end) {
		ll least = p[start].first; // 이만큼 사야한다.
		for (end; end >= start; end--) {
			if (buy + p[end].second < least) { // p[end]에 있는 물건을 다 사야하는 경우
				ans += 2 * p[end].second;
				buy += p[end].second;
				p[end].second = 0;
			}
			else { // p[end]에 있는 물건 몇개만 사도 되는 경우
				p[end].second -= (least - buy);
				ans += 2 * (least - buy);
				buy = least;
				break; // 아직 p[end]에 있는 물건을 다 사지 않았기 때문에
                		// break문을 통해 end 유지
			}
		}


		while (start <= end && p[start].first <= buy) { // 할인 받을 수 있는동안
			ans += p[start].second;
			buy += p[start].second;
			start++;
		}
	}
	cout << ans;
	return 0;
}