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

日本情報オリンピック(JOI) 第11回予選 自分の提出した解答

Programming Algorithm JOI

kyuridenamida解と比較したので多分答えられた部分についてはあってる。

JOI 2011-2012 予選 問題・採点用入力

全体の感想としては、1-3は去年より一段ひねってあるというか、面倒な感じで、4は去年の4番のDPよりは少し難化していると思う。
5が去年の比でなく面倒だった。6はさっぱり分からなかった。6が解けている人が周囲にそれなりにいるので、そこは残念だが、4が解けてよかった。

問題1. ランチ (Lunch)

最も小さい物2つを選んで50を引くだけ。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> read(int n)
{
	vector<int> v(n);
	for (int i = 0; i < n; ++i)
		scanf("%d\n", &v[i]);
	sort(v.begin(), v.end());
	return v;
}

int main()
{
	const vector<int> pasta = read(3);
	const vector<int> juice = read(2);
	const int res = pasta[0] + juice[0] - 50;
	printf("%d\n", res);
	return 0;
}

問題2. サッカー (Soccer)

それぞれのチームの点数を計算して、順位をつけるだけ。
同じ点数のチームを同順にする、っていう操作がきれいに書けない。
ライブラリゲーとかのような気もしたがどうなんだろう。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int N;
	scanf("%d\n", &N);
	vector<int> scores(N, 0);

	for (int i = 0, l = N * (N - 1) / 2; i < l; ++i) {
		int A, B, C, D;
		scanf("%d %d %d %d\n", &A, &B, &C, &D);
		A--, B--;
		if (C > D) {
			scores[A] += 3;
		} else if (C < D) {
			scores[B] += 3;
		} else {
			scores[A]++;
			scores[B]++;
		}
	}

	vector<pair<int, int> > sorted(N);
	for (int i = 0; i < scores.size(); ++i) {
		sorted[i].first = scores[i];
		sorted[i].second = i;
	}

	sort(sorted.rbegin(), sorted.rend());

	vector<int> ranks(N);
	for (int i = 0; i < sorted.size(); ++i) {
		ranks[sorted[i].second] = i + 1;
		if (0 < i) {
			if (sorted[i - 1].first == sorted[i].first) {
				ranks[sorted[i].second] = ranks[sorted[i - 1].second];
			}
		}
	}

	for (int i = 0; i < ranks.size(); ++i) {
		printf("%d\n", ranks[i]);
	}

	return 0;
}

問題3. 最高のピザ (Best Pizza)

トッピングをして金額あたりのカロリーの最も高いピザを作る。トッピングの値段は全部同じなので、
トッピングを1個ものせない所からはじめて、カロリーの高い具から順にのっけていって、最大になる所で止める。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	int N, A, B, C;
	scanf("%d\n%d %d\n%d\n", &N, &A, &B, &C);

	vector<int> D(N);
	for (int i = 0; i < N; ++i) {
		scanf("%d\n", &D[i]);
	}
	sort(D.rbegin(), D.rend());

	int price = A, calorie = C;
	int res = calorie / price;
	for (int i = 0; i < N; ++i) {
		price += B;
		calorie += D[i];
		int cur = calorie / price;
		if (res > cur) {
			break;
		}
		res = cur;
	}
	printf("%d\n", res);

	return 0;
}

問題4. パスタ (Pasta)

見た瞬間多分DPだなと思ったけれども分からずに固まって、問題5にいった。
落ち着いて考えたら、

f(n, tomorrow、today) = 今日はtodayのソースのパスタを食い、昨日はtomorrowのソースのパスタを食った時のn日まで献立の組み合わせの数

という関数を再帰的に定義して、メモ化する事で解ける事に気付いた。

トップダウン式にコードが書けて満足している。というかはじめて本番でDP解けた。ので相当喜んでいる。

#include <cstdio>
#include <vector>
#include <climits>
using namespace std;

class Pasta {
public:
	int N;
	vector<int> fixed;
	vector<vector<int> > dp;
	static const int MODULO = 10000;

	Pasta(int N)
	{
		this->N = N;
		fixed = vector<int>(N, INT_MAX);
		dp = vector<vector<int> >(N, vector<int>(1 << 4, INT_MAX));
		return;
	}

	void set(int A, int B)
	{
		fixed[A - 1] = B - 1;
		return;
	}

	inline int f_impl(int n, int yesterday, int today)
	{
		if (fixed[n] != INT_MAX && fixed[n] != today)
			return 0;

		int res = 0;

		if (n == 1) {
			if (fixed[0] != INT_MAX && fixed[0] != yesterday)
				return 0;
			else
				return 1;
		}

		for (int i = 0; i < 3; ++i) {
			if (yesterday == today && i == today)
				continue;
			res = (res + f(n - 1, i, yesterday)) % MODULO;
		}
		return res;
	}

	int f(int n, int yesterday, int today)
	{
		int& cur = dp[n][(yesterday<<2) + today];
		return (cur != INT_MAX ? cur : (cur = f_impl(n, yesterday, today)));
	}

	int start()
	{
		int res = 0;
		for (int i = 0; i < 3; ++i)
		for (int j = 0; j < 3; ++j) {
			res = (res + f(N - 1, i, j)) % MODULO;
		}
		return res;
	}
};
int main()
{
	int N, K;
	scanf("%d %d\n", &N, &K);

	Pasta pasta(N);
	for (int i = 0; i < K; ++i) {
		int A, B;
		scanf("%d %d\n", &A, &B);
		pasta.set(A, B);
	}

	const int res = pasta.start();
	printf("%d\n", res);
	return 0;
}

問題5. イルミネーション (Illumination)

ハニカム状の平面の問題。別にハニカムはライブラリゲーでもないと思うし、一度見た事があれば難しくないとは思うが、問題文の座標の振り方(の記述)が読みづらくて、結果的に2,30分ぐらい食ってしまった。

#include <cstdio>
#include <vector>
using namespace std;

inline bool isValid(int x, int y, vector<vector<int> >& v)
{
	return 0 <= x && x < v.size() && 0 <= y && y < v[0].size();
}

int search (int x, int y, vector<vector<int> >& v)
{
	const int
	dx[] = {1, (y % 2 ? 1: 0), (y % 2 ? 0 : -1), -1, (y % 2 ? 0: -1), (y % 2 ? 1 : 0)},
	dy[] = {0, -1, -1, 0, 1, 1};

	int res = 0;

	for (int i = 0; i < 6; ++i) {
		const int nx = x + dx[i], ny = y + dy[i];
		if(!isValid(nx, ny, v))
			continue;
		if (v[nx][ny] == 1) {
			res++;
		} else if (v[nx][ny] == 0) {
			v[nx][ny] = 2;
			res += search(nx, ny, v);
		}

	}
	return res;
}

int main()
{
	int W, H;
	scanf("%d %d\n", &W, &H);
	vector<vector<int> > v(W + 2, vector<int>(H + 2, 0));
	for (int i = 0; i < H; ++i)
	for (int j = 0; j < W; ++j) {
		scanf("%d", &v[j + 1][i + 1]);
	}

	const int res = search(0, 0, v);
	printf("%d\n", res);
	return 0;
}

問題6. ジグザグ数 (Zig-Zag Numbers)

どうやって解くんです?解きたきゃ解かしてくれるらしい。

といいつつ解法考えるために書いた総当たりソースで4点。