AtCoder が提供しているABC（AtCoder Beginner Contest）326 のD問題をC++で解いてみました。ABC326は、2023年10月28日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 ABC Puzzle（Difficulty : 1371）
問題はリンク先をご覧ください。
Nが小さいため、全探索できます。AtCoder Problems による Difficulty は、1371 でした。
解答案
制約から $3 \leqq N \leqq 5$ となります。$N=5$ の場合でも、’A’、’B’、’C’ と ‘.’ 2個を含む5文字の文字列は、$5 \times 4 \times 3 = 60$ 通りしかありません。この文字列の中で、特定の文字（$R$ で指定された文字）で始まるものは、20通りとなります。このため、すべての行に対して、全検索しても $20^5=3.2\times 10^6$ 通りとなります。
$N$ 重ループの実装は、再帰関数を使います。引数として呼び出しの深さを渡します。本体からは、引数0で呼び出します。引数が$N$と一致すれば、列について以下の2つの条件を満たすか確認します。
- それぞれの列が $C$ で指定された文字で始まっているか。
- 文字列が、’A’、’B’、’C’ と ‘.’ を含む文字列になっているか。
C++ プログラム例（ABC326D）
事前の準備として、それぞれの行の候補となる文字列の配列 s を求めておきます。文字列 “..ABC”（$N=5$ の場合）に対して next_permutation を使って、候補文字列を生成します。最初の文字で分けて格納します。具体的には、s[0] には、’A’ で始まる文字列を格納します。s[1] には、’B’ で始まる文字列を、s[2] には、’C’ で始まる文字列を格納します（49ー66行目のプログラム）。
再帰関数では、前述の列の条件を満たさなければ、return します（21、28行目）。
それぞれの行は、始まる文字列の配列から選びます。次の行を決めるために dfs 自身を呼び出します。戻ってきたら、選んだ文字列を無かったことにして、次の文字列を調べます。この探索方法をバックトラックと呼びます（39ー41行目）。
解が見つかれば、その解を出力して終了します。このため、関数 dfs から戻ってきた場合は、”No” を出力します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int n;
string r, c;
vector<vector<string>> s(3);
vector<string> a;
string p_original;
void dfs(int depth)
{
if (depth == n) {
for (int j = 0; j < n; ++j) {
string t = "";
bool is_first = true;
for (int i = 0; i < n; ++i) {
t += a[i][j];
if (is_first &&(a[i][j] != '.')) {
if (a[i][j] != c[j]) {
return;
}
is_first = false;
}
}
sort(t.begin(), t.end());
if (p_original != t) {
return;
}
}
cout << "Yes" << endl;
for (int i = 0; i < n; ++i) {
cout << a[i] << endl;
}
exit(0);
}
for (int i = 0; i < s[r[depth] - 'A'].size(); ++i) {
a.push_back(s[r[depth] - 'A'][i]);
dfs(depth + 1);
a.pop_back();
}
}
int main()
{
cin >> n >> r >> c;
string p = "";
for (int i = 0; i < n; ++i) {
if (i < 3) {
p += 'A' + i;
} else {
p += '.';
}
}
sort(p.begin(), p.end());
p_original = p;
do {
for (int i = 0; i < n; ++i) {
if (p[i] != '.') {
s[p[i] - 'A'].push_back(p);
break;
}
}
} while (next_permutation(p.begin(), p.end()));
dfs(0);
cout << "No" << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python の順列生成について
Python の itertools.permutations は、同じ文字を区別します。このため、候補の文字列は、40通りとなります。$40^5 \doteqdot 10^8$ となり、確認するコストを考えると間に合いません。同じ文字を区別しない permutations を実装することが面倒に感じたため、この記事では、Python に移植したプログラムの紹介を省略します。
最後に
$N$ 重のループを再帰関数で実装しました。この問題の Difficulty は、1371 でした。やっていることは全探索です。ABC310D問題（解説記事）でも再帰で繰り返しを実現していますが、Difficulty は、1368 でした。
少なくない人が再帰関数による繰り返しの実装を苦手にしているのかもしれません。このような手法は、差別化にもつながるため習得していきたいです。
引き続き ABC の問題を紹介していきます。
