AtCoder が提供しているABC（AtCoder Beginner Contest）376 C問題をC++とPythonで解いてみました。ABC376は、2024年10月19日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Prepare Another Box（Difficulty : 366）
問題の詳細は、リンク先をご覧ください。
ABC376 C問題 Prepare Another Box
解の二分探索もしくは貪欲法を使って解くことができます。AtCoder Problems による Difficulty は 366 でした。
解答案
$N$ 個のおもちゃの大きさを配列 $A$ に、$N-1$ 個の箱の大きさを配列 $B$ に格納します。配列 $B$ に1つ要素を加えて、$A$ と $B$ をソートして、すべての要素について、
$$A[i] \leqq B[i]$$
が成立していれば、操作2を行うことができます。
また、配列 $B$ に加える要素の最小値は、以下の性質を持ちます。
- ある最小値以上のすべての値では、操作2を行うことができる。
- その最小値未満のすべての値では、操作2を行うことができない。
このような性質を持つ最小値は解の二分探索で求めることができます。
C++ プログラム例（ABC376C）
配列 $B$ に加える値で二分探索を行います。
- 判定関数
is_OKは、ラムダ式で定義しました（18ー30行目）。- 引数を配列 $B$ に加えて、ソートします。
- すべての要素で
a[i] <= b[i]が成立するとtrueを返します。それでなければfalseを返します。
- 解の二分探索の定番コードです（32ー41行目）。
- 上限でも
is_OKが成立しない場合は最小値が存在しないため、-1 を出力します（43ー45行目）。
上記の分岐を実装したのが、以下のC++プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
vector<int> b(n - 1);
for (int i = 0; i < n - 1; ++i) {
cin >> b[i];
}
auto is_OK = [&](int mid) -> bool {
vector<int> tb = b;
tb.push_back(mid);
sort(tb.begin(), tb.end());
bool result = true;
for (int i = 0; i < n; ++i) {
if (a[i] > tb[i]) {
result = false;
break;
}
}
return result;
};
int ng = 0;
int ok = 1000000001;
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (is_OK(mid)) {
ok = mid;
} else {
ng = mid;
}
}
if (!is_OK(ok)) {
ok = -1;
}
cout << ok << endl;
return 0;
}貪欲法でも解くことができます。
配列 $A$ と配列 $B$ を降順にソートします。大きい方から、a[i] <= b[i] が成立するか確認します。成立しない場合は、b[i] として a[i] を挿入することにします。また、これが最小値の候補となります。これ以降の要素について、a[i] <= b[i] が成立すれば、挿入した a[i] が解となります。ふたたび a[i] > b[i] となっていれば解無しとなります（2個は挿入できません）。
注意として、配列 $B$ の大きさを $N-1$ ではなくて $N$ 個用意する必要があります。これは、$A$ の一番小さい値まで条件が成立した場合に b[n-1] をアクセスするためです。この値は初期値の 0 としています。以下が貪欲法のプログラムとなります。実行時間はこちらの方が短くなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end(), greater<int>());
vector<int> b(n);
for (int i = 0; i < n - 1; ++i) {
cin >> b[i];
}
sort(b.begin(), b.end(), greater<int>());
int result;
int diff = 0;
for (int i = 0; i < n; ++i) {
if (b[i - diff] < a[i]) {
if (diff == 0) {
result = a[i];
diff = 1;
} else {
result = -1;
break;
}
}
}
cout << result << endl;
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC376C）
Python版も基本的な考え方は同じです。以下は、解の二分探索を使ったプログラムです。
"""AtCoder Beginner Contest 376 C"""
def is_OK(mid):
global n, a, b
tb = b.copy()
tb.append(mid)
tb.sort()
result = True
for i in range(n):
if a[i] > tb[i]:
result = False
return result
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = list(map(int, input().split()))
ng = 0
ok = 10 ** 9 + 1
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_OK(mid):
ok = mid
else:
ng = mid
if not is_OK(ok):
ok = -1
print(ok)C++に合わせて貪欲法のプログラムも紹介します。リスト b には、オーバーランを避けるために要素を1個追加しています（6行目）。
"""AtCoder Beginner Contest 376 C"""
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = list(map(int, input().split()))
b.append(0)
b.sort(reverse=True)
result = 0
diff = 0
for i in range(n):
if b[i - diff] < a[i]:
if diff == 0:
result = a[i]
diff = 1
else:
result = -1
break
print(result)
こちらも「AC」と判定されました。
最後に
コンテストは、貪欲法で解きました。
コンテストで提出したC++プログラムは配列外参照をしていました。ジャッジではAC判定でしたが、好ましくないと考えています。
引き続き ABC の問題を紹介していきます。
