AtCoder が提供しているABC（AtCoder Beginner Contest）270 のE問題をC++で解いてみました。ABC270は、2022年9月24日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Apple Baskets on Circle（Difficulty : 1211）
問題はリンク先をご覧ください。
ABC270 E問題 Apple Baskets on Circle
解の二分探索を使って解くことができます。AtCoder Problems による Difficulty は、1211 でした。
解答案
何周回れば、リンゴをK個以上食べられるか求めます。これは、解の二分探索を使うことにより $O(N \log K)$ で求めることができます。この値が分かれば、それより1周少なく回った後に、ひとつずつかごを調べることにより解答が求まります。
解の二分探索について、いつものようにめぐる式と呼ばれる二分探索の実装を参考にしました。
C++ プログラム例（ABC270E）
少し長いプログラムですが、以下のコードは定番です。
- 関数 is_ok: mid 周回ったときに K 個以上のりんごを食べたか返します。
- 変数 ng と ok を設定するだけの解の二分探索の定番コードです（28ー37行目）。
変数 ok 周回った時に K 個以上となります。まず、ok-1 周回り、配列 a[i] の個数を減らします（40ー43行目）。そのあとに、K 個になるまで、a[i] からひとつずつ減らします（44ー52行目）。
最後に配列 a の各要素を出力します。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n;
ll k;
vector<ll> a;
bool is_OK(ll mid)
{
ll apple = 0;
for (int i = 0; i < n; ++i) {
apple += min(a[i], mid);
}
return apple >= k;
}
int main()
{
cin >> n >> k;
a.resize(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
ll ng = 0;
ll ok = k;
while (abs(ok - ng) > 1) {
ll mid = (ok + ng) / 2;
if (is_OK(mid)) {
ok = mid;
} else {
ng = mid;
}
}
ll apple = 0;
for (int i = 0; i < n; ++i) {
apple += min(a[i], ok - 1);
a[i] -= min(a[i], ok - 1);
}
for (int i = 0; i < n; ++i) {
if (a[i] > 0) {
--a[i];
++apple;
if (apple == k) {
break;
}
}
}
for (int i = 0; i < n; ++i) {
cout << a[i] << " \n"[i == n - 1];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC270E）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 270 E"""
def is_OK(mid):
global n
global k
global a
apple = 0
for i in range(n):
apple += min(a[i], mid)
return apple >= k
n, k = map(int, input().split())
a = list(map(int, input().split()))
ng = 0
ok = k
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_OK(mid):
ok = mid
else:
ng = mid
apple = 0
for i in range(n):
apple += min(a[i], ok - 1)
a[i] -= min(a[i], ok - 1)
for i in range(n):
if a[i] > 0:
a[i] -= 1
apple += 1
if apple == k:
break
print(*a)こちらも「AC」と判定されました。
最後に
コンテスト中では、問題を読むこともできませんでした。
同じく解けなかった ABC270D（DP）よりも、解の二分探索を使うこの問題の方が簡単に感じました。この1年の進歩をうれしく感じます。
引き続き ABC の問題を紹介していきます。
