USACO2012 December Bronze

結果 : oo△ 700 / 1000pts.

3問目をバグらせてしまいBronze残留です. 来月はSilver行きます><.

それぞれの問題の詳細な解説はサイトにあるのでコードのみ.

1. Meet and Greet
入力数に比例した時間の解法があるみたいですが, 解いた時頭が回っていなかったので愚直解.

#include <cstdio>
#include <cstring>

using namespace std;

int timeB[1000010], timeE[1000010];

int main()
{
	freopen("greetings.in", "r", stdin);
	freopen("greetings.out", "w", stdout);
	
	int B, E;
	
	scanf("%d %d", &B, &E);
	
	memset(timeB, -1, sizeof(timeB));
	memset(timeE, -1, sizeof(timeE));
	
	int pos = 0;
	int tot = 1;
	timeB[0] = timeE[0] = 0;
	for (int i = 0; i < B; i++){
		int dist;
		char dir[2];
		
		scanf("%d %s", &dist, dir);
		
		for (int j = 0; j < dist; j++){
			pos += 1 * (dir[0] == 'R' ? 1 : -1);
			timeB[tot++] = pos;
		}
	}
	while (tot <= 1000000) timeB[tot++] = pos;
	
	pos = 0;
	tot = 1;
	for (int i = 0; i < E; i++){
		int dist;
		char dir[2];
		
		scanf("%d %s", &dist, dir);
		
		for (int j = 0; j < dist; j++){
			pos += 1 * (dir[0] == 'R' ? 1 : -1);
			timeE[tot++] = pos;
		}
	}
	while (tot <= 1000000) timeE[tot++] = pos;
	
	int ans = 0;
	pos = 0;
	while (1){
		while (timeB[pos] == timeE[pos]){
			pos++;
			if (pos > 1000000) break;
		}
		while (timeB[pos] != timeE[pos]){
			pos++;
			if (pos > 1000000) break;
		}
		if (pos > 1000000) break;
		ans += 1;
	}
	
	printf("%d\n", ans);
	
	return (0);
}

2. Scrambled Letters

IOI(春合宿の問題)を感じました.

#include <iostream>
#include <cstdio>
#include <algorithm>

#define MAX_N (50000)

using namespace std;

string dic[MAX_N], back[MAX_N];
string mdic[MAX_N], mback[MAX_N];

int main()
{
	freopen("scramble.in", "r", stdin);
	freopen("scramble.out", "w", stdout);
	
	int n;
	
	cin >> n;
	
	for (int i = 0; i < n; i++){
		string in;
		cin >> in;
		sort(in.begin(), in.end());
		dic[i] = mdic[i] = in;
		reverse(in.begin(), in.end());
		back[i] = mback[i] = in;
	}
	
	sort(dic, dic + n);
	sort(back, back + n);
	
	for (int i = 0; i < n; i++){
		printf("%d %d\n", lower_bound(back, back + n, mdic[i]) - back + 1, upper_bound(dic, dic + n, mback[i]) - dic);
	}
	
	return (0);
}

3. Crazy Fences

問題文をちゃんと読んでいなくて, グループの数を出力していた. こういう時の座標圧縮は, ある点P(x)について, x * 2を点, x * 2 + 1を辺として持つとうまくいく事が多いということに気づいた.

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

#define INF (1 << 30)

using namespace std;

typedef pair<int, int> P;

char field[5010][5010];

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

int main()
{
	int N, C;
	vector<int> xs, ys;
	map<int, int> convx, convy;
	int x1[512], y1[512], x2[512], y2[512];
	int cx[512], cy[512];
	
	
	freopen("crazy.in", "r", stdin);
	freopen("crazy.out", "w", stdout);
	
	
	scanf("%d %d", &N, &C);
	
	x1[0] = 0; y1[0] = 0; x2[0] = INF; y2[0] = 0;
	x1[1] = 0; y1[1] = 0; x2[1] = 0; y2[1] = INF;
	x1[2] = 0; y1[2] = INF; x2[2] = INF; y2[2] = INF;
	x1[3] = INF; y1[3] = 0; x2[3] = INF; y2[3] = INF;
	
	xs.push_back(0); xs.push_back(INF);
	ys.push_back(0); ys.push_back(INF);
	
	for (int i = 4; i < N + 4; i++){
		scanf("%d %d %d %d", x1 + i, y1 + i, x2 + i, y2 + i);
		x1[i]++; x2[i]++; y1[i]++; y2[i]++;
		if (x1[i] > x2[i]) swap(x1[i], x2[i]);
		if (y1[i] > y2[i]) swap(y1[i], y2[i]);
		xs.push_back(x1[i]); xs.push_back(x2[i]);
		ys.push_back(y1[i]); ys.push_back(y2[i]);
	}
	
	for (int i = 0; i < C; i++){
		scanf("%d %d", cx + i, cy + i);
		cx[i]++; cy[i]++;
		xs.push_back(cx[i]); ys.push_back(cy[i]);
	}
	
	sort(xs.begin(), xs.end()); sort(ys.begin(), ys.end());
	
	int idx = 0;
	convx[xs[0]] = idx++;
	for (int i = 1; i < xs.size(); i++){
		if (xs[i] != xs[i - 1]) convx[xs[i]] = idx++;
	}
	
	idx = 0;
	convy[ys[0]] = idx++;
	for (int i = 1; i < ys.size(); i++){
		if (ys[i] != ys[i - 1]) convy[ys[i]] = idx++;
	}
	
	for (int i = 0; i < N + 4; i++){
		for (int x = convx[x1[i]] * 2; x <= convx[x2[i]] * 2; x++){
			for (int y = convy[y1[i]] * 2; y <= convy[y2[i]] * 2; y++){
				field[y][x] = 1;
			}
		}
	}
	
	for (int i = 0; i < C; i++){
		field[convy[cy[i]] * 2][convx[cx[i]] * 2] = 2;
	}
	
	int ans = 0;
	for (int i = 0; i < 5010; i++){
		for (int j = 0; j < 5010; j++){
			if (field[i][j] != 1){
				int cow = field[i][j] == 2;
				field[i][j] = 1;
				queue<P> q;
				
				for (q.push(P(i, j)); !q.empty(); q.pop()){
					P tmp = q.front();
					
					for (int d = 0; d < 4; d++){
						int ny = tmp.first + dy[d], nx = tmp.second + dx[d];
						if (0 <= ny && ny < 5010 && 0 <= nx && nx < 5010 && field[ny][nx] != 1){
							cow += (field[ny][nx] == 2);
							field[ny][nx] = 1;
							q.push(P(ny, nx));
						}
					}
				}
				ans = max(ans, cow);
			}
		}
	}
	
	printf("%d\n", ans);
	
	return (0);
}