Skip to content

Latest commit

 

History

History
373 lines (297 loc) · 10.2 KB

037.md

File metadata and controls

373 lines (297 loc) · 10.2 KB
Raw

037 - Don't Leave the Spice (★5)

解答 1

#include <iostream>
#include <vector>
#include <algorithm> // std::max()
#include <limits> // std::numeric_limits<>::lowest()

// セグメント木による Range Maximum Query
class SegmentTree
{
public:

	SegmentTree() = default;

	// ツリーの初期化（単位元は std::numeric_limits<long long>::lowest()）
	explicit SegmentTree(size_t size)
	{
		// size 以上である 2 のべき乗数を求めて m_size に代入する
		while (m_size < size)
		{
			m_size *= 2;
		}

		m_nodes.resize((m_size * 2 - 1), std::numeric_limits<long long>::lowest());
	}

	// 値の初期化
	void init(const std::vector<long long>& values)
	{
		for (size_t i = 0; i < values.size(); ++i)
		{
			m_nodes[m_size - 1 + i] = values[i];
		}

		for (int i = static_cast<int>(m_size) - 2; i >= 0; --i)
		{
			update(i);
		}
	}

	// 一点更新
	void set(size_t i, long long value)
	{
		// ノードのインデックス
		size_t ni = (i + m_size - 1);

		m_nodes[ni] = value;

		// 親を更新していく
		while (0 < ni)
		{
			// ni を親のインデックスにする
			ni = (ni - 1) / 2;

			// 親を更新
			update(ni);
		}
	}

	// 区間クエリ（対象区間 [begin, end) における最大値を求める）
	long long query(size_t begin, size_t end) const
	{
		return query(begin, end, 0, 0, m_size);
	}

private:

	// ノードの更新
	void update(size_t ni)
	{
		m_nodes[ni] = std::max(m_nodes[(ni * 2 + 1)], m_nodes[(ni * 2 + 2)]);
	}

	// 区間クエリ（対象区間 [begin, end) における最大値を求める）
	// ni: 確認するノードのインデックス. そのノードの管理区間は [nBegin, nEnd)
	long long query(size_t begin, size_t end, size_t ni, size_t nBegin, size_t nEnd) const
	{
		// クエリ対象区間が管理区間と無関係なら
		if ((nEnd <= begin) || (end <= nBegin))
		{
			return std::numeric_limits<long long>::lowest();
		}

		// 管理区間のすべてがクエリ対象区間に含まれていれば
		if ((begin <= nBegin) && (nEnd <= end))
		{
			return m_nodes[ni];
		}

		// query(クエリ対象区間, 子ノード(左) のインデックス, 子ノード(左) の管理区間)
		const long long m1 = query(begin, end, (ni * 2 + 1), nBegin, (nBegin + nEnd) / 2);

		// query(クエリ対象区間, 子ノード(右) のインデックス, 子ノード(右) の管理区間)
		const long long m2 = query(begin, end, (ni * 2 + 2), (nBegin + nEnd) / 2, nEnd);

		return std::max(m1, m2);
	}

	size_t m_size = 1;

	std::vector<long long> m_nodes;
};

// 料理を表す構造体
struct Dish
{
	// 最小で L [mg] の香辛料を消費
	int L;

	// 最大で R [mg] の香辛料を消費
	int R;

	// 料理の価値
	int V;
};

int main()
{
	// 香辛料をちょうど W [mg] 消費, 料理が N 種類
	int W, N;
	std::cin >> W >> N;

	// 料理の情報を入力
	std::vector<Dish> dishes(N);
	for (auto& dish : dishes)
	{
		std::cin >> dish.L >> dish.R >> dish.V;
	}

	// dp[今まで見た料理の個数][香辛料の合計量] = 価値合計の最大値
	// 不可能な状態は -1 で表現する
	std::vector<std::vector<long long>> dp(N + 1, std::vector<long long>(W + 1, -1));
	dp[0][0] = 0;

	std::vector<SegmentTree> rmqs(N + 1, SegmentTree(W + 1));
	rmqs[0].set(0, 0);

	for (int i = 1; i <= N; ++i) // i 個目の料理を見る
	{
		// 現在の料理を作らなかった場合の状態（直前の料理完了時点と同じ）を設定
		dp[i] = dp[i - 1];

		// 見ている料理
		const auto& dish = dishes[i - 1];

		// k: 香辛料の合計量
		for (int k = 0; k <= W; ++k)
		{
			// 現在の料理で [香辛料の合計量] k を実現するために必要な,
			// 直前の料理における [香辛料の合計量] の最小値
			const int fromBegin = std::max(0, (k - dish.R));

			// 現在の料理で [香辛料の合計量] k を実現するために必要な,
			// 直前の料理における [香辛料の合計量] の最大値（の次の要素を指して, 範囲の終端位置を表現）
			const int fromEnd = std::max(0, (k - dish.L + 1));

			// [fromBegin, fromEnd) で範囲を表す. (fromBegin == fromEnd) の場合は, 実現不可能
			if (fromBegin == fromEnd)
			{
				continue;
			}

			// セグメント木による区間最大値取得.
			// [fromBegin, fromEnd) の中で最大の価値合計値を探す
			const long long max = rmqs[i - 1].query(fromBegin, fromEnd);

			// 最大の価値合計値 -1 は, 直前の状態が実現不可能ということなのでスキップ
			if (max != -1)
			{
				// 料理を作らない場合と作る場合の価値合計値を比較して, 大きいほうを採用
				dp[i][k] = std::max(dp[i][k], (max + dish.V));
			}
		}

		// セグメント木を更新
		for (int k = 0; k <= W; ++k)
		{
			rmqs[i].set(k, dp[i][k]);
		}
	}

	// 解答 (dp[N][W]) を出力
	std::cout << dp.back().back() << '\n';
}

解答 2 (AC Library を使用)

自作のセグメント木ではなく、AC Library に実装されているセグメント木 atcoder::segtree を使った解法です。

#include <iostream>
#include <vector>
#include <algorithm> // std::max()
#include <limits> // std::numeric_limits<>::lowest()
#include <atcoder/segtree.hpp> // atcoder::segtree

long long Op(long long a, long long b)
{
	return std::max(a, b);
}

long long E()
{
	return std::numeric_limits<long long>::lowest();
}

// セグメント木による Range Maximum Query
using SegmentTree = atcoder::segtree<long long, Op, E>;

// 料理を表す構造体
struct Dish
{
	// 最小で L [mg] の香辛料を消費
	int L;

	// 最大で R [mg] の香辛料を消費
	int R;

	// 料理の価値
	int V;
};

int main()
{
	// 香辛料をちょうど W [mg] 消費, 料理が N 種類
	int W, N;
	std::cin >> W >> N;

	// 料理の情報を入力
	std::vector<Dish> dishes(N);
	for (auto& dish : dishes)
	{
		std::cin >> dish.L >> dish.R >> dish.V;
	}

	// dp[今まで見た料理の個数][香辛料の合計量] = 価値合計の最大値
	// 不可能な状態は -1 で表現する
	std::vector<std::vector<long long>> dp(N + 1, std::vector<long long>(W + 1, -1));
	dp[0][0] = 0;

	std::vector<SegmentTree> rmqs(N + 1, SegmentTree(W + 1));
	rmqs[0].set(0, 0);

	for (int i = 1; i <= N; ++i) // i 個目の料理を見る
	{
		// 現在の料理を作らなかった場合の状態（直前の料理完了時点と同じ）を設定
		dp[i] = dp[i - 1];

		// 見ている料理
		const auto& dish = dishes[i - 1];

		// k: 香辛料の合計量
		for (int k = 0; k <= W; ++k)
		{
			// 現在の料理で [香辛料の合計量] k を実現するために必要な,
			// 直前の料理における [香辛料の合計量] の最小値
			const int fromBegin = std::max(0, (k - dish.R));

			// 現在の料理で [香辛料の合計量] k を実現するために必要な,
			// 直前の料理における [香辛料の合計量] の最大値（の次の要素を指して, 範囲の終端位置を表現）
			const int fromEnd = std::max(0, (k - dish.L + 1));

			// [fromBegin, fromEnd) で範囲を表す. (fromBegin == fromEnd) の場合は, 実現不可能
			if (fromBegin == fromEnd)
			{
				continue;
			}

			// セグメント木による区間最大値取得.
			// [fromBegin, fromEnd) の中で最大の価値合計値を探す
			const long long max = rmqs[i - 1].prod(fromBegin, fromEnd);

			// 最大の価値合計値 -1 は, 直前の状態が実現不可能ということなのでスキップ
			if (max != -1)
			{
				// 料理を作らない場合と作る場合の価値合計値を比較して, 大きいほうを採用
				dp[i][k] = std::max(dp[i][k], (max + dish.V));
			}
		}

		// セグメント木を更新
		rmqs[i] = SegmentTree(dp[i]);
	}

	// 解答 (dp[N][W]) を出力
	std::cout << dp.back().back() << '\n';
}

TLE する例

次のようなプログラムでも正解の出力を得られますが、各料理について dp[i][k] を求めるのに O(W^2) の計算が必要で、TLE になります。

#include <iostream>
#include <vector>
#include <algorithm> // std::max(), std::max_element()

// 料理を表す構造体
struct Dish
{
	// 最小で L [mg] の香辛料を消費
	int L;

	// 最大で R [mg] の香辛料を消費
	int R;

	// 料理の価値
	int V;
};

int main()
{
	// 香辛料をちょうど W [mg] 消費, 料理が N 種類
	int W, N;
	std::cin >> W >> N;

	// 料理の情報を入力
	std::vector<Dish> dishes(N);
	for (auto& dish : dishes)
	{
		std::cin >> dish.L >> dish.R >> dish.V;
	}

	// dp[今まで見た料理の個数][香辛料の合計量] = 価値合計の最大値
	// 不可能な状態は -1 で表現する
	std::vector<std::vector<long long>> dp(N + 1, std::vector<long long>(W + 1, -1));
	dp[0][0] = 0;

	for (int i = 1; i <= N; ++i) // i 個目の料理を見る
	{
		// 現在の料理を作らなかった場合の状態（直前の料理完了時点と同じ）を設定
		dp[i] = dp[i - 1];

		// 見ている料理
		const auto& dish = dishes[i - 1];

		// k: 香辛料の合計量
		for (int k = 0; k <= W; ++k)
		{
			// 現在の料理で [香辛料の合計量] k を実現するために必要な,
			// 直前の料理における [香辛料の合計量] の最小値へのイテレータ
			const auto itBegin = (dp[i - 1].begin() + std::max(0, (k - dish.R)));

			// 現在の料理で [香辛料の合計量] k を実現するために必要な,
			// 直前の料理における [香辛料の合計量] の最大値（への次の要素を指して, 範囲の終端位置を表現）するイテレータ
			const auto itEnd = (dp[i - 1].begin() + std::max(0, (k - dish.L + 1)));

			// [itBegin, itEnd) で範囲を表す. (itBegin == itEnd) の場合は, 実現不可能
			if (itBegin == itEnd)
			{
				continue;
			}

			// [itBegin, itEnd) の中で最大の価値合計値を探す
			const auto it = std::max_element(itBegin, itEnd);

			// 最大の価値合計値 -1 は, 直前の状態が実現不可能ということなのでスキップ
			if (*it != -1)
			{
				// 料理を作らない場合と作る場合の価値合計値を比較して, 大きいほうを採用
				dp[i][k] = std::max(dp[i][k], (*it + dish.V));
			}
		}
	}

	// 解答 (dp[N][W]) を出力
	std::cout << dp.back().back() << '\n';
}