AtCoder が提供しているABC（AtCoder Beginner Contest）302 のC問題をC++とPythonで解いてみました。ABC302は、2023年5月20日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Almost Equal（Difficulty : 469）
問題はリンク先をご覧ください。
順列全探索を使って与えられた条件を満たす文字列の並びがあるか判定する問題です。AtCoder Problems による Difficulty は 469 でした。
解答案
文字列 S1、S2、…、SN を並べ替えて、T1、T2、…、TN として、Ti と Ti-1 の差が1文字である場合に “Yes”、そのように並べ替えることができない場合に “No” を表示します。
N が8以下です。このため、N! すべて調べる順列全探索が使えます。
C++ プログラム例（ABC302C）
C++ では、ライブラリ関数 next_permutation を使うと順列全探索が楽に実装できます。文字列が1文字差かを判断する関数を分けました（4-14行目）。
配列の添え字にするために 0 から n-1 を格納した配列を next_permutation に与えて、順列全探索を行います。
結果を格納する変数 result は、最初に true を代入して、1つでも条件を満たさない文字列の組が見つかると false にします。最後まで true であれば、解が見つかったため、ループを抜けます。すべての場合に条件を満たさない場合、result が false でループが終了します（31-41行目）。
最後に result に従い、”Yes” か “No” を出力します。以下が、C＋＋プログラムとなります。順列全探索に関する行の背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
bool check(string s1, string s2)
{
int diff = 0;
for (int i = 0; i < s1.length(); ++i) {
if (s1[i] != s2[i]) {
++diff;
}
}
return diff == 1;
}
int main()
{
int n, m;
cin >> n >> m;
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
vector<int> p(n);
for (int i = 0; i < n; ++i) {
p[i] = i;
}
bool result = true;
do {
result = true;
for (int i = 0; i < n - 1; ++i) {
if (!check(s[p[i]], s[p[i + 1]])) {
result = false;
}
}
if (result) {
break;
}
} while(next_permutation(p.begin(), p.end()));
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC302C）
基本的な考えは、C++ と同じです。Python では、itertools.permutations を使って順列全探索を行います。この関数は、すべての順列をリストを返します。
順列全探索に関する行の背景色を変更しました。
"""AtCoder Beginner Contest 302 C"""
import math
import itertools
def check(s1, s2):
diff = 0
for i in range(len(s1)):
if s1[i] != s2[i]:
diff += 1
return diff == 1
n, m = map(int, input().split())
s = [input() for i in range(n)]
num = []
for i in range(n):
num.append(i)
p = list(itertools.permutations(num))
for i in range(math.factorial(n)):
result = True
for j in range(n - 1):
if not check(s[p[i][j]], s[p[i][j + 1]]):
result = False
if result:
break
print("Yes" if result else "No")こちらも「AC」と判定されました。
最後に
本質的な考え方ではありませんが、N が10以下の場合には、順列全探索を使う場合が多いようです。
引き続き ABC の問題を紹介していきます。
