ABC352A-EをC++で解く

ABC352に参加したので、考察や解説を残します。

成績

五完(ABCDE)することができたので、水色目前になりました！

目次

A問題 AtCoder Line
B問題 Typing
C問題 Standing On The Shoulders
D問題 Permutation Subsequence
E問題 Clique Connect

A問題 AtCoder Line

ABC352 A - AtCoder Line
$X$と$Y$の間に$Z$があるかどうかを判定すれば良い。

code.cpp

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

int main() {
    int n, x, y, z;
    cin >> n >> x >> y >> z;
    cout << (min(x, y) < z && z < max(x, y) ? "Yes" : "No") << '\n';
}

B問題 Typing

ABC352 B - Typing
$T$の部分文字列(連続するとは限らない)にSがあるかを確かめる。

code.cpp

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

int main() {
    string s, t;
    cin >> s >> t;
    vector<int> res(s.length());
    for (int i = 0, j = 0; j < int(t.length()); ++j) {
        if (s[i] == t[j]) res[i++] = j;
    }
    for (int i = 0; i < int(s.length()); ++i) cout << (i == 0 ? "" : " ") << res[i] + 1;
    cout << '\n';
}

C問題 Standing On The Shoulders

ABC352 C - Standing On The Shoulders
頂上に立つ巨人は$B$、それ以外は$A$を使って足し合わせる。
$B_i-A_i$が最大となるような巨人を頂上に立たせる。

code.cpp

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

int main() {
	int n;
	cin >> n;

	vector<long long> a(n), b(n);
	for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];
	long long max_dif = 0;
	for (int i = 0; i < n; ++i) max_dif = max(max_dif, b[i] - a[i]);

	cout << reduce(a.begin(), a.end()) + max_dif << '\n';
}

D問題 Permutation Subsequence

ABC352 D - Permutation Subsequence
$pos_i:p上のiの位置$とします。
$pos_i\cdots pos_{i+k-1}$の最大値から最小値を引いた値の最小値が答えとなる。
$pos_i\cdots pos_{i+k-1}$をstd::setに入ることで、最小値と最大値を$O(1)$で求めることができる。

code.cpp

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

int main() {
	int n, k;
	cin >> n >> k;

	vector<int> p(n);
	for (int i = 0; i < n; ++i) cin >> p[i], --p[i];

	vector<int> pos(n);
	for (int i = 0; i < n; ++i) pos[p[i]] = i;

	set<int> st(pos.begin(), pos.begin() + k);

	int res = *st.rbegin() - *st.begin();

	for (int i = 0; i + k <= n; ++i) {
		st.erase(pos[i]);
		st.emplace(pos[i + k]);
		res = min(res, *st.rbegin() - *st.begin());
	}

	cout << res << '\n';
}

E問題 Clique Connect

最小全域木はクラスカル法で考える。

クラスカル法は辺をコストが昇順になるように取り出し、まだその二つの頂点が繋がっていないなら、その辺を採用する。

連結判定はUnionFindですれば良い。
また、$A_i$の頂点すべてを連結にするには、最大で$K_i-1$回、辺を繋げれば良い。

code.cpp

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

// UnionFind...
// ------------
// ...UnionFind

int main() {
	int n, m;
	cin >> n >> m;

	vector<pair<int, vector<int>>> ops(m);
	for (int i = 0; i < m; ++i) {
		int k;
		cin >> k >> ops[i].first;
		ops[i].second.resize(k);

		for (int j = 0; j < k; ++j) cin >> ops[i].second[j], --ops[i].second[j];
	}
	sort(ops.begin(), ops.end());

	UnionFind uf(n);
	long long res = 0;

	for (int i = 0; i < m; ++i) {
		for (int j = 1; j < int(ops[i].second.size()); ++j) {
			if (uf.connected(ops[i].second.front(), ops[i].second[j])) continue;
			uf.merge(ops[i].second.front(), ops[i].second[j]);
			res += ops[i].first;
		}
	}

	cout << (uf.size(0) == n ? res : -1) << '\n';
}

以上です。ありがとうございました。