AtCoder が提供しているABC（AtCoder Beginner Contest）295 のD問題をC++とPythonで解いてみました。ABC295は、2023年3月25日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Three Days Ago（Difficulty : 939）
問題はリンク先をご覧ください。
数字が表れる頻度回数のパリティを使って解くことができました。AtCoder Problems による Difficulty は 939 でした。
解答案
コンテスト中には、TLE（Time Limit Exceeded）判定のプログラムしか書くことができませんでした。
基本的な考え方は、以下です。
- 0から9が現れる頻度回数を求めるために累積和を求める（10-16行目）。
- 区間 [left, right) において、0から9が現れる回数がすべて偶数の場合に [left, right) は、「嬉しい列」となります（22-30行目）。
- すべての区間について調べて、「嬉しい列」の個数を出力する（34行目）。
以下のプログラムは、3つある入力例に対して、すべて正しい解答を出力しました。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
string s;
cin >> s;
vector<vector<int>> sum(10, vector<int>(s.length() + 1, 0));
for (int i = 0; i < s.length(); ++i) {
int temp = s[i] - '0';
for (int j = 0; j < 10; ++j) {
sum[j][i + 1] = sum[j][i] + (j == temp);
}
}
ull result = 0;
for (int left = 0; left < s.length(); ++left) {
for (int right = left + 2; right <= s.length(); right += 2) {
bool happy = true;
for (int i = 0; i < 10; ++i) {
if ((sum[i][right] - sum[i][left]) % 2 != 0) {
happy = false;
break;
}
}
if (happy) {
++result;
}
}
}
cout << result << endl;
return 0;
}制約から文字列 S の長さの最大値は、5 × 105 です。計算量は、文字列の長さの2乗になるため、25 × 1010 となります。確かに間に合いません（108 程度が上限）。
パリティを使った改善版
以下は、公式解説を参考にしました。
結局、累積和を使って、[left, right) において、0から9が現れる回数がすべて偶数であることを確認していました。この場合、具体的な頻度の回数ではなく、パリティ（偶数で0、奇数で1となるビット）さえ分かれば判断ができます。パリティは各数字で1ビットなので、0から9までの数字の出現頻度を10ビットのパリティ（0から1023）で表現できます。
それぞれの数字列の数字 s[i] について、10ビットパリティ p[i] が対応します。このとき、p[i] = p[j] が成り立てば、[i, j) が「嬉しい列」となります。
「嬉しい列」の組み合わせの数は、p[i] として現れる10ビットパリティの頻度をカウントすれば、計算可能です。
C++ プログラム例（ABC295D）
上で考察したことをプログラムに変換しました。p[i + 1] は、p[i] から 1 ビットしか変化しません。これは s[i] が表す数字のパリティが反転するだけです（17行目）。
10ビットパリティの頻度は map コンテナ m でカウントします（14、18行目）。最終的には、m の頻度から解答を求めています（23行目）。
最終的な、C++ プログラムは以下となります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
string s;
cin >> s;
vector<int> p(s.length() + 1);
p[0] = 0;
map<int, ull> m;
++m[p[0]];
for (int i = 0; i < s.length(); ++i) {
int num = s[i] - '0';
p[i + 1] = p[i] ^ (1 << num);
++m[p[i + 1]];
}
ull result = 0;
for (auto e : m) {
result += e.second * (e.second - 1) / 2;
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC295D）
Python では、defaultdict を使いました。C++ のプログラムを移植しました。
"""AtCoder Beginner Contest 295 D"""
from collections import defaultdict
s = input()
p = [0] * (len(s) + 1)
p[0] = 0
m = defaultdict(int)
m[p[0]] += 1
for i, ch in enumerate(s):
num = int(ch)
p[i + 1] = p[i] ^ (1 << num)
m[p[i + 1]] += 1
result = 0
for v in m.values():
result += v * (v - 1) // 2
print(result)こちらも「AC」と判定されました。
最後に
コンテストで提出したプログラムは、時間が間に合いませんでしたが、累積和を使って、区間に入っている個数が2で割り切れるかを確認することはできていました。
公式解説で、パリティに注目すれば解けることが分かりました。元の累積和のプログラムよりもすっきり書けました。勉強になりました。
引き続き ABC の問題を紹介していきます。
