AtCoder

ABC277 C問題(Ladder Takahashi)を解く

AtCoder_ABC277_C

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

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

C問題 Ladder Takahashi(Difficulty : 540)

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

ABC277 C問題 Ladder Takahashi

ビルの階数の問題ですが、グラフを使って解きます。AtCoder Problems による Difficulty は、540 でした。ABC C問題として、やや難しい問題です。

解答案

問題を解く方針を書きだします。

  • 階を頂点、はしごを辺と考えて、グラフとして読み込む。
  • 1階と連結しているもっとも高い階を探索する。
  • 結果を出力する。

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

グラフの表現については、こちらで解説しました。今回は、頂点の範囲が $1 \leqq$ 頂点 $\leqq 10^9$ であるため、map を使ってグラフを表現します。

1階と連結している頂点は、DFS(深さ優先探索:Depth-First-Search)で探索します。探索には、BFS(幅優先探索:Breadth-First-Search)を使ってもよいです。一般的に BFS では、キューを使います。

以下は、DFS を再帰関数として実装しました。解(もっとも高い階)を result として保持しています。より高い階に至れば、result を更新します。最後に result を出力します。

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

map<int, vector<int>> e;
map<int, bool> seen;

int result = 1;

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

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

	dfs(1);

	cout << result << endl;

	return 0;
}

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

Python プログラム例(ABC277C)

2022年11月28日
当初、Python 版は、RE(Runtime Error)と判定されるテストケースが出ました。理由が分からず紹介していませんでした。理由が判明したため、以下を追記します。

最初に RE(Runtime Error)と判定されたプログラムを紹介します。基本的に C++ 版の移植です。

"""AtCoder Beginner Contest 277 C"""
from collections import defaultdict


def dfs(v):
    seen[v] = True
    result.append(v)
    for next_v in e[v]:
        if not seen[next_v]:
            dfs(next_v)


e = defaultdict(list)
seen = defaultdict(lambda: False)
result = [1]
n = int(input())
for i in range(n):
    a, b = map(int, input().split())
    e[a].append(b)
    e[b].append(a)

dfs(1)
print(max(result))

RE と判定される理由は、再帰呼び出しの上限回数を超えていたためです。この事情は、問題269 D問題でも紹介していました。

この問題の場合、$1 \leqq N \leqq 2 \times 10^5$ の数だけ、再帰関数が呼び出される可能性があります(すべての階段を通る場合です)。

sys.setrecursionlimit によって再帰呼び出しの上限回数を増やします。この文を追加して、すべてのテストケースで動作するようになりました。

"""AtCoder Beginner Contest 277 C"""
from sys import setrecursionlimit
from collections import defaultdict

setrecursionlimit(200001)


def dfs(v):
    seen[v] = True
    result.append(v)
    for next_v in e[v]:
        if not seen[next_v]:
            dfs(next_v)


e = defaultdict(list)
seen = defaultdict(lambda: False)
result = [1]
n = int(input())
for i in range(n):
    a, b = map(int, input().split())
    e[a].append(b)
    e[b].append(a)

dfs(1)
print(max(result))

このプログラムは「AC」と判定されました。

最後に

グラフに関係する問題も、いくつか解いているとプログラミングに慣れてきました。今は、グラフの連結している頂点の探索は、(BFSが使える場合も)DFS に決めています。このため、DFS の理解が深まってきたと感じています。

ABC277 のD問題は、今のわたしには難しく感じました。このためC問題までの解説としました。

引き続き ABC を解いていきます。

COMMENT

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

CAPTCHA