AtCoder が提供しているABC（AtCoder Beginner Contest）309 のC問題をC++とPythonで解いてみました。ABC309は、2023年7月8日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Medicine（Difficulty : 348）
問題はリンク先をご覧ください。
シミュレーションまたは解を二分探索します。AtCoder Problems による Difficulty は 348 でした。
解答案
(ai, bi) をソートして、ai が小さい方から処理すれば、結果的に状況をシミュレーションすることになります。調べるのは N 回以下となるため時間的に間に合います。
別解として、解の二分探索でも求めることができます。
C++ プログラム例（ABC309C）
(a[i], b[i]) をソートして、a[i] が小さい方から処理します。飲む薬の総和 need から b[i] を減らしていきます。need が K 以下となれば、a[i] +1 が解となります。
最初から薬の総和が need 以下の場合は、解は1となることに注意です（22－25行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
ll k;
cin >> n >> k;
vector<pair<int, ll>> p;
vector<int> a(n);
vector<ll> b(n);
ll need = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
p.push_back(make_pair(a[i], b[i]));
need += b[i];
}
sort(p.begin(), p.end());
if (need <= k) {
cout << 1 << endl;
return 0;
}
int result = 0;
for (auto e : p) {
need -= e.second;
if (need <= k) {
result = e.first + 1;
break;
}
}
cout << result << endl;
return 0;
}別解として、解を二分探索で求めることができます。めぐる式と呼ばれる二分探索の実装を参考にしました。ABC299D問題でも解説しています。
解は必ず 109+1 以下となります。判定する関数 is_OK は、その日に飲む薬が K 個以下なら true を返します。あとはコードのパターンに従います。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF 1000000001
bool is_OK(int mid, ll key, vector<int> a, vector<ll> b)
{
ll result = 0;
for (int i = 0; i < a.size(); ++i) {
if (mid <= a[i]) {
result += b[i];
}
}
return result <= key;
}
int main()
{
int n;
ll k;
cin >> n >> k;
vector<int> a(n);
vector<ll> b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
}
int ng = 0;
int ok = INF;
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (is_OK(mid, k, a, b)) {
ok = mid;
} else {
ng = mid;
}
}
cout << ok << endl;
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC309C）
最初に、シミュレーションをするプログラムを紹介します。
"""AtCoder Beginner Contest 309 C"""
n, k = map(int, input().split())
a = [0] * n
b = [0] * n
p = []
need = 0
for i in range(n):
a[i], b[i] = map(int, input().split())
p.append((a[i], b[i]))
need += b[i]
p.sort()
result = 0
if need <= k:
result = 1
else:
for e in p:
need -= e[1]
if need <= k:
result = e[0] + 1
break
print(result)次に解を二分探索するプログラムです。
"""AtCoder Beginner Contest 309 C"""
def is_OK(mid, key, a, b):
result = 0
for i in range(len(a)):
if mid <= a[i]:
result += b[i]
return result <= key
n, k = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
a[i], b[i] = map(int, input().split())
ng = 0
ok = 10 ** 9 + 1
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_OK(mid, k, a, b):
ok = mid
else:
ng = mid
print(ok)こちらも「AC」と判定されました。
最後に
この問題は、二分探索を使う別解のほうが実行時間がかかりました。これは判定関数で何度もその日までに飲む薬の数を求めているためです。
自分でパターンが分かっている方法に持ち込む方がよいと考えて、コンテストでは二分探索を使いました。
引き続き ABC の問題を紹介していきます。
