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)$ となるため、時間的に間に合いませんでした。ダイクストラ法については、知っていましたが応用ができませんでした。
公式解説を参照しながらではありますが、この問題を解くことにより、ダイクストラ法の理解が深まりました。
引き続き ABC の問題を紹介していきます。
