[Codeforces] Round #559 (Div. 2) A ~ E 풀이

 

21.03.05 23:35 virtual 참가 / performance = 2391

 

 

 

A. A pile of stones (*800)

 

+가 주어질 때는 돌이 1개 증가하고, -가 주어질 때는 돌이 1개 감소한다. 

처음에 보유할 수 있는 돌은 임의로 정할 수 있고, 중간에 돌이 0개일 때 -가 들어오면 안 될 때, 최종적으로 가능한 최소 돌의 개수를 구하는 문제이다.

처음의 돌 수를 직접 정할 수 있으므로, 단순하게 -가 들어오는 경우, 만약 현재 돌이 0개이면 그대로 유지시켜주면 된다.

이 과정이 결국 처음의 돌 수를 1개 증가시키는 과정과 동일하다.

 

[소스 코드]

#include<bits/stdc++.h>
using namespace std;
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n; cin >> n;
	string s; cin >> s;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '-') {
			cnt = max(cnt - 1, 0);
		}
		else cnt++;
	}
	cout << cnt;
}

 

 

B. Expansion coefficient of the array (*1300)

 

n개의 원소로 이루어진 배열이 주어질 때, 모든 $(i, j)$ 쌍에 대해서 $k*|i - j| \leq min(a_i, a_j)$를 만족하는 최대 $k$를 구하는 문제이다. 

만족하는 어떤 k값을 x라고 하면 x보다 작은 모든 값은 항상 가능하므로, 파라메트릭 서치(parametric search)를 이용해 줄 수 있다. 

시간 복잡도는 O(nlog(1e9)) 정도로 나오게 된다.

 

[소스 코드]

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
ll a[300001];
vector<pii> v;
int n;
bool sol(ll m) {
	for (int i = 0; i < sz(v); i++) {
		if (m * (ll)max(n - v[i].second, v[i].second - 1) > v[i].first) return false;
	}
	return true;
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		v.push_back({ a[i], i });
	}
	sort(all(v));
	ll s = 0;
	ll e = 1e10;
	ll ans = 0;
	while (s <= e) {
		ll mid = (s + e) / 2;
		if (sol(mid)) {
			ans = max(ans, mid);
			s = mid + 1;
		}
		else e = mid - 1;
	}
	cout << ans;
}

 

 

C. The Party and Sweets(*1500)

 

2차원 행렬이 있을 때, 각 행별로 해당 행의 원소들 중 최솟값 $b_i$가 주어지고, 각 열 별로 해당 열의 원소들 중 최댓값 $g_i$가 주어질 때, 행렬의 모든 원소들의 합을 최소화하는 문제이다. 

 

	3	4
1	3	1
2	2	4
1	1	1

 

위의 예시처럼 1열은 각 행의 최솟값을 의미하고, 1행은 각 열의 최댓값을 의미할 때, 다음과 같이 원소를 배정하는 경우가 전체 원소의 합이 최소인 경우이다.

 

우선, 각 행별로는 최솟값이 주어지기 때문에 해당 값만큼 각 행의 모든 원소의 배정해준다. 

위의 예시로는 다음과 같이 배정해주는 것이다.

 

	3	4
1	1	1
2	2	2
1	1	1

 

그 다음, 각 열 별로 최댓값을 고려해주어야 하는데, 원소의 합을 최소화하기 위해서는 이미 배정된 원소들 중 제일 큰 값, $max(b_i)$인 행을 더 증가시켜주는 것이 최적이다. 

 

그러므로, 두번째 행의 원소들을 모두 열의 최댓값 $g_i$ 들로 바꿔주면 된다. 

단, 해당 행의 모든 원소들이 반드시 증가해야 한다면 행의 최솟값 조건을 만족하지 못하기 때문에, 그다음으로 큰 원소가 있는 행을 하나 골라서 $min(g_i)$에 해당하는 열을 바꾸어준다.  

 

문제 조건을 만족하지 못하는 경우는, $max(b_i) > min(g_i)$ 인 경우이다. 

 

[소스 코드]

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

ll b[100001], g[100001];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n, m; cin >> n >> m;
	ll mx = 0;
	ll mi = MAX;
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
		mx = max(mx, b[i]);
	}
	for (int i = 1; i <= m; i++) {
		cin >> g[i];
		mi = min(mi, g[i]);
	}
	if (mx > mi) return cout << -1, 0;
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += 1LL * m * b[i];
	}
	if (mi == mx) {
		for (int i = 1; i <= m; i++) {
			ans += g[i] - mx;
		}
	}
	else {
		sort(b + 1, b + 1 + n);
		sort(g + 1, g + 1 + m);
		for (int i = 2; i <= m; i++) {
			ans += g[i] - b[n];
		}
		ans += g[1] - b[n - 1];
	}
	cout << ans;
}

 

D. The minimal unique substring (*2200)

 

s가 0과 1로 이루어진 문자열이고, n과 k가 주어진다. s의 substring 중에서 s에서 1번만 출현하는 substring 중 가장 짧은 substring의 길이가 k가 되는 s를 찾는 문제이다. 

 

예를 들어서 n = 5, k = 3인 경우, s = 10101이 가능한데, "1", "0", "10", "01" 은 모두 2번 이상 나오고, "010"은 1개만 존재하므로 조건을 만족한다. 

 

개인적으로 E보다 훨씬 쉬운 듯 한데 규칙 찾는 문제라 Div.1에서는 E보다 덜 풀렸고 난이도가 더 높은 것 같다. 

Div.2에서는 D가 더 많이 풀렸다.

 

규칙을 찾는 과정은 직접 예시를 만들어보다보면 나오는 과정이라 설명하기가 애매해서... 정답만 적겠다. 

 

먼저, n = k인 경우에는 "111....1" 을 출력하면 된다. 

n = k+2인 경우에는, "10101010...1", 즉 '10'이 반복되도록 출력하면 된다. 

그러면 양끝 문자 하나씩을 제외한 [2, n-1] substring이 조건을 만족하는 substring이 된다.

n = k+4인 경우에는 "110110110....", 즉 "110"이 반복되도록 출력하면 된다. 

그러면 양끝 문자 두개씩을 제외한 [3, n-2] substring이 조건을 만족하는 substring이 된다.

이런 식으로 n-k가 2씩 커질 때마다, "1110", "11110", .... 과 같이 문자열을 반복하면 된다. 

 

[소스 코드]

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

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n, k; cin >> n >> k;
	if (n == k) {
		for (int i = 1; i <= n; i++) cout << 1;
	}
	else {
		for (int i = 1; i <= (n - k) / 2; i++) cout << 1;
		cout << 0;
		for (int i = 1; i <= (n - k) / 2; i++) cout << 1;
		int cnt = (n - k) / 2;
		n -= cnt * 2 + 1;
		for (int i = 1; i <= n; i++) {
			if (i % (cnt + 1) == 1) cout << 0;
			else cout << 1;
		}
	}

} 

 

 

E. Permutation recovery (*2100)

 

풀이를 계속 봐도 정확히 이해를 못하겠다. 가능한 경우에 permutation을 배정하는 건 알겠는데, 불가능한 경우인지 확인하는 과정이 이해가 잘 안 된다. 다른 사람들의 풀이를 보니 세그 트리를 이용한 풀이가 꽤 있던데, 혹시 풀이를 잘 아시는 분은 알려주시면 매우 매우 감사할 것 같다....

 

일단은 간략하게, next[i] -> i로 가는 간선들을 모두 연결한 후, 루트 (n+1)부터 정점을 방문할 때마다 번호를 하나씩 감소시켜가면서 p[i]를 할당시켜주는 방식이다. 

이 방식은 꽤 유용할 것 같아서 일단 아이디어만 대충 학습했다.

 

[소스 코드]

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

int nex[500010];
vector<int> adj[500010];
int cnt;
int p[500010];
void dfs(int u) {
	p[u] = cnt--;
	for (int v : adj[u]) dfs(v);
}
int main(void) {
	ios::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 + 1; i++) adj[i].clear();
		for (int i = 1; i <= n; i++) {
			cin >> nex[i];
			if (nex[i] == -1) nex[i] = i + 1;
			adj[nex[i]].push_back(i);
		}
		cnt = n+1;
		dfs(n + 1);
		stack<int> s;
		bool chk = true;
		for (int i = n; i >= 1; i--) {
			while (!s.empty() && p[s.top()] < p[i]) s.pop();
			//i < j < next_i < next_j  => No answer
			if ((s.empty() && nex[i] != n + 1) || (!s.empty() && s.top() != nex[i])) chk = false;
			s.push(i);
		}
		if (!chk) cout << -1 << '\n';
		else {
			for (int i = 1; i <= n; i++) cout << p[i] << ' ';
			cout << '\n';
		}
	}
}

 

---

한동안 코포를 소홀히하고, SUAPC가 끝난 후 첫 코포를 망치고, 어느 순간부터 내가 썼던 퍼플 공부법을 하나도 지키고 있는 내 모습을 발견했다.... 업솔빙도 안하고 손으로 풀어보지도 않고...

다시 초심으로 돌아가서 코포에 집중을 해보려고 한다. 학회사람들과 진행하는 코포 스터디뿐만 아니라 개인적으로도 자주 버추얼을 돌리면서 올해 목표인 오렌지를 꼭 달성하고 싶다.

 

PC로 보시는 것을 권장합니다. 

피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^