076.md

076 - Cake Cut (★3)

解答

#include <iostream>
#include <vector>
#include <algorithm> // std::binary_search()

int main()
{
	// N 個のピース
	int N;
	std::cin >> N;

	std::vector<int> A(N);
	for (auto& a : A)
	{
		std::cin >> a;
	}

	// 連続させて二倍の長さにしたうえでの累積和を構築
	// 
	// 例: A = { 1, 18, 1 } のとき
	// B = { 0, 1, 19, 20, 21, 39, 40 }, B[N] = 20
	//
	std::vector<long long> B = { 0 };
	for (int i = 0; i < 2; ++i)
	{
		for (const auto& a : A)
		{
			B.push_back(B.back() + a);
		}
	}

	// 一周分の大きさ
	const long long whole = B[N];

	// 一周分の大きさに対し, ちょうど 10 分の 1 になる整数が存在しない場合は No
	if (whole % 10 != 0)
	{
		std::cout << "No\n";
		return 0;
	}

	// それぞれのピースの開始位置に対し
	for (int i = 0; i < N; ++i)
	{
		// 現在の位置から 10 分の 1 の大きさで取り出す場合の終了位置
		const long long target = (B[i] + (whole / 10));

		// 二分探索で target を検索
		if (std::binary_search(B.begin(), B.end(), target)) // 10 分の 1 の大きさにする取り出し方が存在
		{
			std::cout << "Yes\n";
			return 0;
		}
	}

	// 10 分の 1 の大きさにする取り出し方が存在しなかった
	std::cout << "No\n";
}