AtCoder

ABC284 E問題（Count Simple Paths）を解く

 
AtCoder_ABC284_E

AtCoder が提供しているABC（AtCoder Beginner Contest）284 のE問題をC++とPythonで解いてみました。ABC284は、2023年1月7日21:00に実施されました。

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

目次
  1. E問題 Count Simple Paths（Difficulty : 1043）
  2. 解答案
  3. 最後に

E問題 Count Simple Paths（Difficulty : 1043）

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

ABC284 E問題 Count Simple Paths

グラフの単純パスをカウントする問題です。AtCoder Problems による Difficulty は、1043 でした。

解答案

考察

以下、公式解説を参考にしました。

入力例2の場合、グラフは以下となります。

ABC284E Ex2

1 を始点とする単純パスは、以下の16個となります。

  • 1
    • 1-2
      • 1-2-3
        • 1-2-3-4
      • 1-2-4
        • 1-2-4-3
    • 1-3
      • 1-3-2
        • 1-3-2-4
      • 1-3-4
        • 1-3-4-2
    • 1-4
      • 1-4-2
        • 1-4-2-3
      • 1-4-3
        • 1-4-3-2

以下は、グラフを探索する dfs の基本的な実装です。

void dfs(int v)
{
	seen[v] = true;
	for (auto next_v : e[v]) {
		if (!seen[next_v]) {
			dfs(next_v);
		}
	}
}

この場合、一度通った頂点は2度と通りません。

書きだした単純パスを見てみると「自分を通った後は、自分にはたどり着いて欲しくない（単純パスの定義から）、一方、自分から親に戻った場合は、再び自分にたどり着くのは構わない」ことが分かります。

つまり、関数を抜ける前に、seen を false に戻す、dfs が呼び出される毎に単純パスの個数を増やせばよいことが分かりました。以下となります。

void dfs(int v)
{
	seen[v] = true;
	++result;
	for (auto next_v : e[v]) {
		if (!seen[next_v]) {
			dfs(next_v);
		}
	}
	seen[v] = false;
}

これだけの違いですが、単純パスの個数をカウントすることができました。

パス個数の上限を 106 としています。このため、上限に達すれば、上限値を出力してプログラムを抜けます。dfs の呼び出しは、106 回を超えることはないため、計算量としても間に合います。

余談ですが、入力例3の単純パス数が2023になっていました。参加者に楽しんでもらおうと工夫されたのだと思います。

C++ プログラム例（ABC284E）

上記で考察した dfs に上限値の処理を加えました。上限値に達したときは、exit しています。一般的には、再帰呼び出しの深いところでプログラム終了するのは、乱暴です。ただし、そのまま dfs を return する場合、本当に計算時間が収まるのか、自信がなく exit しました。

2023/01/13追記
公式解説動画に解説がありました。問題の制約に「入力で与えられるグラフの頂点の次数はすべて 10 以下」とありました。このため、dfs の呼び出し回数は、106 × 10 = 107 が上限になります。変数 result のインクリメントを if 文の後ろに移して、if 文で return する方が、問題の制約も活かしたプログラムになります。
競技プログラミングの解答として、システム関数である exit を呼び出しているのは、よろしくないのですが、自分の記録としてコードは修正しないで残しておきます。（exit しているのは、かっこう悪いですが間違いではないこともあります。）

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

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

#define N 200001
vector<vector<int>> e(N);
vector<bool> seen(N, false);

#define LIMIT 1000000
int result;

void dfs(int v)
{
	seen[v] = true;
	++result;
	if (result >= LIMIT) {
		cout << LIMIT << endl;
		exit(0);
	}
	for (auto next_v : e[v]) {
		if (!seen[next_v]) {
			dfs(next_v);
		}
	}
	seen[v] = false;
}

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}

	result = 0;
	dfs(1);
	cout << result << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC284E）

Python は、C++をそのまま移植しました。再帰関数の呼び出し回数の上限を増やすために sys.setrecursionlimit を呼び出しています（5行目）。また、プログラムを抜けるために、sys.exit を呼び出しています（14行目）。

"""AtCoder Beginner Contest 284 E"""
import sys

LIMIT = 10**6
sys.setrecursionlimit(LIMIT + 1)


def dfs(v):
    global result
    seen[v] = True
    result += 1
    if result >= LIMIT:
        print(LIMIT)
        sys.exit(0)
    for next_v in e[v]:
        if not seen[next_v]:
            dfs(next_v)
    seen[v] = False


n, m = map(int, input().split())
e = [[] for i in range(n + 1)]
seen = [False] * (n + 1)
for i in range(m):
    u, v = map(int, input().split())
    e[u].append(v)
    e[v].append(u)

result = 0
dfs(1)
print(result)

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

最後に

ABC284は、A問題から順番に解いて、38:32にD問題でAC判定をもらいました。

その後、E問題と60分格闘しました。DFS を使って解いたABC284 C問題と似た構造になることは分かり、dfs が呼び出されると単純パス（同じ頂点を複数回通らないパス）が1増えることは分かりましたが、コンテスト中には解けませんでした。

結果的にE問題は解けませんでしたが、考えた分、公式解説に納得することができました。感動に似た驚きもありました。

E問題の解説は初めてとなりますが、理解が深まったと考えています。

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

ABC E問題 C++ DFS Python グラフ プログラミング 難易度:緑
関連記事はこちら

COMMENT

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

CAPTCHA