D - Minimum Width - AtCoder Beginner Contest 319
D - Minimum Width - AtCoder Beginner Contest 319
問題:
解説:
提出:
簡単な方針
解答は最大の単語長$ \max_{i} L_i以上、全てを1行ずつ並べたときの幅$ -1+\sum_{i}(1+L_i)以下にある
の範囲で、単調な関数$ fを二分探索する
関数の解の二分探索
ただし、単純な二分探索ではなく、上界下界二分探索
疑問
D - Minimum Width - AtCoder Beginner Contest 319 の「単語を先頭から貪欲に配置する方法」が最適であることを確認したい
空白込みで単語を計算していた場合(これを計算する関数を$ f'とする)、なぜ最後に1を引く必要があるか?
---> 空白込みの1文字で入るかどうかを算出している点で、本来の$ f(W)とはずれるため
aは例1の入力系列として、Pythonで$ f'(26)を計算させたら、実際の$ f(26)とはずれていることが確認できる。
https://gyazo.com/82d3c91dcc076359d1f996c92ff7ba4b
元の$ fの計算において、少なくとも一つの行は幅を全て使い切る。
本来の行末には空白は必要がないが、ここでは全ての単語の後に空白を含めて考えてしまっている
なので、その幅を使い切る行においては入り切らず、本来とは異なる結果が出てきてしまう
その点で、幅を1増やした$ f'(W + 1)は正しく$ f(W)を計算してくれる。
行末に当たる全ての単語には必要のない空白が1つ加えられているので、それと加えられた幅1がうまく影響を吸収してくれる。
もっと厳密な言い回しができそう。
知見
std::range::max関数でコンテナの最大値が取れる。 in <algorithm>
https://cpprefjp.github.io/reference/algorithm/ranges_max.html
std::reduce関数で総和が取れる。in <numeric>
通常の二分探索とは違って、begin_W != end_Wだと永遠に終わらない。
std::upper_bound関数
// begin_W = mid_W + 1の更新を行なっていればそうでもないのだが、
// 今回はf(W) < aを満たす最小のW(上界)を求めなければならないので、
// このような二分探索をとっている
code:cpp
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <numeric>
#define DEBUG(x) x
#define INFO(x) DEBUG(std::cerr << x << std::endl)
#define snap(var) DEBUG(std::cerr << "snap " << #var << " = " << (var) << std::endl)
#define snap_msg(msg, var) DEBUG(std::cerr << "snap:" << (msg) << " " << #var << " = " << (var) << std::endl)
using ull = unsigned long long;
/**
* @brief 解答の関数fに相当する
* この関数(数列)Wに対して単調減少するので、
* ある自然数aに対してf(W) = aとなるようなWの二分探索が可能。
*/
ull get_lines_stuffed_words(const std::vector<ull>& L, const ull W){
ull chara_in_line = 0;
ull line_count = 1;
for (const ull word:L){
if (W - chara_in_line < word) {
chara_in_line = 0;
line_count += 1;
}
chara_in_line += word;
}
return line_count;
}
int main(){
int N, M; std::cin >> N >> M;
std::vector<ull> L(N);
// 空白付け足し
for (int i = 0; i < N; i++) { std::cin >> Li; Li++; }
ull begin_W = std::ranges::max(L) - 1ull;
ull end_W = std::reduce(L.begin(), L.end());
// 通常の二分探索とは違って、begin_W != end_Wだと永遠に終わらない。
// begin_W = mid_W + 1の更新を行なっていればそうでもないのだが、
// 今回はf(W) < aを満たす最小のW(上界)を求めなければならないので、
// このような二分探索をとっている
while (begin_W + 1 < end_W){
const ull mid_W = std::midpoint(begin_W, end_W);
const ull lines = get_lines_stuffed_words(L, mid_W);
if (lines > M) { begin_W = mid_W; }
else { end_W = mid_W; }
}
std::cout << end_W - 1 << std::endl;
}
解き直し D
全くわからんかったやつ
解を引数にとる関数が単調な関数で表せて
変数が有界な範囲にあると絞れたら
二分探索によって関数の引数を求めることができる
二分探索による単調な関数を含む方程式の解を求める