AtCoder が提供しているABC（AtCoder Beginner Contest）353 のC問題をC++とPythonで解いてみました。ABC353は、2024年5月11日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Sigma Problem（Difficulty : 795）
問題はリンク先をご覧ください。
足して1億以上となる組み合わせの数を求めます。AtCoder Problems による Difficulty は 795 でした。
解答案
$f(x, y)$ の演算で $10^8$ で割った余りを求める必要がなければ、それぞれの要素は、足し算の中に $N-1$ 回現れるため、以下の式で求めることができます。
$$\sum^{N-1}_{i=1} \sum^N_{j=i+1} A_i + A_j = (N\;-\;1) \sum^{N}_{i=1} Ai$$
$A_i + A_j$ は、$10^8$ 以上となる場合はあります。ただし、$2 \times 10^8$ 未満となります。このため、$10^8$ 以上となる組み合わせの数を求めて、それに $10^8$ を掛けて引けば求める式の値となります。
C++ プログラム例（ABC353C）
ソートして二分探索で、和が $10^8$ 以上となる組み合わせの数を求めます。
- 読み込んだ数列 a をソートします（15行目）。
- 変数 result に仮の和を代入しておきます（17ー20行目）。
- 各 a[i] に対して、加えると $10^8$ を超える要素数を求めます（24行目）。
- $10^8$ – a[i] 以上となる要素の数を求めます。
- a[i] 以降の要素の数を求めるため、a.begin() + i + 1 を開始点にしています。
- 結果は、変数 over10e8 に加えていきます。
- 最後に result から over10e8 $\times 10^8$ の値を引きます。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
#define LIMIT 100000000LL
typedef long long int ll;
int main()
{
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
ll result = 0;
for (int i = 0; i < n; ++i) {
result += a[i] * (n - 1);
}
ll over10e8 = 0;
for (int i = 0; i < n - 1; ++i) {
over10e8 += a.end() - lower_bound(a.begin() + i + 1, a.end(), LIMIT - a[i]);
}
result -= over10e8 * LIMIT;
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC353C）
基本的な考え方は同じです。以下となります。
ただし、CPython 3.11.4 でも PyPy 3.10-v7.3.12 でも TLE となりました。二分探索（bisect_left）の中で、a[i+1:] を求めています。これに $O(N)$ 時間かかることで TLE となっているようです。
TLE となるプログラムですが、Python の知識が足りないため、本記事ではここまでとします。
"""AtCoder Beginner Contest 353 C"""
import bisect
LIMIT = 10 ** 8
n = int(input())
a = list(map(int, input().split()))
a.sort()
result = sum(a) * (n - 1)
over10e8 = 0
for i in range(n - 1):
over10e8 += (n - 1 - i) - bisect.bisect_left(a[i + 1:], LIMIT - a[i])
result -= over10e8 * LIMIT
print(result)最後に
この問題は、2回WA（Wrong Answer）の後、97分2秒での提出でACとなりました。D問題の提出が31分10秒でACでしたから、1時間以上この問題と格闘していたことになります。2週続けて、茶色Diffの問題に苦戦しました（前回は、ABC352D問題）。
緑Diffは解けるようになってきました。それより低い難易度の問題を手早く解けるよう工夫する必要があります。
引き続き ABC の問題を紹介していきます。
