JOI2007 本選

友達に勉強を教えながら, ゆったり2007を解いてみました.
4 -> 3 -> 2 -> 1 -> 5 の順で解きました. 4 が一番簡単なんだよなあ...
1時間半くらい余らせて終了.

1. 碁石並べ

シミュレーションを行う. オセロっぽい操作を行う.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> P;

int main()
{
	int n;
	while (scanf("%d", &n) && n){
		vector<P> line;
		for (int i = 0; i < n; i++){
			int col;
			scanf("%d", &col);
			if (!i) line.push_back(make_pair(col, 1));
			else if (i % 2 == 0){
				if (line.size() && line[line.size() - 1].first == col){
					line[line.size() - 1].second++;
				}
				else line.push_back(make_pair(col, 1));
			}
			else {
				if (line[line.size() - 1].first == col) line[line.size() - 1].second++;
				else {
					line[line.size() - 1].first = col;
					line[line.size() - 1].second++;
					if (line.size() > 1 && line[line.size() - 2].first == col){
						line[line.size() - 2].second += line[line.size() - 1].second;
						line.erase(line.end() - 1, line.end());
					}
				}
			}
		}
		int sum = 0;
		for (int i = 0; i < line.size(); i++) if (line[i].first == 0) sum += line[i].second;
		
		printf("%d\n", sum);
	}
	return (0);
}

2. 共通部分文字列

共通部分列と勘違いしてヤバい式を入れて1 WA をいただきました. 気をつけます...

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long lint;

int main()
{
	char s[4096], t[4096];
	static int dp[2][4096];
	
	while (scanf("%s", s) == 1){
		scanf("%s", t);
		
		memset(dp, 0, sizeof(dp));
		
		int ans = 0;
		
		for (int i = 1; s[i - 1]; i++){
			for (int j = 1; t[j - 1]; j++){
				if (s[i - 1] == t[j - 1])
					dp[i & 1][j] = dp[(i - 1) & 1][j - 1] + 1;
				else dp[i & 1][j] = 0;
				ans = max(ans, dp[i & 1][j]);
			}
		}
		
		printf("%d\n", ans);
	}
	
	return (0);
}

3. ダーツ

今となっては有名な半分全列挙の問題. upper_bound便利.

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long lint;

int main()
{
	lint n, m;
	lint score[1024];
	static lint pSum[512 * 1023];
	
	while (scanf("%lld %lld", &n, &m) && n){
		
		for (int i = 0; i < n; i++){
			scanf("%lld", score + i);
		}
		score[n++] = 0;
		
		int k = 0;
		for (int i = 0; i < n; i++){
			for (int j = i; j < n; j++){
				pSum[k++] = score[i] + score[j];
			}
		}
		
		sort(pSum, pSum + k);
		
		lint res = 0;
		for (int i = 0; i < k; i++){
			if (pSum[i] > m) break;
			res = max(res, pSum[i] + *(upper_bound(pSum, pSum + k, m - pSum[i]) - 1));
		}
		
		printf("%lld\n", res);
	}
	return (0);
}

4. ぴょんぴょん川渡り

メモ化再帰氏を使う. DPでやったときバグらせたのを思い出した. (DP苦手らしい)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>

using namespace std;

int k[256];
int x[256][16], d[256][16];
int memo[256][16][128];
int n, m;

int getMin(int nowY, int idx, int left)
{
	if (nowY == n) return (0);
	if (~nowY && memo[nowY][idx][left] >= 0) return (memo[nowY][idx][left]);
	
	int res = INT_MAX;
	
	for (int i = 0; i < k[nowY + 1]; i++){
		int bad = (nowY == -1 || nowY == n - 1 ? 0 : (d[nowY][idx] + d[nowY + 1][i]) * abs(x[nowY][idx] - x[nowY + 1][i]));
		res = min(res, getMin(nowY + 1, i, left) + bad);
	}
	
	if (left && nowY + 2 <= n){
		for (int i = 0; i < k[nowY + 2]; i++){
			int bad = (nowY == -1 || nowY == n - 2 ? 0 : (d[nowY][idx] + d[nowY + 2][i]) * abs(x[nowY][idx] - x[nowY + 2][i]));
			res = min(res, getMin(nowY + 2, i, left - 1) + bad);
		}
	}
	
	if (~nowY) memo[nowY][idx][left] = res;
	return (res);
}

int main()
{
	while (scanf("%d %d", &n, &m) && n){
		
		for (int i = 0; i < n; i++){
			scanf("%d", k + i);
			for (int j = 0; j < k[i]; j++){
				scanf("%d %d", &x[i][j], &d[i][j]);
			}
		}
		k[n] = 1;
		
		memset(memo, -1, sizeof(memo));
		
		printf("%d\n", getMin(-1, 0, m));
		
	}
	return (0);
}

5. ペンキの色

座標圧縮氏を行う. 境界周りの処理が少しむずかしいが, 点Xを区間[X, X + 1]に対応させると解きやすい.
今年の予選 5 の応用っぽい問題. JOI は過去問力がある程度試される気がする.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

typedef pair<int, int> P;

bool exist[2048][2048];
int x1[1024], y1[1024], x2[1024], y2[1024];
vector<int> xs, ys;
map<int, int> convX, convY;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};


int main()
{
	int X, Y, N;
	
	while (scanf("%d %d", &X, &Y) && X){
		scanf("%d", &N);
		
		for (int i = 0; i < N; i++){
			scanf("%d %d %d %d", x1 + i, y1 + i, x2 + i, y2 + i);
			xs.push_back(x1[i]); xs.push_back(x2[i]);
			ys.push_back(y1[i]); ys.push_back(y2[i]);
		}
		
		xs.push_back(0); xs.push_back(X - 1);
		ys.push_back(0); ys.push_back(Y - 1);
		
		sort(xs.begin(), xs.end());
		sort(ys.begin(), ys.end());
		
		xs.erase(unique(xs.begin(), xs.end()), xs.end());
		ys.erase(unique(ys.begin(), ys.end()), ys.end());
		
		for (int i = 0; i < xs.size(); i++) convX[xs[i]] = i;
		for (int i = 0; i < ys.size(); i++) convY[ys[i]] = i;
		
		memset(exist, 0, sizeof(exist));
		
		for (int i = 0; i < N; i++){
			for (int y = convY[y1[i]]; y < convY[y2[i]]; y++){
				for (int x = convX[x1[i]]; x < convX[x2[i]]; x++){
					exist[y][x] = true;
				}
			}
		}
		
		int ret = 0;
		
		for (int y = 0; y <= convY[Y - 1]; y++){
			for (int x = 0; x <= convX[X - 1]; x++){
				if (!exist[y][x]){
					exist[y][x] = true;
					queue<P> q;
					
					for (q.push(P(y, x)); q.size(); q.pop()){
						P x = q.front();
						for (int i = 0; i < 4; i++){
							int ny = x.first + dy[i], nx = x.second + dx[i];
							if (0 <= ny && ny <= convY[Y - 1] &&
									0 <= nx && nx <= convX[X - 1] &&
										exist[ny][nx] == false){
								exist[ny][nx] = true;
								q.push(P(ny, nx));
							}
						}
					}
					ret++;
				}
			}
		}
		printf("%d\n", ret);
	}
	return (0);
}