AtCoder が提供しているABC（AtCoder Beginner Contest）333 のD問題をC++とPythonで解いてみました。ABC333は、2023年12月16日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Erase Leaves（Difficulty : 704）
問題はリンク先をご覧ください。
頂点1の子の子孫の個数を計算して最大の個数を抜いて加えます。AtCoder Problems による Difficulty は 704 でした。
解答案
以下の方針で計算します。
- 頂点1を根とする。
- 頂点1の子（頂点1を親とする頂点）の子孫となる頂点の個数を求める。子自体も子孫の個数に含める。
- 操作の回数として、子孫の個数が小さい方から加えていく。一番大きな子孫を持つ子は、残りを削除すると頂点１が葉となるため、削除する必要がない。
- 最後に頂点1を削除する操作の回数として1を加える。
結果的に頂点1が最初から葉になっている場合（入力例2）は、1を出力することになります。
C++ プログラム例（ABC333D）
コードの多くは、グラフ（木）に対してDFSで全探索をする場合の定番コードとなっています。以下は補足です。
- 関数 dfs は、自分を含む子孫の頂点の個数を返します（8、11行目）。
- 配列 child に頂点1の子の子孫の頂点の個数を格納します（32行目）。
- 配列 child の一番大きな値を除いて加えます（36ー39行目）。
- 最後の1を足して出力します（41行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
int dfs(int v, int par)
{
int result = 1;
for (auto next_v : G[v]) {
if (next_v != par) {
result += dfs(next_v, v);
}
}
return result;
}
int main()
{
int n;
cin >> n;
G.resize(n + 1);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> child;
for (auto next_v : G[1]) {
child.push_back(dfs(next_v, 1));
}
sort(child.begin(), child.end());
int result = 0;
for (int i = 0; i < child.size() - 1; ++i) {
result += child[i];
}
cout << 1 + result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC333D）
Python 版の補足です。
- 再帰関数の呼出回数を増やしています（2、4行目）。
- 最後の出力は、スライス記法と組込み関数 sum で1行で書けました（30行目）。
"""AtCoder Beginner Contest 333 D"""
import sys
sys.setrecursionlimit(10**6)
def dfs(v, par):
global G
result = 1
for next_v in G[v]:
if next_v != par:
result += dfs(next_v, v)
return result
n = int(input())
G = [[] for _ in range(n + 1)]
for i in range(n - 1):
u, v = map(int, input().split())
G[u].append(v)
G[v].append(u)
child = []
for next_v in G[1]:
child.append(dfs(next_v, 1))
child.sort()
print(1 + sum(child[:len(child) - 1]))こちらも「AC」と判定されました。
最後に
DFS を使い子孫の数を求めました。コンテスト中にも解くことができて、うれしく感じました。
引き続き ABC の問題を紹介していきます。
