AtCoder が提供しているABC（AtCoder Beginner Contest）302 のE問題をC++とPythonで解いてみました。ABC302は、2023年5月20日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Isolation（Difficulty : 988）
問題はリンク先をご覧ください。
コンテナをうまく使って状況を更新していく問題です。AtCoder Problems による Difficulty は 988 でした。
解答案
各頂点と結ばれている頂点の集合を set で表します。グラフの場合、vector を使うことが多いですが、今回の問題では結ばれている頂点を削除することがあるため、$O(\log)$ で削除できる set を使いました。
C++ プログラム例（ABC302E）
頂点 i と結ばれている頂点を s[i] とします。問題で求められている「他のどの頂点とも辺で結ばれていない頂点」を set コンテナ iso とします。
- iso の初期値として、1 から N までを insert しておきます。
- クエリ1 の場合、s[u] と s[v] を更新して、iso から u と v を除きます。
- クエリ2 の場合、v と結ばれている頂点から v を除きます。v を除いた結果、孤立した場合は、iso に加えます。v の頂点を初期化して、v を iso に加えます。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<set<int>> s(n + 1);
set<int> iso;
for (int i = 1; i <= n; ++i) {
iso.insert(i);
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int type;
cin >> type;
if (type == 1) {
int u, v;
cin >> u >> v;
s[u].insert(v);
s[v].insert(u);
iso.erase(u);
iso.erase(v);
} else if (type == 2) {
int v;
cin >> v;
for (auto e : s[v]) {
s[e].erase(v);
if (s[e].size() == 0) {
iso.insert(e);
}
}
s[v].clear();
iso.insert(v);
}
cout << iso.size() << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC302E）
C++ をそのまま移植したため、Python らしい書き方ではないかもしれません。また効率も十分ではなく、Pyhon (3.8.2) ではTLEとなりました。PyPy3 (7.3.0) では、AC 判定となります。
"""AtCoder Beginner Contest 302 E"""
n, q = map(int, input().split())
s = [set() for _ in range(n + 1)]
iso = set()
for i in range(1, n + 1):
iso.add(i)
for i in range(q):
query = list(map(int, input().split()))
if query[0] == 1:
u = query[1]
v = query[2]
s[u].add(v)
s[v].add(u)
iso.discard(u)
iso.discard(v)
elif query[0] == 2:
v = query[1]
for e in s[v]:
s[e].discard(v)
if len(s[e]) == 0:
iso.add(e)
s[v].clear()
iso.add(v)
print(len(iso))最後に
この問題は、コンテスト中は時間がなく解くことができませんでした。コンテスト終了後にコンテナを工夫すれば解けることが分かり、この記事で解説しました。
引き続き ABC の問題を紹介していきます。
