AtCoder が提供しているABC（AtCoder Beginner Contest）381 D問題をC++とPythonで解いてみました。ABC381は、2024年11月22日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 1122 Substring（Difficulty : 921）
問題の詳細は、リンク先をご覧ください。
偶数番目と奇数番目の位置から2文字ずつ調べました。AtCoder Problems による Difficulty は 921 でした。
解答案
C++ プログラム例（ABC381D）
2文字ずつ調べます。文字列の先頭からと次の文字からで2回調べます（14行目）。
- a[i] と a[i+1] が同じであれば、調べている1122文字列の長さを伸ばすことができます。ただし、同じ数字は2回以上現れてはいけません。
- 数字の重複を確認するために map を使います。すでに出現している数字であれば、その数字以降の長さを1122文字列の長さとします（22行目）。
- すでに出現している数字でも、いま調べている1122文字列の長さに影響がない場合もあります。その数字が対象としている1122文字列に含まれていない場合です（19行目右側の条件）。
- map の値を更新します（24行目）。
- a[i] と a[i+1] が異なっていれば、調べていた1122文字列の長さを0にします（26、27行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int result = 0;
for (int start = 0; start <= 1; ++start) {
int t_result = 0;
map<int, int> m;
for (int i = start; i + 1 < n; i += 2) {
if (a[i] == a[i + 1]) {
if ((m.find(a[i]) == m.end()) || (i - t_result > m[a[i]])) {
t_result += 2;
} else {
t_result = i - m[a[i]];
}
m[a[i]] = i;
} else {
t_result = 0;
m.clear();
}
result = max(result, t_result);
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC381D）
Python版も基本的な考え方は同じです。C++の map の代わりに Python の辞書を使用しました。以下がプログラムです。
"""AtCoder Beginner Contest 381 D"""
n = int(input())
a = list(map(int, input().split()))
result = 0
for start in range(2):
t_result = 0
m = {}
for i in range(start, n, 2):
if i + 1 >= n:
continue
if a[i] == a[i + 1]:
if a[i] not in m or i - t_result > m[a[i]]:
t_result += 2
else:
t_result = i - m[a[i]]
m[a[i]] = i
else:
t_result = 0
m.clear()
result = max(result, t_result)
print(result)こちらも「AC」と判定されました。
最後に
公式解説の解法1の補足にある「なお、C++ の std::map などのデータ構造を使うことで $O(N \log N)$ で解くこともできます」のプログラムだと思われます。尺取法（解法1）よりもこちらの方が分かりやすく、記事で紹介することにしました。
引き続き ABC の問題を紹介していきます。
