AtCoder が提供しているABC（AtCoder Beginner Contest）363 C問題をC++とPythonで解いてみました。ABC363は、2024年7月20日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Avoid K Palindrome 2（Difficulty : 602）
問題の詳細は、リンク先をご覧ください。
ABC363 C問題 Avoid K Palindrome 2
順列全探索で文字列を組み立て、回文がないか確認します。AtCoder Problems による Difficulty は 602 でした。
解答案
文字列の長さの上限が10文字です。順列全探索で並び替えて得られるすべての文字列は最大 $10! = 3628800$ 通りです。これに長さ $K$ 文字の回文が含まれているか確認するために、大雑把に見積もり $10 \times 10$ 回の比較が必要となります。合わせて計算量は、$3.6 \times 10^8$ 程度となり、（余裕はありませんが）間に合います。
C++ プログラム例（ABC363C）
標準ライブラリの関数 next_permutation を使って、文字列を並べ替えます。並べ替えた文字列に長さ $K$ 文字の回文が含まれていない場合に、set コンテナ result に格納します。
最後に result の大きさを出力します。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
string s;
cin >> s;
sort(s.begin(), s.end());
set<string> result;
do {
bool is_ok = true;
for (int i = 0; i + k - 1 < n; ++i) {
string t1 = s.substr(i, k);
string t2 = t1;
reverse(t1.begin(), t1.end());
if (t1 == t2) {
is_ok = false;
}
}
if (is_ok) {
result.insert(s);
}
} while (next_permutation(s.begin(), s.end()));
cout << result.size() << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC363C）
Python版も基本的な考え方は同じです。以下がプログラムです。残念ながら、CPython 3.11.4 でも PyPy 3.10-v7.3.12 でも TLE 判定となります。
"""AtCoder Beginner Contest 363 C"""
import itertools
n, k = map(int, input().split())
s = input()
result = set()
for t in itertools.permutations(s):
for i in range(n - k + 1):
t1 = t[i:i + k]
t2 = t1[::-1]
if t1 == t2:
break
else:
result.add(t)
print(len(result))標準ライブラリではありませんが、more_itertools.distinct_permutations という関数が提供されています（PyPy 3.10-v7.3.12 で使うことができました）。この関数で重複がない並べ変えた文字列を得ることができます。このため、set を使う必要がありません。以下がプログラムとなります。
"""AtCoder Beginner Contest 363 C"""
import more_itertools
n, k = map(int, input().split())
s = input()
result = 0
for t in more_itertools.distinct_permutations(s):
for i in range(n - k + 1):
t1 = t[i:i + k]
t2 = t1[::-1]
if t1 == t2:
break
else:
result += 1
print(result)こちらは「AC」と判定されました。
最後に
この問題に関しては、Python は不利だったかもしれません。
引き続き ABC の問題を紹介していきます。
