AtCoder が提供しているABC（AtCoder Beginner Contest）319 のD問題をC++とPythonで解いてみました。ABC319は、2023年9月9日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Minimum Width（Difficulty : 631）
問題はリンク先をご覧ください。
解の二分探索を使って解くことができました。AtCoder Problems による Difficulty は 631 でした。
解答案
二分探索で求めることができます。めぐる式と呼ばれる二分探索の実装を参考にしました。ABC299D問題（解説）、ABC309C問題（解説）、ABC312C問題（解説）でも解説しています。定番の考え方と言えます。
C++ プログラム例（ABC319D）
以下のコードパターンを実装します。
- 関数 is_OK: この関数は条件を満たすか満たさないか判定します。
この問題の場合、与えられた幅 mid の行に単語を詰めていって、m 行以内に収まるか判定しています。 - 二分探索を行うコード（43ー53行目）: このコードは変数 ng と ok を定める以外は、変更する必要がありません。
- ng は 0 となります（幅 0 は明らかに解とならない）。
- ok は、m=1 の場合に、長さ Li（最大 109）の単語を n（最大 2 × 105）個入れる必要があるため、1015 を設定しました（43、44行目）。
関数 is_OK の計算量は $(N)$、呼び出し回数は、$\log_2 10^{15}$ が上限となるため間に合います。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n, m;
vector<ll> L;
bool is_OK(ll mid)
{
int line = 0;
ll remain = mid;
for (int i = 0; i < n; ++i) {
if (L[i] > mid) {
return false;
}
if (L[i] <= remain) {
remain -= L[i];
if (remain > 0) {
--remain;
}
} else {
++line;
remain = mid - L[i];
if (remain > 0) {
--remain;
}
}
}
++line;
return line <= m;
}
int main()
{
cin >> n >> m;
L.resize(n);
for (int i = 0; i < n; ++i) {
cin >> L[i];
}
ll ng = 0LL;
ll ok = 1000000000000000LL;
while (abs(ok - ng) > 1) {
ll mid = (ok + ng) / 2LL;
if (is_OK(mid)) {
ok = mid;
} else {
ng = mid;
}
}
cout << ok << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC319D）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 319 D"""
def is_OK(mid):
global n
global m
global L
line = 0
remain = mid
for i in range(n):
if L[i] > mid:
return False
if L[i] <= remain:
remain -= L[i]
if remain > 0:
remain -= 1
else:
line += 1
remain = mid - L[i]
if remain > 0:
remain -= 1
line += 1
return line <= m
n, m = map(int, input().split())
L = list(map(int, input().split()))
ng = 0
ok = 10 ** 15
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_OK(mid):
ok = mid
else:
ng = mid
print(ok)こちらも「AC」と判定されました。
最後に
「解の二分探索」は、関数 is_OK、変数 ng と ok を適切に設定するだけで、多くの問題を解くことができます。今回の問題は、特に直前にブログ記事にした ALDS1 4_D問題と設定が似ていました（行に文字を詰める代わりに、トラックに荷物を積める問題になっていました）。このような手の内化できている問題を増やしていきたいです。
引き続き ABC の問題を紹介していきます。
