Atcoder解いてみた AtCoder Beginner Contest D - Minimum Width

AtCoder Beginner Contest D - Minimum Width

問題はこちら

回答

解の二分探索

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>
#include <iomanip>
#include <random>


int N, M;
std::vector<long long> L;
const long long inf = 4e14;


// 幅Xのスクリーンを使ったときに、全ての文字をM行で表示できるか判定する
// 単純にO(N)で見ていき、必要な行数を求め、M以下か判定?
bool Judge(const long long& X) {

	int res = 1; // 実際に必要な行数
    
	long long currentLen = 0;
	for (int i = 0; i < L.size(); i++) {
		if (L[i] > X) {
			return false;
		}

		// ちょうどL[i]を置ける
		if (currentLen + L[i] == X) {
			currentLen += L[i];
		}
		// L[i]をおいても余裕あり
		else if (currentLen + L[i] < X) {
			currentLen += (L[i] + 1);
		}
		else {
			// 行追加
			res++;
			currentLen = L[i];

			// 空白を追加できるなら追加する
			if (currentLen < X) {
				currentLen++;
			}
		}
	}
    
	// 必要な行数がM行で収まるか否か
	return res <= M;
}

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N >> M;

	for (int n = 0; n < N; n++) {
		long long l;
		std::cin >> l;
		L.push_back(l);
	}

	long long wa = 0; // 絶対にありえない値
	long long ac = inf;

	while (wa + 1 < ac) {
		long long X = (wa + ac) / 2;

		if (Judge(X)) {
			ac = X;
		}
		else {
			wa = X;
		}
	}

	std::cout << ac << std::endl;

	return 0;
}

振り返り

発想自体は簡単だが、判定処理の実装で条件分岐が複雑にならないように工夫する必要がある
当初、以下のコードを書いていた
しかし、Xから引いていく（減算）実装では、改行した瞬間に、処理中(else)の単語の扱いの状態管理が複雑化した
そして、L[i] > tmpXの場合の処理が漏れてしまった
そのため、回答のような、加算形式の考え方の方が実装がシンプルになる

	long long tmpX = X;

	for (int i = 0; i < L.size(); i++) {
		if (L[i] > X) {
			return false;
		}

		// 途中でXを復活させること
		if (L[i] < tmpX) {
			tmpX -= (L[i] + 1);
		}
		else if (L[i] == tmpX) {
			tmpX -= L[i];
		}
		else {
			// 行追加
			res++;
			// 次の行に移るため、復活
			tmpX = X;

			if (L[i] < tmpX) {
				tmpX -= (L[i] + 1);
			}
			else if (L[i] == tmpX) {
				tmpX -= L[i];
			}
			// ここで、L[i] > tmpXの場合が無視される
		}
	}

しかし、さらに以下の実装の方がシンプル
回答の実装では、1時刻先に発生する見たいの空白を現在のループで考慮する方法となっていた
しかし、以下の実装では、空白→文字の順を想定し、1時刻先の空白を考慮しない実装にし、else内の実装を簡略化した
このような実装は、currentLenを「今画面上に実際に置かれている純粋な文字数」という1つの意味に固定したことにより可能となる

	long long currentLen = 0;

	for (int i = 0; i < L.size(); i++) {

		if (L[i] > X) {
			return false;
		}

		// 最初の単語の場合、空白は不要
		if (currentLen == 0) {
			currentLen = L[i];
		}
		// 今の行に「空白(1) + 次の単語(L[i])」を追加しても幅 X に収まるか？
		else if (currentLen + 1 + L[i] <= X) {
			currentLen += (1 + L[i]);
		}
		// 収まらないなら改行する
		else {
			res++;
			currentLen = L[i];
		}
	}

得られた教訓

1

アルゴリズムの種類によって、思考のフレームワークを以下のように切り替えるとバグが一気に減る
「選び方の組み合わせ・最適化」（DP・再帰）は減算思考が有効(実際は加算でもいいが、実装しやすい方で)
→ 減算しても、境界リセットが発生しないため

「順番に詰めていく・シミュレーション」（二分探索の判定・貪欲法）は、加算思考が有効
→ 境界リセット処理がシンプル化

2

変数の意味は一位に固定すること