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))\ast (t/x)+(t/x)\ast (t/x-1)/2$

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

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

 

 결국, $max(0,(n-(t/x))\ast t/x)+min(n\ast (n-1),(t/x)\ast (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\ast 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;
}