第11回情オリ本選対策12日目(あと使えるのは3日!)

今日やるつもりの物

  • アリ本P126の少し考察を要するDP5問、P.253のビットDP5問
  • AOJ0550 Dividing Snacksをどうにか他人の見てでも
  • JOI Flagもどうにか
  • POJ3280 Cheapest Palindromeもどうにか
  • AOJ0232 Life Gameもどうにか
  • AOJ1056 Ben Tohもどうにか解説みて
  • 解きたきゃ解く物3問

17:00-21:50

  • POJ 1065 Wooden Sticks、他人の解見たけどあんまりDPに見えないというか他人の解がDPに見えないのでパス。よく分からないし。
  • サクサク進まねぇなぁ…生まれてはじめてSegment Tree書いたので、Range Maximum Queryの正しく動くか不明な物をおいておきますね つ
#include <cstdio>
#include <vector>
using namespace std;

class RMQ {
private:
	int n;
	vector<int> data;
public:
	RMQ(int n) {
		int t = 1;
		while (t < n) t *= 2;
		data = vector<int>(t * 2 - 1, 0);
		this->n = t;
		return;
	}
	void set(int idx, int value) {
		int k = idx + n - 1;
		data[k] = value;
		while (k > 0) {
			k = (k - 1) / 2;
			data[k] = max(data[k * 2 + 1], data[k * 2 + 2]);
		}
		return;
	}
	int query_impl(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l)
			return 0;
		if (a <= l && r <= b)
			return data[k];
		return max(
			query_impl(a, b, k * 2 + 1, l, (l + r) / 2),
			query_impl(a, b, k * 2 + 1, (l + r) / 2, r));
	}
	int query(int a, int b) {
		return query_impl(a, b, 0, 0, n);
	}
};
  • POJ1631 Bridging signals、ただのLISだが、最初気付かずぐぐってもLIS解法ではないのが上のほうに出てきていたので、なんとなくRMQを書いてしまったの図が↑。ちゃんと問題文読解しよう。あとLISのO(n log n)解法覚えてませんでしたが多分これで覚えた。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main()
{
	int n;
	scanf("%d\n", &n);
	for (int h = 0; h < n; ++h) {
		int p;
		scanf("%d\n", &p);

		vector<int> routes(p);
		for (int i = 0; i < p; ++i)
			scanf("%d\n", &routes[i]);

		vector<int> dp(p, INT_MAX);
		for (int i = 0; i < p; ++i) {
			*(lower_bound(dp.begin(), dp.end(), routes[i])) = routes[i];
		}
		int res = p - 1;
		for (int i = 0; i < p; ++i) {
			if (dp[i] == INT_MAX) {
				res = i;
				break;
			}
		}
		printf("%d\n", res);
	}
	
	return 0;
}
  • POJ3666、わからん!わからん!
  • POJ 2392 Space Elevator、ソートしてからDPというのがありえん程苦手である。数学センス皆無よろしく、脳内で証明を立てて(反例がない確信を得て)何かするのが極めて苦手。ソートさえすれば普通のDP。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

class Block {
public:
	int h, a, c;
	Block(int h, int a, int c) : h(h), a(a), c(c) {}
	bool operator<(const Block& bl) const {
		return a < bl.a;
	}
};

int main()
{
	int K;
	scanf("%d\n", &K);
	vector<Block> blocks; blocks.reserve(K);
	for (int i = 0; i < K; ++i) {
		int h, a, c;
		scanf("%d %d %d\n", &h, &a, &c);
		blocks.push_back(Block(h, a, c));
	}

	sort(blocks.begin(), blocks.end());

	vector<vector<bool> > dp(2, vector<bool>(blocks.back().a + 1, false));
	int cur = 0, prev = 1;
	dp[prev][0] = true;

	int res = 0;
	for (int i = 0; i < K; ++i) {
		for (int j = 0; j < dp[cur].size(); ++j) {
			if (!dp[prev][j])
				continue;
			for (int k = j, l = min(j + blocks[i].h * blocks[i].c, blocks[i].a);
				k <= l; k += blocks[i].h) {
				dp[cur][k] = true;
				res = max(res, k);
			}
		}
		cur = !cur, prev = !prev;
	}
	printf("%d\n", res);

	return 0;
}
  • POJ 2184 分かるはずなんだけど写経モードに入ってしまい、ためにならない上に答えあわないのでパス。
  • POJ 2441 メモ化で書いてMLEったのでDPに落としたらサンプルケース通らなくなった時の脱力感について