ABC288 A~C(C++)

ABC288に参加しました。AからCまでの感想・解説を書いていきます~

A - Many A+B Problems

問題概要

$N$個の整数の組$(A_1,B_1),(A_2,B_2),\dots,(A_N,B_N)$が与えられる。各$i=1,2,\dots,N$に対して$A_i+B_i$を出力せよ。

• $1\leq N\leq 1000$
• $-10^9\leq A_i,B_i\leq 10^9$
• 入力はすべて整数

解説

整数$a,b$を受け取って、$a+b$を出力することを$N$回繰り返せばよい。

#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        cout<<a+b<<'\n';
    }
}
return 0;

• AC:12ms

B - Qualification Contest

問題概要

$N$人がコンテストに参加し、$i$位の人のハンドルネームは$S_i$でした。
上位$K$人のハンドルネームを辞書順で出力してください。

• $1\leq K\leq N\leq 100$
• $K,N$は整数
• $S_i$は英小文字のみからなる長さ$10$以下の文字列
• $S_i\neq S_j(i\neq j)$

解説

上位$K$人を抽出して、後はsortすればよい。

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

	vector<string> vec(k);	//上位k人を抽出する
	for(int i=0;i<k;i++){
		vec[i]=s[i];
	}

	sort(vec.begin(),vec.end());	//辞書順で並べ替える
	//出力
	for(int i=0;i<k;i++){
		cout<<vec[i]<<'\n';
	}
}

• AC:7ms

C - Don’t be cycle

問題概要

単純無向グラフが与えられる。このグラフが、閉路を持たないようにするにはいくつ辺を取り除けばよいか?

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

解説

求める答えは閉路の個数に一致する。

理由

まず、各閉路は、一つ辺を取り除くことで解消することができる。すなわち、閉路の個数$c$について、削除する辺の本数は高々$c$本である。
また、取り除いた辺が$c$本未満の時は、少なくともひとつ、解消されていない閉路が残ってしまう。したがって、取り除く本数は$c$本以上。
以上より、削除するべき辺の本数はちょうど$c$であることが分かる。

閉路の個数のカウントは...UnionFindとか、BFS,DFSを使うことができる。
ここでは、UnionFindを用いる。

UnionFind(DSUクラス)の実装は省略している。

#include<iostream>
#include<vector>
using namespace std;
int main(){
	int n,m;
	cin>>n>>m;
	DSU uf(n);	//n頂点のUnionFind
	int cycle=0;
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		a--,b--;
		if(uf.same(a,b)){	//同じ連結成分同士でもう一度繋がれると、サイクルができる。
			cycle++;
		}
		uf.merge(a,b);
	}
	cout<<cycle<<'\n';
}

• AC:106ms