ABC287 A～C(C++)

A - Majority

問題概要

ある提案に対し、$N$人の人が賛成か反対かを表明しています。なお、$N$は奇数であることが保証されます。
$i$番目の人の意見は文字列$S_i$で表されます。$S_i=$Forのときは$i$番目の人が賛成であることを、$S_i=$Againstのときは反対であることを表します。
過半数の人がこの提案に賛成しているか判定してください。

• $1\leq N\leq 99$
• $N$は奇数
• 各$i=1,2,\dots,N$について、$S_i=$Forまたは$S_i=$Against

問題リンク

• https://atcoder.jp/contests/abc287/tasks/abc287_a

解説

$S_i$なる$i$の個数が$\frac{N}{2}$個より多いかを判定すればよいです。

実装例

#include<iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		if (s == "For") {
			cnt++;
		}
	}
	if (cnt > n / 2)cout << "Yes\n";
	else cout << "No\n";
}

• AC:8ms

B - Postal Card

問題概要

数字のみからなる長さ$6$の文字列が$N$個与えられます。$i(1\leq i\leq N)$番目の文字列は$S_i$です。
また、数字のみからなる長さ$3$の文字列が$M$個与えられます。$i$番目の文字列は$T_i$です。
$S_i$の末尾$3$文字が$T_1,\dots,T_N$のいずれかに一致するような$S_i$はいくつありますか?

• $1\leq N,M\leq 10^3$
• $N,M$は整数
• $|S_i|=6$であり、$S_i$は数字のみからなる
• $|T_i|=3$であり、$T_i$は数字のみからなる

問題リンク

• https://atcoder.jp/contests/abc287/tasks/abc287_b

解説

素直にforとかを使うと解ける。$O(NM)$で十分間に合う。

実装例

#include<iostream>
#include<vector>
using namespace std;
int main() {
	int n, m;
	cin >> n >> m;
	vector<string> s(n), t(m);
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> t[i];
	}

	int ans = 0;
	for (int i = 0; i < n; i++) {
		bool exist = false;

		string sub = s[i].substr(s[i].size() - 3);  //末尾3文字
		for (int j = 0; j < m; j++) {
			if (sub == t[j]) {
				exist = true;
			}
		}
		if (exist) {
			ans++;
		}
	}
	cout << ans << endl;
}

• AC:8ms

C - Path Graph?

問題概要

$N$頂点$M$辺の単純無向グラフが与えられます。このグラフがパスグラフであるか判定してください。

• $1\leq N,M\leq 10^5$
• 入力はすべて整数
• 入力で与えられるグラフは単純

パスグラフとは

$(1,2,\dots,N)$の並べ替え$(v_1,\dots,v_N)$であって、次の条件を満たすようなものが存在するときパスグラフであるといいます。

• $1\leq i\leq N-1$なるすべての$i$について、$v_i,v_{i+1}$を結ぶ辺がある。
• $|i-j|>1$ならば$v_i,v_j$を結ぶ辺はない

問題リンク

• https://atcoder.jp/contests/abc287/tasks/abc287_c

解説(?)

ほぼ木みたいな感じである。ただ、これだけだとダメ。さらに、

• 次数が$2$以下

である必要がある。これらの判定は...UnionFindとか使えば解ける。
ACL(AtCoderLibrary)というのがあって、そこにUnionFindは用意されてる。持ってなければ、それを使うといいかも。

筆者の解法(めんどい)

次のように言い換えて解いた。

• 木である。
• ある頂点$v$が存在して、$v$を根としてみると各頂点の子は高々$1$つ

$3$番目の条件についてだが、例えば、サンプル1のグラフ(下図)

だと$v=1,4$とするといい。直感的に言うと、一番端の頂点を選べば条件を満たしてくれる。
ちゃんとやると、$v$は木の「葉」を選べばいいことがわかる。
あとはDFSとかでがんばる。

実装例

#include<iostream>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main() {
	int n, m;
	cin >> n >> m;
	if (m != n - 1) {
		cout << "No\n";
		return 0;
	}
	dsu uf(n);
	vector<int> deg(n);
	for (int i = 0; i < m; i++) {
		int v, u;
		cin >> v >> u;
		v--;
		u--;
		deg[v]++;
		deg[u]++;
		if (uf.same(v, u)) {
			//サイクルがあったとき
			cout << "No\n";
			return 0;
		}
		uf.merge(v, u);
	}
	if (uf.groups().size() > 1) {
		//非連結のとき
		cout << "No\n";
		return 0;
	}
	for (int v = 0; v < n; v++) {
		//次数が2より大きい頂点があるとき
		if (deg[v] > 2) {
			cout << "No\n";
			return 0;
		}
	}
	cout << "Yes\n";
}

• AC:98ms

終わりに

D,Eは...別記事で書きます。
ここまで読んでくださってありがとうございます。