AtCoder が提供しているABC（AtCoder Beginner Contest）320 のB問題をC++とPythonで解いてみました。ABC320は、2023年9月16日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Longest Palindrome（Difficulty : 84）
問題はリンク先をご覧ください。
与えられた文字列が含む、もっとも長い回文の長さを求める問題です。AtCoder Problems による Difficulty は 84 でした。
解答案
C++ プログラム例（ABC320B）
与えられた文字列が回文か判定する関数 is_palindrome を実装します。文字列の先頭から比較をすることによって判定しています（4ー15行目）。
関数 main では、substr を使って文字列を切り出して、関数 is_palindrome を呼び出します（26行目）。
切り出す文字列を [i, j) となるようにループ変数を設定しています（24、25行目）。substr メソッドの第2引数には、切り出す文字列の長さとなるように j – i を与えています。書き方を、半開区間に統一しておくと、一個違い間違いを減らすことができると考えています。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
bool is_palindrome(string s)
{
bool result = true;
for (int i = 0; i < s.size() / 2; ++i) {
if (s[i] != s[s.size() - 1 - i]) {
result = false;
break;
}
}
return result;
}
int main()
{
string s;
cin >> s;
int size = s.length();
int result = 0;
for (int i = 0; i < size; ++i) {
for (int j = i + 1; j <= size; ++j) {
if (is_palindrome(s.substr(i, j - i))) {
result = max(result, j - i);
}
}
}
cout << result << endl;
return 0;
}関数 is_palindrome は、reverse を使うと、もっと簡単に書くことできます。以下が、reverse を使ったプログラムです。先に紹介したプログラムから関数 is_palindrome だけを変更しています（4ー10行目）。
#include <bits/stdc++.h>
using namespace std;
bool is_palindrome(string s)
{
string t = s;
reverse(t.begin(), t.end());
return s == t;
}
int main()
{
string s;
cin >> s;
int size = s.length();
int result = 0;
for (int i = 0; i < size; ++i) {
for (int j = i + 1; j <= size; ++j) {
if (is_palindrome(s.substr(i, j - i))) {
result = max(result, j - i);
}
}
}
cout << result << endl;
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC320B）
Python では、逆順の文字列を1行で求めることができるため、if 文の条件に記しました（8行目）。この書き方は、少し長いですが定番表現のようです。
切り出す文字列は、C++ と同じく [i, j) となるようにループを書いています。Python のスライス記法は、半開区間と相性が良いです。
"""AtCoder Beginner Contest 320 B"""
s = input()
size = len(s)
result = 0
for i in range(size):
for j in range(i + 1, size + 1):
if ''.join(list(reversed(s[i:j]))) == s[i:j]:
result = max(result, j - i)
print(result)こちらも「AC」と判定されました。
最後に
回文に関する問題は、一定の割合で出題されています。
文字列処理は、一個違い間違いやメモリアクセスの範囲外アクセスが発生しやすいですが、切り出す文字列を半開区間で表現するなどして、ミスを減らしていきたいです。
引き続き ABC の問題を紹介していきます。
