AtCoder が提供しているABC（AtCoder Beginner Contest）365 C問題をC++とPythonで解いてみました。ABC365は、2024年8月3日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Transportation Expenses（Difficulty : 269）
問題の詳細は、リンク先をご覧ください。
ABC365 C問題 Transportation Expenses
解の二分探索で、交通費補助の上限額の最適値を求めます。AtCoder Problems による Difficulty は 269 でした。
解答案
交通費補助の上限額が低いと予算が余る可能性があります。逆に、交通補助の上限額を高くすると予算が足りなくなる可能性があります。
上限額は、解の二分探索で求めることができます。タグ付けしている記事も参考にしてください。
C++ プログラム例（ABC365C）
交通費の総和が予算以下の場合には、”infinite” を出力して終了します（21ー24行目）。
めぐる式と呼ばれる二分探索の実装を参考にしています。
判断をする関数は、埋め込みました（30ー32行目）。判断をするために、交通費をソートして累積和を求めています。二分探索で調べる変数 mid 未満の個数を u とします。上限値未満の交通費の金額は累積和 s(u) となります。上限を超えた交通費補助の金額は、(n – u) × mid となります（31行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
ll m;
cin >> n >> m;
vector<ll> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
vector<ll> s(n + 1, 0);
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + a[i];
}
if (s[n] <= m) {
cout << "infinite" << endl;
return 0;
}
ll ng = m + 1;
ll ok = 0;
while (abs(ok - ng) > 1) {
ll mid = (ok + ng) / 2;
int u = lower_bound(a.begin(), a.end(), mid) - a.begin();
ll cost = (n - u) * mid + s[u];
if (cost <= m) {
ok = mid;
} else {
ng = mid;
}
}
cout << ok << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC365C）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 365 C"""
import sys
import bisect
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
s = [0] * (n + 1)
for i in range(n):
s[i + 1] = s[i] + a[i]
if s[n] <= m:
print("infinite")
sys.exit()
ng = m + 1
ok = 0
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
u = bisect.bisect_left(a, mid)
cost = (n - u) * mid + s[u]
if cost <= m:
ok = mid
else:
ng = mid
print(ok)こちらも「AC」と判定されました。
最後に
解の二分探索を使う問題でしたが、Difficulty は 269 でした。茶色Diff（Diffculty 400以上）の難易度となっても不思議ではないです。AtCoder 参加者の実力が高いことが分かります。
引き続き ABC の問題を紹介していきます。
