AtCoder が提供しているABC（AtCoder Beginner Contest）375 D問題をC++とPythonで解いてみました。ABC375は、2024年10月12日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 ABA（Difficulty : 658）
問題の詳細は、リンク先をご覧ください。
それぞれの文字の場所を記録して、2つの同じ文字に挟まれた回文の数を計算します。AtCoder Problems による Difficulty は 658 でした。
解答案
‘A’ から ‘Z’ までの出現場所を配列 a に格納します。以下の2つに場合分けします。
- 同じ文字が3つ続く回文（例 “AAA”）の数は、ある文字の頻度を $tn$ とすると、
$(tn \times (tn – 1) \times (tn – 2)) / 6$ 通りとなります（$tn$ 個から3個とる組み合わせの数です）。 - ある文字に異なる文字が挟まれている回文の数は、以下のように考えます。
- 入力例1 “ABCACC” の文字 ‘C’ に注目します。
- ‘C’ がある場所は、{3, 5, 6} となります。
- 3番目の次にある4番目の文字は、文字 ‘C’ ではない。
- それより前にある ‘C’ の数は1個ある。
- それより後ろにある ‘C’ の数は2個ある。
- 4番目の文字 ‘A’ を挟む “CAC” の回文の数は、$1 \times 2 = 2$ となります。
- それ以降は、”C*C” となる回文となる場合はありません。
C++ プログラム例（ABC375D）
上記の考え方をプログラムとして実装します。
- 文字別の頻度をカウントします（11－14行目）。
- 同じ文字が3つ続く回文の数を計算します（22行目）。
- 同じ文字に挟まれる回文の数を計算します（23ー30行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
string s;
cin >> s;
int n = s.length();
vector<vector<int>> a(26);
for (int i = 0; i < n; ++i) {
a[s[i] - 'A'].push_back(i);
}
ll result = 0;
for (int i = 0; i < 26; ++i) {
ll tn = a[i].size();
if (tn <= 1LL) {
continue;
}
result += tn * (tn - 1LL) * (tn - 2LL) / 6LL;
ll ti = 1LL;
for (int j = a[i][0] + 1; j < a[i][tn - 1]; ++j) {
if (j != a[i][ti]) {
result += (tn - ti) * ti;
} else {
++ti;
}
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC375D）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 375 D"""
s = input()
n = len(s)
a = [[] for _ in range(26)]
for i, ch in enumerate(s):
a[ord(ch) - ord('A')].append(i)
result = 0
for i in range(26):
tn = len(a[i])
if tn <= 1:
continue
result += tn * (tn - 1) * (tn - 2) // 6
ti = 1
for j in range(a[i][0] + 1, a[i][tn - 1]):
if j != a[i][ti]:
result += (tn - ti) * ti
else:
ti += 1
print(result)こちらも「AC」と判定されました。
最後に
ABC373からABC375は、（わたしの実力では）E問題以降の難易度が高く感じました。水色Diffの問題を解けるように少しずつ実力を上げていきたいです。
引き続き ABC の問題を紹介していきます。
