001.md

001 - Yokan Party (★4)

解答

#include <iostream>
#include <vector>

// ピースのサイズが minPieceSize 以上になるようにカットして,
// K 回以上カットできるかを調べる関数.
// カットできる場合 true, できない場合 false を返す
bool Check(int minPieceSize, const std::vector<int>& A, int K, int L)
{
	// カットした回数
	int cutCount = 0;

	// 最後にカットした位置 (cm)
	int lastCutPos = 0;

	// 各切れ目の位置について
	for (const auto& a : A)
	{
		// 現在の位置でカットした場合にできるピースの長さ
		const int pieceSize = (a - lastCutPos);

		// 現在の位置でカットした場合に残るほうのピースの長さ
		const int remaining = (L - a);

		// どちらのピースも minPieceSize 以上であれば, そこでカットする
		if ((minPieceSize <= pieceSize)
			&& (minPieceSize <= remaining))
		{
			// カット回数を増やす
			++cutCount;

			// 最後にカットした位置を更新
			lastCutPos = a;
		}
	}

	// カットした回数が K 以上なら OK
	return (K <= cutCount);
}

int main()
{
	// N 個の切れ目, 全体が L cm, 切れ目を K 個選ぶ
	int N, L, K;
	std::cin >> N >> L >> K;

	// 各切れ目の位置 (cm)
	std::vector<int> A(N);
	for (auto& a : A)
	{
		std::cin >> a;
	}

	////////////////////////////////
	//
	// いわゆる「めぐる式二分探索法」
	// https://qiita.com/drken/items/97e37dd6143e33a64c8c
	// 

	// 解答（最も短いピースの長さ）の候補を表す区間を二分探索
	int ok = 1;
	int ng = L + 1;

	// 解答を 1 つに絞れないうちは繰り返す
	while (1 < std::abs(ok - ng))
	{
		// 試すピースの長さ
		const int mid = (ok + ng) / 2;

		if (Check(mid, A, K, L)) // そのピースの長さで成立したら
		{
			ok = mid;
		}
		else
		{
			ng = mid;
		}
	}
	//
	////////////////////////////////

	// 解答を出力
	std::cout << ok << '\n';
}