ARC106-Bの解答

AtCoder Regular Contest106-B Valueの解答を書いていきます。

問題はこちらから。

B - Values

Difficulty 686　（茶色）

問題

n 頂点 m 辺の単純無効グラフがあります。 i 番目の辺は頂点 ci とdi を結んでいます。はじめ、各頂点 i には ai が与えられます。次の操作を 0 回以上行うことで、各頂点 i の数字を bi にしたいです。

辺を一つ選択する。この辺が結ぶ頂点の片方を+1、片方を-1とする。

適切に操作をすることで、目標を達成することは可能でしょうか？可能であれば"Yes"、可能でなければ"No"を出力してください。また、グラフは自己ループや多重辺を含みません。

考察

今回の問題で求められていることは「目標の達成が可能であるかの判定」であり、具体的な操作方法は導出する必要がありません。ここ重要です。

そこで、操作について少し考えます。

操作では、片方を+1、もう片方を-1するため、操作前後で2つの頂点(a1,a2とします)の値の総和は変化しません。さて、では片方の頂点(a1)に更に別の頂点(a3)がつながっていた場合はどうなるでしょうか？a1とa3を繋ぐ辺を選択すれば、a1の値とa3の値を+1,-1できますが、その和って変化しませんよね。

これは、さらに辺と頂点を追加していっても同様のことが言えます。連結している頂点の値の総和は本操作では変更することができないのです。

また、操作にて値は±1ずつ変化します。そのため、連結成分の値の総和が等しくなる条件の下であれば、各頂点にて任意の値が実現されます。

操作の特性がわかったので、条件について考えます。

本操作を用いると

連結成分の総和が変化しない
任意の数が実現可能

となります。そのため条件を満たすためには、

連結成分の a の総和と b の総和が等しい

ことが条件となります。全ての頂点が連結されていれば簡単なのですが、そうもいきません。どの頂点が同じグルーブに属しているかを求める必要があります。

そのために、今回はUnion Findという手法を用いました。この手法はグラフの連結の関係をツリー状のデータ構造にて管理する手法です。

以前、「本手法を用いた問題があったから、UnionFindの解説記事を書いたはずだ」と思い、記事を探してみたら下書きに眠っていました。時間を見つけて書いておきます。ざっくりとした解説はabc177dをご覧いただけると幸いです。

Union Findにて、同じグループに属する頂点を管理できましたので、あとは a と b の総和を取っていきます。すべてのグループに関して、a の総和と b の総和が等しければ "Yes"、そうでなければ"No"を出力しましょう。

補足です。a = bとなればよいので、a - b = 0ですね。そのため、先にすべての頂点に関して、a - b をしておいて、総和 = 0とすれば少しだけスマートに処理できます。

あと、私のUnion Findは 0 インデックスで作ってますので、デクリメントしてから投げています。

実装

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using ll = long long;
using namespace std;

struct UnionFind {
	vector<int> d;
	//コンストラクタ
	UnionFind(int n = 0) : d(n, -1) {}
	//根の探索と張り替え
	int find(int x) {
		if (d[x] < 0) return x;
		//根のはりかえ
		return d[x] = find(d[x]);
	}
	//根の結合
	bool unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return false;
		//大きい方に小さい方をくっつける
		if (x < y) swap(x, y);
		//サイズの更新
		d[x] += d[y];
		//結合
		d[y] = x;
		return true;
	}
	//サイズの取得
	int size(int x) { return -d[find(x)]; }
	//同じ集合に属しているか
	bool same(int x, int y) { return (find(x) == find(y)); }
};

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> d(n);
	vector<int> a(n);
	vector<int> b(n);

	rep(i, n) cin >> a[i];
	rep(i, n) cin >> b[i];


	rep(i, n)d[i] = b[i] - a[i];


	UnionFind uf(n);

	rep(i, m) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		uf.unite(a, b);
	}

	vector<ll> s(n, 0);
	rep(i, n)
	{
		s[uf.find(i)] += d[i];
	}

	string ans = "Yes";
	for (auto i : s)
	{
		if (i != 0)
		{
			ans = "No";
			break;
		}
	}

	cout << ans << endl;

	return 0;
}

おわりに

この問題を解いた際には「結構難しいなー」って思ったのですが、案外diffは高くなくて、あれ？っと思いました。でも、以前にあったabc177dも似たようなdiffなので、そんなもんなのかと納得させました。

アルゴリズムを知らないと結構大変ですが、知っていればライブラリに投げて終わりということを考えれば、適切な数値なのかな。

とはいえ、ライブラリは充実するに越したことはないので、コツコツと増やしていきましょう。