ABC352A-EをC++で解く

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

## 成績
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3784579/93c485b2-bf7a-e86a-ecb5-c79de96ac3e1.png)
**五完**(ABCDE)することができたので、<font color="Cyan">**水色目前**</font>になりました！

## 目次
[A問題 AtCoder Line](#a問題-atcoder-line)
[B問題 Typing](#b問題-typing)
[C問題 Standing On The Shoulders](#c問題-standing-on-the-shoulders)
[D問題 Permutation Subsequence](#d問題-permutation-subsequence)
[E問題 Clique Connect](#e問題-clique-connect)

## A問題 AtCoder Line
[ABC352 A - AtCoder Line](https://atcoder.jp/contests/abc352/tasks/abc352_a)
$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';
}
```
https://atcoder.jp/contests/abc352/submissions/53080770

## B問題 Typing
[ABC352 B - Typing](https://atcoder.jp/contests/abc352/tasks/abc352_b)
$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';
}
```
https://atcoder.jp/contests/abc352/submissions/53087062

## C問題 Standing On The Shoulders
[ABC352 C - Standing On The Shoulders](https://atcoder.jp/contests/abc352/tasks/abc352_c)
頂上に立つ巨人は$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';
}
```
https://atcoder.jp/contests/abc352/submissions/53092947

# D問題 Permutation Subsequence
[ABC352 D - Permutation Subsequence](https://atcoder.jp/contests/abc352/tasks/abc352_d)
$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';
}
```
https://atcoder.jp/contests/abc352/submissions/53115673

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