1. 概要
公式解説をもとに、競プロ典型90問の1問目の解法と実装をc++で解説します。
2. 問題 001 - Yokan Party（★4）
問題文
左右の長さが $L$ [cm] のようかんがあります。 $N$ 個の切れ目が付けられており、左から $i$ 番目の切れ目は左から $A_i$ [cm] の位置にあります。
あなたは $N$ 個の切れ目のうち $K$ 個を選び、ようかんを $K+1$ 個のピースに分割したいです。そこで、以下の値を スコア とします。
- $K+1$ 個のピースのうち、最も短いものの長さ（cm 単位）
スコアが最大となるように分割する場合に得られるスコアを求めてください。
制約
- 1 $\leq$ $K$ $\leq$ $N$ $\leq$ 10000
- 0 $<$ $A_1$ $<$ $A_2$ $<$ $\cdots$ $<$ $A_N$ $<$ $L$ $\leq$ $10^9$
- 入力はすべて整数
3. 解法
| 【ポイント】最小値の最大化→答えで二分探索をする |
|---|
切り分け方で全探索することを考えてみます。
$N$ 個の切れ目から $K$ 個の切れ目を入れる方法は ${}_N\mathrm{C}_K$ 通りあるのですべて試すとTLEになります。
今、ようかんの長さが $L$ なので答えは $L$ 以下の整数であることが分かっています。そこで切り方ではなく、答えの長さに注目します。つまり、
「長さ $M$ 以上のピースを $K+1$ 個以上作ることができるか」
の判定をいろいろな $M$ について行います。
この判定問題は、
「左端から順に切れ目を調べていき、ピースの長さが $M$ 以上になった時点で切る」
とすれば $O(N)$ で解くことができます。 ( 詳細は後述 )
$M=1, 2, \cdots$ と順次調べれば最大で $O(NL)$ の計算量が必要で、TLEになります。計算量を減らすために二分探索を用います。すると、$O(N \log L)$ で求めることができます。
4. 実行コード(c++)
4.1 コードの全容
#include <bits/stdc++.h>
using namespace std;
int N, L, K;
vector<long long> A;
bool solve(int M)
{
// 長さM以上でK+1個以上に分割できるかを判定する
int cut_count = 0;
int prev = 0; // 現在のピースの長さ
int total_cut_length = 0; // 切り分けられたピースの合計の長さ
for (int i = 1; i <= N; i++)
{
prev += A[i] - A[i - 1];
if (prev >= M)
{
cut_count += 1;
total_cut_length += prev;
prev = 0;
}
}
if (cut_count > K)
return true;
if ((cut_count == K) && ((L - total_cut_length) >= M))
return true;
return false;
}
int main()
{
// 入力
cin >> N >> L >> K;
A.resize((N + 1), 0);
for (int i = 1; i <= N; i++)
{
cin >> A[i];
}
// 二分探索
int ok = 0;
int ng = L + 1;
while((ng - ok) > 1){
int mid = (ok + ng) / 2;
if (solve(mid))
ok = mid;
else ng = mid;
}
//出力
cout << ok << endl;
return 0;
}
4.2 コードの補足説明
int N, L, K;
vector<long long> A;
bool solve(int M)
{
// 長さM以上でK+1個以上に分割できるかを判定する
int cut_count = 0;
int prev = 0; // 現在のピースの長さ
int total_cut_length = 0; // 切り分けられたピースの合計の長さ
for (int i = 1; i <= N; i++)
{
prev += A[i] - A[i - 1];
if (prev >= M)
{
cut_count += 1;
total_cut_length += prev;
prev = 0;
}
}
省略
}
solve 関数では「長さ$M$ 以上のピースを $K+1$ 個以上作ることができるか」を判定しています。
左端から順に切れ目を探索し、ピースの長さが $M$ 以上になる初めての場所で切ります。
bool solve(int M){
省略
if (cut_count > K)
return true;
if ((cut_count == K) && ((L - total_cut_length) >= M))
return true;
return false;
}
$K+1$ 個以上のピースに切り分けられるかを判定します。
切れ目が $K$ 個以上あればよいです。ただし、切れ目がちょうど $K$ 個であるときには注意が必要です。最後のピースが $M$ 以上である保証がないので、最後のピースの長さ L - total_cut_length が $M$ 以上であることを確認します。
$K + 1$ 個以上の切れ目がある時は $K+1$ ピース以上が長さ $M$ 以上あるので確認する必要はありません。
int N, L, K;
vector<long long> A;
省略
int main()
{
省略
// 二分探索
int ok = 0;
int ng = L + 1;
while((ng - ok) > 1){
int mid = (ok + ng) / 2;
if (solve(mid))
ok = mid;
else ng = mid;
}
省略
}
$K+1$ 個以上のピースに切り分けられる最大の長さを二分探索で求めます。
二分探索の実装は二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜を用いました。
ok 以下の長さでは $K+1$ 個以上のピースに切り分けられます。ng 以下の長さでは $K+1$ 個以上のピースに切り分けられません。
5. 最後に
公式の解説だけでは難しいと感じる人にとって、少しでも役に立っていれば幸いです。
他の問題の解説も随時アップロードする予定です。
最後まで読んで下さりありがとうございました。