AtCoder が提供しているABC（AtCoder Beginner Contest）346 のC問題をC++とPythonで解いてみました。ABC346は、2024年3月23日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Σ（Difficulty : 179）
問題はリンク先をご覧ください。
与えられた範囲の自然数の和から、指定された値を引いていきます。AtCoder Problems による Difficulty は 179 でした。
解答案
$K$ 以下の自然数の和を求めて、数列に表れる数を引いていきます。同じ数字を2回以上引かないようにsetコンテナを使います。
C++ プログラム例（ABC346C）
数列から $K$ 以下の自然数を set コンテナ a に格納します（16行目）。$K$ 以下の自然数の和を求めて（20行目）、a に格納されている自然数を引いていきます。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
ll k;
cin >> n >> k;
set<ll> a;
for (int i = 0; i < n; ++i) {
ll t;
cin >> t;
if (t <= k) {
a.insert(t);
}
}
ll result = k * (k + 1) / 2;
for (auto e : a) {
result -= e;
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC346C）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 346 C"""
n, k = map(int, input().split())
a = set(list(map(int, input().split())))
result = k * (k + 1) // 2
for e in a:
if e <= k:
result -= e
print(result)こちらも「AC」と判定されました。
ただし、Python の set には注意が必要なようです。以下のユーザ解説を参考にしました。一言でまとめると、「このＣ問題のテストケースは、Python で set を使ってAC判定となるが、TLEになるようなテストケースを加えることが可能だ」ということです。
C++の set コンテナは、内部的に平衡二分探索木を使っていて、順序付きで処理ができます。一方、C++の unoredered_set と Python の set は、ハッシュを使っています。ハッシュテーブルのサイズに依存しますが、値を取り出す平均の計算量は、後者の方が良くなる場合が多いようです。ただし、多くの値が同じハッシュ値を持つ場合は、計算量が悪くなります（$O(N)$）。言語処理系のバージョンまで特定できると、それを狙ったテストケースを作ることができるようです。
ハッシュを使った連想配列（dict）については、この記事で紹介しています。
最後に
Python の set と dict については、なんとなく使っていました。コンテナの実装について考えるきっかけとなりました。
引き続き ABC の問題を紹介していきます。
