AtCoder が提供しているABC（AtCoder Beginner Contest）385 C問題をC++とPythonで解いてみました。ABC385は、2024年12月21日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Illuminate Buildings（Difficulty : 446）
問題の詳細は、リンク先をご覧ください。
ABC385 C問題 Illuminate Buildings
2つのビルを選び、飾る電飾を伸ばせるだけ伸ばします。AtCoder Problems による Difficulty は 446 でした。
解答案
C++ プログラム例（ABC385C）
2つの異なるビルを選びます。選んだビルの高さ h[i] と h[j] が異なれば、次の組み合わせを調べます。j-i を間隔として、同じ値が続くか調べます（19ー25行目）。
一見すると、3重ループのため、計算量が $O(N^3)$ となり、間に合わないように思えます。この場合、2番目のループ（j）が大きくなると、3番目のループ回数が減ります。例えば、j > n/2 であれば、3番目のループは1回しか実行されません（最初の条件で偽になります）。3番目のループの実行回数は、おおむね n/j 回となります。$\sum_{i=1}^N 1/i$ の値は、$\log N$ で抑えることができます。このため、この解法の計算量は、$O(N^2 \log N)$ となり間に合います。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> h(n);
for (int i = 0; i < n; ++i) {
cin >> h[i];
}
int result = 1;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (h[i] != h[j]) {
continue;
}
int diff = j - i;
int end_p = j;
int t_result = 2;
while ((end_p + diff < n) && (h[i] == h[end_p + diff])) {
end_p += diff;
++t_result;
}
result = max(result, t_result);
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC385C）
基本的な考え方は同じです。
「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。以下がプログラムです。
"""AtCoder Beginner Contest 385 C"""
n = int(input())
h = list(map(int, input().split()))
result = 1
for i in range(n):
for j in range(i + 1, n):
if h[i] != h[j]:
continue
diff = j - i
end_p = j
t_result = 2
while end_p + diff < n and h[i] == h[end_p + diff]:
end_p += diff
t_result += 1
result = max(result, t_result)
print(result)最後に
コンテスト中は、ビルの高さごとに配列に格納し、同じ高さのビル間で電飾を可能な限り伸ばす方法を取りました。この解法は、実行時間が1523msで、ぎりぎり制限時間内に収まりました（プログラムはこちら）。
この解法の妥当性について、競技プログラミングをするフレンズ様に X で質問したところ、非常に分かりやすく解説していただけました（解説はこちら）。感謝いたします。
なお、公式解説では、ビルの間隔に着目した計算量 $O(N^2)$ の解法が紹介されています。
この記事では、私のコンテスト提出プログラムに近い解法を紹介することにしました。
引き続き ABC の問題を紹介していきます。
