読者です 読者をやめる 読者になる 読者になる

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

JOI対策日記

なんか昼間はエンジンがかからなくて、「やべえいろんな物を放棄して時間作ってるのにダラダラしてるとか俺マズい」みたいな気分に夜なってからそこそこ解いた。
といっても簡単なのばっかりですが…

  • POJ 2385 Apple Catching 最初の再帰関数を立てて、脳内トポロジカルソートする所まではできたけど答えに至るにあたって他人のソースとか参照した。
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	int T, W;
	scanf("%d %d\n", &T, &W);

	vector<int> apples(T);
	for (int i = 0; i < T; ++i) {
		int cur;
		scanf("%d\n", &cur);
		apples[i] = cur - 1;
	}

	// dp[t][w][p]
	vector<vector<vector<int> > > dp(T,
		vector<vector<int> >(W + 1, vector<int>(2, 0)));

	int res = 0;
	for (int t = T - 1; 0 <= t; --t)
	for (int w = 0; w <= W; ++w)
	for (int p = 0; p < 2; ++p) {
		int& cur = dp[t][w][p];
		if (t == T - 1) {
			cur = (apples[t] == p);
		}else  if (w == 0) {
			cur = dp[t + 1][w][p] + (apples[t] == p);
		} else if (w > 0) {
			cur = max((w > 0 ? dp[t + 1][w - 1][!p] : 0), dp[t + 1][w][p]) + (apples[t] == p);
		}
		res = max(res, cur);
	}
	printf("%d\n", res);
	return 0;
}
  • POJ 3616 Milking Time、多分O(n^2)程度なんだろうなという以上の事は分からなかった。他人のソース見た。もう一度解ける自信ない。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

class Interval {
public:
	int start, end, efficient;
	Interval(int start, int end, int efficient)
		: start(start), end(end), efficient(efficient) {}
	bool operator<(const Interval& intv) const {
		return start < intv.start;
	}
};

int main()
{
	int N, M, R;
	scanf("%d %d %d\n", &N, &M, &R);
	vector<Interval> intervals; intervals.reserve(M);
	for (int i = 0; i < M; ++i) {
		int start, end, efficient;
		scanf("%d %d %d\n", &start, &end, &efficient);
		intervals.push_back(Interval(start, end, efficient));
	}
	sort(intervals.begin(), intervals.end());

	vector<int> dp(M, 0);
	int res = 0;
	for (int i = 0; i < dp.size(); ++i) {
		for (int j = 0; j < i; ++j) {
			if (intervals[j].end + R <= intervals[i].start)
				dp[i] = max(dp[i], dp[j]);
		}
		dp[i] += intervals[i].efficient;
		res = max(res, dp[i]);
	}
	printf("%d\n", res);
	return 0;
}
  • POJ 1742 Coins、殆どアリ本の個数制限付き部分和DP(P.62)そのまま。アリ本読んで理解して通した。
#include <cstdio>
#include <vector>
#include <numeric>
using namespace std;

int main()
{
	int n, m;
	while (scanf("%d %d\n", &n, &m), n || m) {
		vector<int> A(n), C(n);
		for (int i = 0; i < n; ++i)
			scanf("%d", &A[i]);
		for (int i = 0; i < n; ++i)
			scanf("%d", &C[i]);

		vector<int> dp(m + 1, -1);
		dp[0] = 0;

		for (int i = 0; i < n; ++i) {
			for (int j = 0; j <= m; ++j) {
				if (dp[j] >= 0) {
					dp[j] = C[i];
				} else if (j < A[i]) {
					dp[j] = -1;
				} else if (dp[j - A[i]] <= 0) {
					dp[j] = -1;
				} else {
					dp[j] = dp[j - A[i]] - 1;
				}
			}
		}
		int res = -1;
		for (int i = 0; i < dp.size(); ++i)
			res += (dp[i] >= 0);
		printf("%d\n", res);
	}
	return 0;
}
  • POJ 3046 Ant Counting、至って普通。なのに他人のソースをちょくちょく見た。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	const int MODULO = 1000000;
	int T, A, S, B;
	scanf("%d %d %d %d\n", &T, &A, &S, &B);
	vector<int> N(T, 0);
	for (int i = 0; i < A; ++i) {
		int t;
		scanf("%d\n", &t);
		N[t - 1]++;
	}

	vector<vector<int> > dp(T, vector<int>(B + 1, 0));
	for (int i = 0; i <= N[0]; ++i)
		dp[0][i] = 1;

	for (int i = 1; i < T; ++i) {
		for (int j = 0; j <= B; ++j) {
			int& cur = dp[i][j];
			for (int k = 0, l = min(N[i], j); k <= l; ++k) {
				cur = (cur + dp[i - 1][j - k]) % MODULO;
			}
		}
	}
	int res = 0;
	for (int i = S; i <= B; ++i) {
		res = (res + dp[T - 1][i]) % MODULO;
	}
	printf("%d\n", res);
	return 0;
}
  • POJ 3181 Dollar Dayz、なんやこの簡単なDP!とみせかけた多倍長問題。アリ本の練習問題一覧って、これ多倍長問題だっていう前提でのってるんだろうか?不明。仕方がないのでJavaに逃げる。
import java.util.*;
import java.math.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int N = s.nextInt(), K = s.nextInt();
		BigInteger[][] dp = new BigInteger[K][N + 1];
		for (int i = 0; i < N + 1; ++i) {
			dp[0][i] = BigInteger.ONE;
		}
		for (int i = 1; i < K; ++i) {
			for (int j = 0; j <= N; ++j) {
				dp[i][j] = dp[i - 1][j];
				if (i + 1 <= j)
					dp[i][j] = dp[i][j].add(dp[i][j - (i + 1)]);
			}
		}
		System.out.println(dp[K - 1][N]);
	}
}