[Codeforces] Round #705 (Div. 2) A ~ D 풀이

 

 

21.03.06 23:05 Round #705 참가 (Rating 1740 -> 1855 / Performance = 2137)

 

대회 시간도 2시간 15분이고, 세터의 예전 라운드도 어려운 난이도였고, 점수 분포를 보고도 대충 어려울 거라고 예상은 했지만, C부터 이렇게 어려울 줄이야.... 대회 때 C, D 솔브수가 1000명이 안되었다.

2시간이 아니어서 다행히 D까지 풀 수 있었다. 

 

---

 

A. Anti-knapsack (*800)

 

n과 k가 주어질 때, {1, 2, ..., n}의 부분집합 중에서, 합이 k가 되도록 원소 일부를 고를 수 없는 최대 부분집합을 구하는 문제이다.

일단, k+1 ~ n까지는 항상 포함시켜도 된다. 

그리고, (k-1, 1) , (k-2, 2) ... 등의 쌍이 둘을 더하면 k가 되므로,

k-1 ~ 1에서 앞의 절반만큼, k-1, k-2, ..., k- (k-1)/2 만큼 부분집합에 포함시키면 k를 만들 수 없으면서 최대이다. 

 

[소스 코드]

#include<bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
 
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int n, k; cin >> n >> k;
		vector<int> ans;
		for (int i = n; i > k; i--) ans.push_back(i);
		for (int i = k - 1; i >= (k + 1) / 2; i--) {
			ans.push_back(i);
		}
		cout << sz(ans) << '\n';
		for (int i : ans) cout << i << ' ';
		cout << '\n';
	}
}

 

 

B. Planet Lapituletti (*1300)

 

'시'와 '분'의 범위가 주어지고, 시간을 거울에 비췄을 때 거울에 나타난 시간이 '시'와 '분'의 범위 내를 만족하는 제일 빠른 시간을 구하는 문제이다.

2는 5와 대칭이고, 1은 중간에 있기 때문에, 시간에 3, 4, 6, 7, 9가 나타난 경우는 항상 불가능하다. 

주어진 시간을 시작으로 1분씩 계속 더해가면서 완전탐색으로 가능한 경우를 찾아주면 된다.

 

[소스 코드]

#include<bits/stdc++.h>
using namespace std;
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int h, m; cin >> h >> m;
		string s; cin >> s;
		int nh, nm;
		nh = (s[0] - '0') * 10 + s[1] - '0';
		nm = (s[3] - '0') * 10 + s[4] - '0';
		for (int i = 0; ; i++) {
			int x = (nh + (nm + i) / m) % h;
			int y = (nm + i) % m;
			if (x == 0 && y == 0) {
				cout << "00:00\n";
				break;
			}
			vector<int> v(4);
			v[0] = y % 10;
			v[1] = y / 10;
			v[2] = x % 10;
			v[3] = x / 10;
			bool chk = false;
			for (int j = 0; j < 4; j++) {
				if (v[j] == 2) v[j] = 5;
				else if (v[j] == 5) v[j] = 2;
				else if (v[j] != 0 && v[j] != 1 && v[j] != 8) chk = true;
			}
			if (chk) continue;
			if (v[0] * 10 + v[1] < h && v[2] * 10 + v[3] < m) {
				cout << x / 10 << x % 10 << ':' << y / 10 << y % 10 << '\n';
				break;
			}
		}
	}
}

 

 

C. K-beautiful Strings (*2000)

 

길이 n의 문자열 s가 주어지고, 자연수 k가 주어진다.

s보다 사전 순으로 뒤에 있으면서, 문자열에 출현한 각 알파벳의 횟수가 k의 배수인 문자열 중 사전 순으로 가장 빠른 문자열을 구하는 문제이다.

 

(푸는데 1시간이 넘게 걸렸다... 복잡하게 푼줄 알았는데 에디토리얼 코드마저 길다)

 

일단 기본적으로 주어진 문자열이 이미 조건을 만족한다면 그대로 출력해주면 된다.

그리고 n이 k로 나누어떨어지지 않는다면, 절대 출현하는 각 알파벳의 횟수가 k의 배수가 될 수 없다.

이외의 경우는 항상 가능하다. "zzzzz....zzz"가 항상 가능한 경우이기 때문이다.

 

먼저, 사전 순으로 가장 빠르면서 조건을 만족하는 문자열(ans)을 찾아야 하므로 앞에서부터 확인한다.

핵심적인 아이디어는, 답이 되는 문자열(ans)이 기존의 문자열(s)과 처음으로 다른 부분이 어느 부분인지를 찾아준다. 

ans는 무조건 s보다 사전 순으로 뒤에 있기 때문에, 처음으로 다른 부분을 q라고 하면, ans[q] > s[q]를 만족한다.

 

따라서, i = 0, 1, ... n-1 에서 s[i]를 현재 알파벳보다 사전 순으로 더 큰 알파벳으로 바꿀 때, 조건을 만족하는 경우가 있는지를 찾아주고, i가 가장 큰 경우를 답으로 고려하면 된다.

 

s[i]를 현재 알파벳보다 사전 순으로 더 큰 알파벳으로 바꾼다면 s[i+1] ~ s[n-1] 알파벳들은 어떤 것으로 바꾸어도 항상 기존의 s보다 사전 순으로 크기 때문에, 이를 이용해서 조건을 만족하면서 사전 순으로 가장 빠른 문자열을 구하면 된다.

 

자세한 건 코드를 통해서 확인해보자.

변수 r은 s[i+1] ~ s[n-1]의 알파벳이 아무거나 가능하므로, 자유롭게 배정 가능한 문자의 수를 의미한다. 

if (w > 0) r -= (k - w) 문장은 k의 배수로 맞춰주기 위해서 필요한 문자의 수만큼 빼주는 부분이다.

 

[소스 코드]

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

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int n, k; cin >> n >> k;
		string s; cin >> s;
		vector<int> cnt(26);
		for (int i = 0; i < n; i++) {
			cnt[s[i] - 'a']++;
		}
		bool can = true;
		for (int i = 0; i < 26; i++) {
			if ((cnt[i] % k) != 0) can = false;
		}
		if (can) {
			cout << s << '\n';
			continue;
		}
		if (n % k != 0) cout << -1 << '\n';
		else if (k == 1) cout << s << '\n';
		else {
			cnt.assign(26, 0);
			int idx = -1;
			int val = -1;
			for (int i = 0; i < n; i++) {
				vector<int> tmp(26);
				for (int j = s[i] - 'a' + 1; j < 26; j++) {
					tmp[j] = 1;
					int r = n - i - 1;
					for (int q = 0; q < 26; q++) {
						int w = (cnt[q] + tmp[q]) % k;
						if (w > 0) r -= (k - w);
					}
					if (r >= 0 && r % k == 0) {
						idx = i;
						val = j;
						break;
					}
					tmp[j] = 0;
				}
				cnt[s[i] - 'a']++;
			}
			if (idx == -1) {
				cout << -1 << '\n';
			}
			else {
				cnt.assign(26, 0);
				for (int i = 0; i < idx; i++) {
					cnt[s[i] - 'a']++;
				}
				s[idx] = 'a' + val;
				cnt[val]++;
				for (int i = n - 1; i > idx; i--) {
					bool chk = false;
					for (int j = 25; j >= 0; j--) {
						if (cnt[j] % k != 0) {
							s[i] = 'a' + j;
							cnt[j]++;
							chk = true;
							break;
						}
					}
					if (!chk) s[i] = 'a';
				}
				cout << s << '\n';
			}
		}
	}
}

 

 

D. GCD of an Array (*2100)

 

디스크립션은 간단하다.

n개의 원소로 이루어진 배열이 주어지고, q개의 쿼리가 들어온다.

각 쿼리는 a[i]에 x를 곱하는 쿼리이고, 쿼리를 수행할 때마다 배열의 모든 원소의 gcd를 구하는 문제이다.

 

당연하게, 매 쿼리마다 gcd를 다시 계산해줄 수는 없다.

a[i]에 x가 곱해질 때, 어떤 소수가 모든 원소에 공통으로 포함된 최소 개수가 증가하는 경우에만 gcd를 갱신해주면 된다. 

이를 위해서 set과 map을 이용해준다. 

set<pii> 배열인 st는 각 원소에 들어있는 소수 i의 최소 개수를 구하는데 이용된다. st[i].begin()을 이용하기 위함이다.

그리고 map은 이전에 a[i]에 들어있는 어떤 소수의 개수를 저장하는데 이용되고,

쿼리마다 a[i]에 x가 추가로 곱해질 때 map을 이용해서 원래 a[i]에 들어있던 소수의 개수를 구하여 set에서 제거해준다.

그다음 x를 곱하면 소수의 개수가 증가하고, 증가한 값을 다시 set에 넣어준 다음 st[i].begin()을 이용하여 최소 개수를 구해준다.

 

[소스 코드]

#include<bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MOD = (int)1e9 + 7;

set<pii> st[200001]; //st[i] = 소인수 i를 a[j]에 몇개 가지고 있는지 (cnt, a[j]) pair로 저장하는 set
map<pii, int> mp; //mp[{i, j}] = a[i]에 들어있는 소인수 j의 개수 
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n, q; cin >> n >> q;
	ll g = 0;
	for (int i = 1; i <= n; i++) {
		int a; cin >> a;
		g = gcd(a, g);
		for (int j = 2; j * j <= a; j++) {
			if (a % j == 0) {
				int cnt = 0;
				while (a % j == 0) {
					a /= j;
					cnt++;
				}
				st[j].insert({ cnt, i });
				mp[{i, j}] = cnt;
			}
		}
		if (a > 0) {
			st[a].insert({ 1, i });
			mp[{i, a}] = 1;
		}
	}

	while (q--) {
		int a, b; cin >> a >> b;
		vector<pii> tmp; //A[a]에 곱해지는 소인수들 
		for (int i = 2; i * i <= b; i++) {
			if (b % i == 0) {
				int cnt = 0;
				while (b % i == 0) {
					b /= i;
					cnt++;
				}
				tmp.push_back({ i, cnt });
			}
		}
		if (b > 1) tmp.push_back({ b, 1 });

		for (auto [i, cnt] : tmp) {
			int k = mp[{a, i}];
			int prev = 0, post = 0;
			if (sz(st[i]) == n) prev = (*st[i].begin()).first; //소인수 i를 가장 적게 가지고 있는 원소에 들어있는 i의 개수
			st[i].erase({ k, a });
			st[i].insert({ k + cnt, a });
			mp[{a, i}] += cnt;
			if (sz(st[i]) == n) post = (*st[i].begin()).first; 
			if (post > prev) {
				for (int j = 1; j <= post - prev; j++) {
					g = (g * i) % MOD;
				}
			}
		}
		cout << g << '\n';
	}
}