AtCoder が提供しているABC（AtCoder Beginner Contest）310 のD問題をC++とPythonで解いてみました。ABC310は、2023年7月15日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Peaceful Teams（Difficulty : 1368）
問題はリンク先をご覧ください。
DFSを用いて全探索する問題です。AtCoder Problems による Difficulty は 1368 でした。
解答案
再帰を使って全探索を行います。変数 team は、配列の配列（リストのリスト）とします。team[j] は、j 番目のチームを表す配列（リスト）となります。
再帰関数 dfs の処理は以下となります。引数 i は、i 番目のメンバを処理することを表します。
- 引数 i が n となった場合、すべての人がチームに所属した。以下の処理を行う。
- チームの数が t であれば、条件を満たすため result を増やす。
- 関数から戻る。
- 存在するチームに相性の悪い相手がいなければ、そのチームに i を加えて、次の i+1 を引数に dfs を呼び出す。dfs から戻った後は、チームから i の値を抜いて、無かったことにして、次のチームに対して処理を行う。
- 新しいチームに i を加えて、次の i+1 を引数に dfs を呼び出す。dfs から戻った後は、そのチームを無かったことにする。
チームメンバーを増やして、dfs 呼び出し後にそのチームメンバーを無かったことにして、次を調べることをバックトラックと呼ぶようです。
C++ プログラム例（ABC310D）
上記の考察に従い、関数 dfs を実装します。
main では入力を読み、相性の悪い相手を表す配列 ng を更新して、dfs を呼び出します。このプログラムのキーとなる行の背景色を変更しておきます。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int n;
int t;
int m;
vector<vector<bool>> ng(10, vector<bool>(10, false));
vector<vector<int>> team;
int result;
void dfs(int i)
{
if (i == n) {
if (team.size() == t) {
++result;
}
return;
}
for (int j = 0; j < team.size(); ++j) {
bool this_team = true;
for (auto e : team[j]) {
if (ng[e][i]) {
this_team = false;
}
}
if (this_team) {
team[j].push_back(i);
dfs(i + 1);
team[j].pop_back();
}
}
team.push_back(vector<int>(1, i));
dfs(i + 1);
team.pop_back();
return;
}
int main()
{
cin >> n >> t >> m;
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
--a;
--b;
ng[a][b] = true;
ng[b][a] = true;
}
result = 0;
dfs(0);
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC310D）
C++ 版をそのまま移植しました。Python の多くの環境は、再帰関数の呼び出し回数の制限が 1000 回であるため、それを増やしています（5行目）。
"""AtCoder Beginner Contest 310 D"""
import sys
LIMIT = 10**6
sys.setrecursionlimit(LIMIT + 1)
def dfs(i):
global n
global t
global ng
global team
global result
if i == n:
if len(team) == t:
result += 1
return
for j in range(len(team)):
this_team = True
for e in team[j]:
if ng[e][i]:
this_team = False
if this_team:
team[j].append(i)
dfs(i + 1)
team[j].pop(-1)
team.append([i])
dfs(i + 1)
team.pop(-1)
return
n, t, m = map(int, input().split())
ng = [[False for i in range(n)] for j in range(n)]
for i in range(m):
a, b = map(int, input().split())
a -= 1
b -= 1
ng[a][b] = True
ng[b][a] = True
team = []
result = 0
dfs(0)
print(result)こちらも「AC」と判定されました。
最後に
この問題は、コンテスト中に解くことができませんでした。公式解説を参考にして解いてみました。自分でプログラムをすることにより、DFS を使った全探索について、理解を深めることができました。
引き続き ABC の問題を紹介していきます。
