AtCoder

ABC327 D問題(Good Tuple Problem)を解く

AtCoder_ABC327_D

AtCoder が提供しているABC(AtCoder Beginner Contest)327 のD問題をC++とPythonで解いてみました。ABC327は、2023年11月4日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Good Tuple Problem(Difficulty : 709)

問題はリンク先をご覧ください。

ABC327 D問題 Good Tuple Problem

二部グラフか判断することに帰着できます。AtCoder Problems による Difficulty は、709 でした。

解答案

ABC284D問題解説記事)の問題文で二部グラフについて以下のように説明されていました。

無向グラフが二部グラフであるとは、下記の条件を満たすように各頂点を黒または白のどちらかの色で塗ることができることを言います。

  • 同じ色に塗られた頂点どうしを結ぶ辺は存在しない。
https://atcoder.jp/contests/abc282/tasks/abc282_d

この問題は、(Ai, Bi)を辺としたグラフが二部グラフになれば、白の頂点を0,黒の頂点を1と考えれば、「良い数列の組」となります。

二部グラフかの判断は、DFS(深さ優先探索:Depth-First Search)で行うグラフの探索を応用します。色を格納する配列 color を用意します。color の値は、-1:未決定、0:白、1:黒 とします。関数 dfs の戻り値は、二部グラフかどうかを返します。

関数 dfs の引数に色を表す cur_color を追加して、枝の先を反対の色で塗っていきます。もし、枝の先が同じ色であれば、二部グラフではないと判定できます。

C++ プログラム例(ABC327D)

上記で解説したように関数 dfs を実装しました。色が未決定の頂点に対して、dfs を呼び出し、二部グラフになっているか判定して、結果を出力しました。

以下が、C++プログラムとなります。

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

vector<vector<int>> G;
vector<int> color;

bool dfs(int v, int cur_color)
{
	color[v] = cur_color;
	for (auto next_v : G[v]) {
		if (color[next_v] != -1) {
			if (color[next_v] == cur_color) {
				return false;
			}
			continue;
		}
		if (!dfs(next_v, 1 - cur_color)) {
			return false;
		}
	}

	return true;	
}

int main()
{
	int n, m;
	cin >> n >> m;
	G.resize(n + 1);
	color.assign(n + 1, -1);

	vector<int> a(m);
	for (int i = 0; i < m; ++i) {
		cin >> a[i];
	}
	vector<int> b(m);
	for (int i = 0; i < m; ++i) {
		cin >> b[i];
	}

	for (int i = 0; i < m; ++i) {
		G[a[i]].push_back(b[i]);
		G[b[i]].push_back(a[i]);
	}

	bool result = true;
	for (int i = 1; i <= n; ++i) {
		if (color[i] != -1) {
			continue;
		}
		if (!dfs(i, 1)) {
			result = false;
		}
	}

	if (result) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC327D)

基本的な考え方はC++と同じです。関数の再帰呼び出し回数の上限を増やしています(2、4行目)。以下となります。

"""AtCoder Beginner Contest 327 D"""
import sys

sys.setrecursionlimit(10**6)


def dfs(v, cur_color):
    global G, color

    color[v] = cur_color
    for next_v in G[v]:
        if color[next_v] != -1:
            if color[next_v] == cur_color:
                return False
            continue
        if not dfs(next_v, 1 - cur_color):
            return False

    return True


n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
G = [[] for _ in range(n + 1)]
color = [-1] * (n + 1)
for i in range(m):
    G[a[i]].append(b[i])
    G[b[i]].append(a[i])

result = True
for i in range(1, n + 1):
    if color[i] != -1:
        continue
    if not dfs(i, 1):
        result = False

print("Yes" if result else "No")

こちらも「AC」と判定されました。

最後に

二部グラフの問題に帰着して、コンテスト中に解くことができました。類題のABC282D問題は、当時(2022年12月17日)、まったく解くことができませんでした。進歩を感じることができて良かったです。

引き続き ABC の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA