AtCoder が提供しているABC（AtCoder Beginner Contest）388 C問題をC++とPythonで解いてみました。ABC388は、2025年1月11日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Various Kagamimochi（Difficulty : 211）
問題の詳細は、リンク先をご覧ください。
ABC388 C問題 Various Kagamimochi
それぞれの餅の半分以下の大きさの餅の総数を求めます。AtCoder Problems による Difficulty は 211 でした。
解答案
ABC077C問題の解説記事で二分探索についてまとめました。再び掲載します。
C++ の二分探索を行う lower_bound、upper_bound の動作
| 求めたい要素数 | コード |
| x 未満の配列 a の要素数 | lower_bound(a.begin(), a.end(), x) - a.begin() |
| x 以下の配列 a の要素数 | upper_bound(a.begin(), a.end(), x) - a.begin() |
| x を超える配列 a の要素数 | a.end() - upper_bound(a.begin(), a.end(), x); |
| x 以上の配列 a の要素数 | a.end() - lower_bound(a.begin(), a.end(), x); |
C++ プログラム例（ABC388C）
ある餅に対して、その半分以下の大きさの餅の数は upper_bound で求めることができます。その総和を出力するだけです。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
ll result = 0;
for (int i = 0; i < n; ++i) {
result += upper_bound(a.begin(), a.end(), a[i] / 2) - a.begin();
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC388C）
Python版も基本的な考え方は同じです。二分探索は、bisect.bisect_right を使いました。以下がプログラムです。
"""AtCoder Beginner Contest 388 C"""
import bisect
n = int(input())
a = list(map(int, input().split()))
result = 0
for i in range(n):
result += bisect.bisect_right(a, a[i] // 2)
print(result)こちらも「AC」と判定されました。
最後に
今回のコンテストは、C問題を11分26秒で解くことができました。ただし、それから90分近くD問題とE問題と格闘するだけでしたが。
引き続き ABC の問題を紹介していきます。
