pushback

A. Contest Start

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

까다로웠던 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

 구간 합으로 해결했다.

 각 알파벳 별로 \( [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

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

 작은 수가 모인 그룹 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

 핵심은 할인을 최대한 많이 받으면서 물건을 구매해야한다. 그렇다면 할인받는데 필요한 구매 개수가 각각 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;
}

A. Stone Game

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

관심있게 봐야하는건 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

캔디를 정확하게 나눠야 하므로 캔디의 합이 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

 시간 복잡도가 \(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

두 수 \(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;
}

A. Alexey and Train

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

 역을 떠나는 조건을 잘못 읽어서 4번의 WA를 받았다...

 문제에서 원하는대로 구현하면 된다. 

 주의할 점으로 떠나는 시간이 (현재 시간 + \(\left \lceil \frac{(b_i - a_i)}{2} \right \rceil\)) 이 \(b_i\)보다 작다면 출발을 못하기 때문에, 현재시간을 \(b_i\)로 설정해준다.

#include <bits/stdc++.h>

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

vector<pair<int, int>> train(100001);
vector<int> extra(100001);

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;
		for (int i = 1; i <= n; i++) cin >> train[i].first >> train[i].second;
		for (int i = 1; i <= n; i++) cin >> extra[i];
        
		int time = 0; // 현재 시간
        
		for (int i = 1; i <= n; i++) {
			time += (train[i].first - train[i - 1].second + extra[i]); // 역에 도착하는 시간
            
			if (i != n) { // 마지막 역이 아니라면 떠나는 시간을 정해야함.
				time += (int)round(((double)train[i].second - (double)train[i].first) / 2);
				time = max(time, train[i].second);
			}
		}
		cout << time << '\n';

	}

	return 0;
}

B. Napoleon Cake

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

 stack을 이용하여 \(log n\)에 해결했다.

 \(a\)층\((1 <= a <= n)\)에서 \(b\)만큼의 레이어가 drench됐다면 \((a - b + 1)\)층까지 drench됐다는 의미이다.따라서 현재 \(a\)층이고, \(b\)만큼 drench됐다면 stack의 top이 \((a - b)\)보다 크다면 계속 pop해준다. ( == drench되는 층들을 stack에서 제거하는 과정)

 결국, stack에 남아있는 레이어 번호는 drench되지 않은 레이어이다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;
vector<bool> isNotDrenched;
int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	stack<int> stk;
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		isNotDrenched.clear();
		isNotDrenched.resize(n + 1);
		for (int i = 1; i <= n; i++) {
			stk.push(i);
			int level;
			cin >> level;
			while (!stk.empty() && stk.top() > (i - level))
				stk.pop();
		}
		while (!stk.empty()) {
			isNotDrenched[stk.top()] = true;
			stk.pop();
		}
		for (int i = 1; i <= n; i++)
			if (isNotDrenched[i]) cout << 0 << ' ';
			else cout << 1 << ' ';
		cout << '\n';

	}
	
	return 0;
}

C. Going Home

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

 \(a[i] + a[j], ( i != j )\) 의 최댓값인 5백만이란 큰 숫자에 겁 먹지말자. (난 겁 먹었었다.)

 단순히 \(a[i] + a[j]\)를 index로 하는 벡터에 (i , j) 한 쌍을 push_back해주고 해당 인덱스에 여러 쌍이 존재한다면, \(x \neq  y \neq  z \neq  w\)를 만족하는 두 쌍을 찾으면 된다. 여기서 Time Limit이 뜨지 않을까라는 의구심이 든다.

 정답은 "Time Limit은 뜨지 않는다" 이다. 왜 그런지에 대해 araboja.

 \(a[i] + a[j]\)를 index로 하고 \( {i, j} \)를 저장하는 벡터를 sum이라고 해보자.

 모든 쌍 안에 두 index는 서로 다르다. 그렇다면 \(sum[a[i] + a[j]]\)에 두 쌍의 index에서 우리가 원하는 답이 안되는 경우는 \( (x, y_1), (x, y_2) , (x \neq  y_1 \neq  y_2)\)이다. 너무 슬픈 상황이다. 여기서 \(x\)를 갖는 한 쌍이 추가됐다고 생각해보자. 

\( (x, y_1), (x, y_2) , (x, y_3)\). 상황은 여전히 암울하다. 하나 더 추가해보자.

\( (x, y_1), (x, y_2) , (x, y_3), (x, y_4)\). 아직도 암울한가 ? 그렇지 않다. 저 네 쌍의 index로부터 우리가 알 수 있는건 \(a[y_1] = a[y_2] = a[y_3] = a[y_4]\) 이고 \(y_1 \neq  y_2 \neq  y_3 \neq  y_4\)이다. 찾았다. \((y_1, y_2), (y_3, y_4)\)이 답이 될 수 있다. 도출할 수 있는 결론은 "\(a[i] + a[j]\)가 같은 네 쌍 이상의 index가 있다면 우리는 무조건 답을 찾아낼 수 있다."

 정리해보자. sum의 한 index안에 네 개 이상의 원소를 갖고 있고, 이 원소들 중 두 개를 뽑아 비교했을 때 답이 안되는 경우는 \( (x, y_1), (x, y_2) , ... , (x, y_m) , ( m<=n)\) 이다. 이 외의 경우는 모두 상수 시간 안에 답을 찾아낼 수 있으므로, 시간 복잡도는 \(O(n^2)\)으로 봐도 무방하다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MOD = 998244353;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

vector<vector<pair<int, int>>> sum(5000000);
int a[200001] = { 0, };
int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		for (int j = 1; j < i; j++) {
			sum[a[j] + a[i]].push_back({ j, i });
			if (sum[a[j] + a[i]].size() > 1) {
				vector<pair<int, int>>& vec = sum[a[j] + a[i]];

				for (int p1 = 0; p1 < vec.size(); p1++) {
					int x = vec[p1].first, y = vec[p1].second;
					for (int p2 = p1 + 1; p2 < vec.size(); p2++) {
						int z = vec[p2].first, w = vec[p2].second;

						if (x == z || x == w || y == z || y == w) continue;

						cout << "YES\n" << x << ' ' << y << ' ' << z << ' ' << w;
						return 0;
					}
				}
			}
		}
	}

	cout << "NO\n";

	return 0;
}

맨날 백준만 풀다가 처음으로 도전해본 Codefroce 

A. Split it!

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

식으로 멋지게 포장되어있지만 핵심은 입력받은 string의 앞에서부터 palindrome을 만족하는 string의 길이를 확인하면 된다.

예를 들어 8 2 pushahsup 가 입력으로 들어왔다고 가정해보자.

pushahsup

앞뒤로 4개의 알파벳이 palindrome을 만족하고 있다. 이 때, 주어진 k는 2이므로 우리는

s = p + u + shahs + u + p

  = pu + s + hah + s + up

  = pus + h + a + h + sup

문제에서 제시한 조건에 만족하는 3개의 s를 만들 수 있다. 

결국, 입력받은 string에서 palindrome을 만족하는 string의 길이를 count라고 한다면, count가 k보다 크거나 같으면  조건에 만족하는 s를 찾을 수 있고, 그렇지 않다면 불가능하다.

여기서 한가지 예외가 있는데, n이 짝수이고 k == n / 2인 경우를 생각해보자.

우리는 분명히 앞에서부터 k개의 palindrome을 만들고 \(a_{k+1}\)에 남은 substring을 넣어주어야 한다. 

하지만 n이 짝수이고 k == n / 2이라면, 입력받은 string에 상관없이 \(a_{k+1}\)은 empty string이 된다. 따라서 이 경우 무조건 NO를 출력해준다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MOD = 998244353;
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 n, k;
		string str;
		cin >> n >> k >> str;
        
		if (n % 2 == 0 && n / 2 == k) {
			cout << "NO\n";
			continue;
		}

		bool ans = true;
		int cnt = 0;
		for (int i = 0; i < n / 2; i++) {
			if (str[i] == str[n - 1 - i]) {
				cnt++;
			}
			else break;
		}
		if (cnt >= k) cout << "YES\n";
		else cout << "NO\n";
			
	}
	return 0;
}

B. Max and Mex

https://codeforces.com/contest/1496/problemB

테스트 중에 set을 이용하여 제시된 operation을 k번 하는 코딩을 했으나, k가 최대 10의 9승이라 당연히 TIME LIMIT.

테스트 끝나고 생각해보니, distinct number가 계속해서 늘어나는 경우는 mex(S)가 max(S)보다 큰 경우 밖에 없다.

mex(S)가 max(S)보다 작은 경우 operation은 몇번 하든 추가되는 숫자는 항상 같다. 왜냐하면 항상 mex(S)와 max(S) 중간에 있는 숫자가 추가되기 때문에, mex(S)나 max(S)가 바뀔 일이 없다.

결국,

mex(S)가 max(S)보다 크면, n + k

mex(S)가 max(S)보다 작고 \(\left \lceil \frac{mex(S) + max(S)}{2} \right \rceil \) 의 값이 이미 S에 존재하면, n

그렇지 않다면, n + 1 을 출력하면 된다.

max(S) = set에 마지막 원소, O(1)

mex(S) = set의 find 함수 이용, 0부터 하나씩 찾아본다. O(n * log n)

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MOD = 998244353;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int num[100001] = { 0 , };

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

	int T;
	cin >> T;
	while (T--) {
		int n, k;
		set<int> s;
		cin >> n >> k;
		int MEX = -1, MAX = 0, ans = 0;
		for (int i = 0; i < n; i++) {
			cin >> num[i];
			s.insert(num[i]);
		}
		if (k == 0) {
			cout << n << '\n';
			continue;
		}

		auto it = s.end();
		it--;
		MAX = *it;
		while (s.find(++MEX) != s.end());

		if (MEX > MAX) cout << n + k << '\n';
		else {
			int add = (MAX + MEX + 1) / 2;
			if (s.find(add) != s.end()) cout << n << '\n';
			else cout << n + 1 << '\n';
		}
	}
	return 0;
}

C. Diamond Miner

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

간단하다.

0에 가까운 순서대로 mine과 miner를 매칭시켜주면 된다.

이 부분은 자명해서 자세한 설명은 생략.

sorting 후, 계산만 해주면 되기 때문에 O(n*log n)에 해결 가능하다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<int> mine;
vector<int> miner;
bool compare(const int& a, const int& b) {
	if (abs(a) == abs(b))
		return a < b;
	return abs(a) < abs(b);
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T;
	cin >> T;
	while (T--) {
		int n, x, y;
		cin >> n;
		mine.resize(n);
		miner.resize(n);
		for (int i = 0, j = 0; i + j < 2 * n;) {
			cin >> x >> y;
			if (x == 0)
				miner[i++] = y;
			if (y == 0)
				mine[j++] = x;
		}
		sort(mine.begin(), mine.end(), compare);
		sort(miner.begin(), miner.end(), compare);
		double sum = 0;
		for (int i = 0; i < n; i++)
			sum += sqrt(pow(mine[i], 2) + pow(miner[i], 2));
		cout.precision(10);
		cout << fixed << sum << '\n';


	}


	
	return 0;
}