AtCoder

ABC305 E問題(Art Gallery on Graph)を解く

AtCoder_ABC305_E

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

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

E問題 Art Gallery on Graph(Difficulty : 1158)

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

ABC305 E問題 Art Gallery on Graph

ダイクストラ法の考え方を適用して解くことができます。AtCoder Problems による Difficulty は 1158 でした。

解答案

この問題は、各頂点から警備員がいる頂点までの距離を求めて、条件を満たすか判定する解法は、明らかに計算時間が間に合いません。

また、警備員がいる頂点から体力 hi を考慮して、距離を求める解法も計算量が $O(N^2)$ となるため間に合いません。

以下で紹介するダイクストラ法と同じ考え方が使えます。

ダイクストラ(Dijkstra)法とは

ダイクストラ法は、グラフのある頂点からすべての2頂点間の最短経路を求めるアルゴリズムです。

アルゴリズムのポイントは、「登録された距離が最小である頂点から処理していく」ことにあります。この処理のために優先度付きキューを使う場合が多いようです。この問題は、「警備員の体力が多い頂点から処理していく」と読み替えてアルゴリズムを適用します。

ダイクストラ法については、書籍でもネット上でも説明を見つけることができるため、本記事の記述は以上とします。

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

優先度付きキュー priority_queue を使います。通常のダイクストラ法では、距離が最小の値から取り出すため、テンプレートの第3引数を指定しますが、この問題は最大の値から取り出すため、テンプレートの第1引数だけ指定します(21行目)。

以下のように処理をしていきます。

  • グラフを定義する(12-19行目)。
  • 優先度付きキュー que に(警備員の体力、頂点)を登録する(21ー27行目)。
  • キューにデータが残っている場合、以下を行う(29-42行目)。
    • キューから値を取り出す(警備員の体力が一番大きな頂点を取り出す)。
    • その頂点の警備員の体力が(更新されて)大きい場合は、次のキューの処理を行う。
    • その頂点と連結している頂点に対して、更新した警備員の体力が大きくなる場合
      • その頂点の警備員の体力を更新する。
      • que にその(更新した警備員の体力、頂点)を登録する

配列 guard の初期値 -1 が更新されていれば、それは警備されている頂点になるため、その頂点を配列 result に格納して出力します。

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

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

vector<vector<int>> G;
vector<int> guard;

int main()
{
	int n, m, k;
	cin >> n >> m >> k;

	G.resize(n + 1);
	guard.assign(n + 1, -1);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	priority_queue<pair<int, int>> que;
	for (int i = 0; i < k; ++i) {
		int p, h;
		cin >> p >> h;
		guard[p] = h;
		que.push(make_pair(h, p));
	}

	while (!que.empty()) {
		pair<int, int> p = que.top();
		que.pop();
		int now = p.second;
		if (guard[now] > p.first) {
			continue;
		}
		for (auto next_v : G[now]) {
			if (guard[next_v] < guard[now] - 1) {
				guard[next_v] = guard[now] - 1;
				que.push(make_pair(guard[next_v], next_v));
			}
		}
	}

	vector<int> result;
	for (int i = 1; i <= n; ++i) {
		if (guard[i] >= 0) {
			result.push_back(i);
		}
	}

	cout << result.size() << endl;
	for (int i = 0; i < result.size(); ++i) {
		cout << result[i] << " \n"[i == result.size() - 1];
	}

	return 0;
}

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

Python プログラム例(ABC305E)

Python では、優先度付きキュー headq を使いました。ただし、headq は最小値を取り出すため、-1 を掛けて値を取り出しています。これにより結果的に最大値を取り出しています(16、22、27行目)。

heapq に関係する行の背景色を変更しました。

"""AtCoder Beginner Contest 305 E"""
import heapq

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

que = []
for i in range(k):
    p, h = map(int, input().split())
    guard[p] = h
    que.append((-1 * h, p))
heapq.heapify(que)

while que:
    t = heapq.heappop(que)
    now = t[1]
    if guard[now] > -1 * t[0]:
        continue
    for next_v in G[now]:
        if guard[next_v] < guard[now] - 1:
            guard[next_v] = guard[now] - 1
            heapq.heappush(que, (-1 * guard[next_v], next_v))

result = []
for i in range(1, n + 1):
    if guard[i] >= 0:
        result.append(i)

print(len(result))
print(*result)

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

最後に

警備員の体力 hi が大きい頂点から DFS を使って該当する頂点を求めました。この考え方の場合、$O(N^2)$ となるため、時間的に間に合いませんでした。ダイクストラ法については、知っていましたが応用ができませんでした。

公式解説を参照しながらではありますが、この問題を解くことにより、ダイクストラ法の理解が深まりました。

ABC305 について、引き続き問題を紹介していきます。

COMMENT

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

CAPTCHA