Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI 春合宿 2013 Day1 (bustour, collecting, communication, joi_poster)

JOI

今日はJOI 春合宿2013 Day1 の問題を復習. APIO がんばるゾ.

Bus Tour (問題文は コチラ)

[どのバスか][バスの位置]を持ってdijkstra. もう訪れた地点を訪れないように枝刈りする.
実装が少し大変.

/*
	TASK : Bus Tour
	LANG : C++
	NAME : kagamiz JPN12
*/


#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cassert>

using namespace std;
typedef long long lint;

struct Event {
	int bus, T, time;
	Event(int bus, int T, int time) : bus(bus), T(T), time(time){}
};

bool operator > (const Event &a, const Event &b)
{
	return (a.time > b.time);
}

int x1[1024], y1[1024], x2[1024], y2[1024], T[1024];
vector<pair<int, int> > pt[1024][1024];
pair<int, int> get[1024][4096];
bool done[1024][4096], doneXY[1024][1024];

pair<int, int> calcPos(int x1, int y1, int x2, int y2, int T)
{
	if (T <= x2 - x1) return (make_pair(x1 + T, y1));
	if (T <= x2 - x1 + y2 - y1) return (make_pair(x2, y1 + T - (x2 - x1)));
	if (T <= 2 * (x2 - x1) + y2 - y1) return (make_pair(x2 - (T - (x2 - x1 + y2 - y1)), y2));
	return (make_pair(x1, y2 - (T - 2 * (x2 - x1) - (y2 - y1))));
}

int main()
{
	int W, H, Sx, Sy, Gx, Gy;
	int N;
	
	scanf("%d %d %d %d %d %d", &W, &H, &Sx, &Sy, &Gx, &Gy);
	--Sx; --Sy; --Gx; --Gy;
	
	scanf("%d", &N);
	
	priority_queue<Event, vector<Event>, greater<Event> > pq;
	
	for (int i = 0; i < N; i++){
		scanf("%d %d %d %d %d", x1 + i, y1 + i, x2 + i, y2 + i, T + i);
		--x1[i]; --x2[i]; --y1[i]; --y2[i];
		for (int j = 0; j < 2 * (x2[i] - x1[i] + y2[i] - y1[i]); j++){
			int p = (j + T[i]) % (2 * (x2[i] - x1[i] + y2[i] - y1[i]));
			pt[calcPos(x1[i], y1[i], x2[i], y2[i], p).first][calcPos(x1[i], y1[i], x2[i], y2[i], p).second].push_back(make_pair(i, j));
			get[i][j] = calcPos(x1[i], y1[i], x2[i], y2[i], p);
			if (get[i][j] == make_pair(Sx, Sy)){
				pq.push(Event(i, j, j));
			}
		}
	}
	
	for (; !pq.empty(); pq.pop()){
		Event t = pq.top();
		if (get[t.bus][t.T] == make_pair(Gx, Gy)) return (!printf("%d\n", t.time));
		
		if (done[t.bus][t.T]) continue;
		done[t.bus][t.T] = true;
		
		int L = 2 * (x2[t.bus] - x1[t.bus] + y2[t.bus] - y1[t.bus]);
		
		pair<int, int> now = get[t.bus][t.time % L];
		if (!doneXY[now.first][now.second]){
			for (int i = 0; i < pt[now.first][now.second].size(); i++){
				pair<int, int> nxt = pt[now.first][now.second][i];
				int L = 2 * (x2[nxt.first] - x1[nxt.first] + y2[nxt.first] - y1[nxt.first]);
				int x = (t.time + 1 - nxt.second + L - 1) / L;
				pq.push(Event(nxt.first, nxt.second, x * L + nxt.second));
			}
			doneXY[now.first][now.second] = true;
		}
		pq.push(Event(t.bus, (t.T + 1) % L, t.time + 1));
	}
	
	return (0);
}

Collecting Images is Fun (問題文はコチラ)

分割を木で遷移っぽく表すと, 4 * 分割している点 + 1 が答えになることが分かる.
分割している点 = 全体 - 白黒はっきりしている点なので, これをBIT を展開したセグメント木で数える.

/*
	TASK : Collecting Images is Fun
	LANG : C++
	NAME : kagamiz JPN12
*/


#include <cstdio>

using namespace std;

typedef long long lint;

int N, Q;
int seg[2][1 << 21];
bool bef[2][1 << 21];
lint all[2][21];

void add(int xy, int k, int x)
{
	int num = 1;
	int depth = N;
	k += (1 << N) - 1;
	seg[xy][k] += x;
	
	while (k){
		depth -= 1;
		k = (k - 1) >> 1;
		num *= 2;
		seg[xy][k] = seg[xy][k * 2 + 1] + seg[xy][k * 2 + 2];
		if (seg[xy][k] == 0 || seg[xy][k] == num){
			all[xy][depth] += !(bef[xy][k]); bef[xy][k] = true;
		}
		else {
			all[xy][depth] -= bef[xy][k]; bef[xy][k] = false;
		}
	}
}

lint count()
{
	lint sum = 0;
	lint two = 1ll;
	
	for (int i = 0; i < N; i++){
		sum += two - (all[0][i] * all[1][i]);
		two *= 4ll;
	}
	
	return (sum);
}

int main()
{
	scanf("%d %d", &N, &Q);
	
	for (int i = 0; i < 1 << N; i++){
		add(0, i, 1); add(1, i, 1);
	}
	
	int ct = 0;
	
	for (int i = 0; i < Q; i++){
		int xy, pos;
		scanf("%d %d", &xy, &pos);
		--pos;
		add(xy, pos, seg[xy][pos + (1 << N) - 1] ? -1 : 1);
		
		printf("%lld\n", 4 * count() + 1);
	}
	
	return (0);
}

Communication Jamming (問題文はコチラ)

"任意の 2 つの回線は端点同士以外で共有点を持たないようになっていることが保証されている．" という記述により, 平面性が成り立つことが分かる. したがって, 両隣が接続されているかのみを確認すれば良い.
これは, LCA を使えばコーナーケースを考えずに実装できる.
クエリが来る度に, 高さについてしゃく取り法のようなことを行えば良い.

/*
	TASK : Communication Jamming
	LANG : C++
	NAME : kagamiz JPN12
*/


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

#define MAX_N (100000)
#define MAX_M (100000)
#define MAX_Q (100000)

using namespace std;

int x1[MAX_N + MAX_M], y1[MAX_N + MAX_M], x2[MAX_N + MAX_M], y2[MAX_N + MAX_M];
int q1[MAX_N], q2[MAX_N]; //highest position of (i, i + 1)
int par1[20][MAX_N + MAX_M], par2[20][MAX_N + MAX_M];
int hi1[20][MAX_N + MAX_M], hi2[20][MAX_N + MAX_M];
int dep1[MAX_N + MAX_M], dep2[MAX_N + MAX_M]; 
int res[MAX_Q];
pair<int, int> Qmem[MAX_Q];
vector<int> G1[MAX_N + MAX_M], G2[MAX_N + MAX_M];

void dfs(int v, int p, int d, vector<int> *G, int par[][MAX_N + MAX_M], int dep[], int hi[][MAX_N + MAX_M], int y[])
{
	par[0][v] = p;
	if (~p) hi[0][v] = max(abs(y[v]), abs(y[p]));
	else hi[0][v] = abs(y[v]);
	dep[v] = d;
	
	for (int i = 0; i < G[v].size(); i++){
		if (G[v][i] != p) dfs(G[v][i], v, d + 1, G, par, dep, hi, y);
	}
}

int qLCA(int u, int v, int par[][MAX_N + MAX_M], int dep[], int hi[][MAX_N + MAX_M], int y[])
{
	int res = max(abs(y[u]), abs(y[v]));
	if (dep[u] < dep[v]) swap(u, v);
	
	for (int i = 19; i >= 0; i--){
		if (((dep[u] - dep[v]) >> i) & 1){
			res = max(res, hi[i][u]);
			u = par[i][u];
		}
	}
	if (u == v) return (res);
	
	for (int i = 19; i >= 0; i--){
		if (par[i][u] != par[i][v]){
			res = max(res, max(hi[i][u], hi[i][v]));
			u = par[i][u], v = par[i][v];
		}
	}
	res = max(res, hi[0][u]);
	return (res);
}

void init(vector<int> *G, int par[][MAX_N + MAX_M], int dep[], int hi[][MAX_N + MAX_M], int y[], int q[])
{
	memset(par, -1, sizeof(par));
	dfs(0, -1, 0, G, par, dep, hi, y);
	
	for (int i = 1; i < 20; i++){
		for (int j = 0; j < MAX_N + MAX_M; j++){
			if (~par[i - 1][j]){
				par[i][j] = par[i - 1][par[i - 1][j]];
				hi[i][j] = max(hi[i - 1][j], hi[i - 1][par[i - 1][j]]);
			}
		}
	}
	
	for (int i = 0; i < MAX_N - 1; i++){
		q[i] = qLCA(i, i + 1, par, dep, hi, y);
	}
} 

int main()
{
	int N, m1, m2, Q;
	
	scanf("%d %d %d %d", &N, &m1, &m2, &Q);
	
	for (int i = 0; i < N; i++)
		x1[i] = x2[i] = i + 1, y1[i] = y2[i] = 0;
	
	for (int i = 0; i < m1; i++)
		scanf("%d %d", x1 + i + N, y1 + i + N);
	
	for (int i = 0; i < N + m1 - 1; i++){
		int T, C, D;
		scanf("%d %d %d", &T, &C, &D);
		if (T == 1){
			G1[C - 1].push_back(D - 1 + N);
			G1[D - 1 + N].push_back(C - 1);
		}
		else {
			G1[C - 1 + N].push_back(D - 1 + N);
			G1[D - 1 + N].push_back(C - 1 + N);
		}
	}
	
	for (int i = 0; i < m2; i++)
		scanf("%d %d", x2 + i + N, y2 + i + N);
	
	for (int i = 0; i < N + m2 - 1; i++){
		int T, C, D;
		scanf("%d %d %d", &T, &C, &D);
		if (T == 1){
			G2[C - 1].push_back(D - 1 + N);
			G2[D - 1 + N].push_back(C - 1);
		}
		else {
			G2[C - 1 + N].push_back(D - 1 + N);
			G2[D - 1 + N].push_back(C - 1 + N);
		}
	}
	
	init(G1, par1, dep1, hi1, y1, q1); init(G2, par2, dep2, hi2, y2, q2);
	
	vector<pair<int, int> > villages;
	for (int i = 0; i < N - 1; i++){
		villages.push_back(make_pair(q1[i], i));
	}
	
	sort(villages.rbegin(), villages.rend());
	
	for (int i = 0; i < Q; i++){
		scanf("%d", &Qmem[i].first);
		Qmem[i].second = i;
	}
	
	sort(Qmem, Qmem + Q); reverse(Qmem, Qmem + Q);
	
	int ans = 0, ptr = 0;
	for (int i = 0; i < Q; i++){
		while (ptr != N - 1 && Qmem[i].first < villages[ptr].first){
			ans = max(ans, q2[villages[ptr].second]);
			ptr++;
		}
		res[Qmem[i].second] = ans;
	}
	
	for (int i = 0; i < Q; i++)
		printf("%d\n", -res[i]);
	
	
	return (0);
}

JOI Poster (問題文はコチラ)
n ≦ 50 なので, 4 点に対して全探索が行える.
円の交差判定は, EPS を使ってごまかす. できるだけ実数演算をしないように工夫するとときやすい.

/*
	TASK : JOI Poster
	LANG : C++
	NAME : kagamiz JPN12
*/

#include <cstdio>
#include <cmath>
#include <algorithm>

#define two(x) ((x) * (x))

using namespace std;

int W, H;
int res;
int x[64], y[64];
const double EPS = 1e-7;

bool ok(int a, int b, int c)
{
	int D = b * b - 4 * a * c;
	if (D > 0) return (false);
	return (true);
}

bool satisfy(int a, int b, int c, int d)
{
	int dist = two(x[a] - x[c]) + two(y[a] - y[c]);
	int    r1 = two(x[a] - x[b]) + two(y[a] - y[b]),
		   r2 = two(x[c] - x[d]) + two(y[c] - y[d]);
	
	//1.
	if (r1 <= r2) return (false);
	if (sqrt(dist) - (sqrt(r1) + sqrt(r2)) + EPS >= 0) return (false);
	if ((sqrt(r1) - sqrt(r2)) - sqrt(dist) <= EPS) return (false);
	
	//2.
	if (!ok(1, -2 * y[a], - r1 + x[a] * x[a] + y[a] * y[a])) return (false);
	if (!ok(1, -2 * y[a], - r1 + (W - x[a]) * (W - x[a]) + y[a] * y[a])) return (false);
	if (!ok(1, -2 * x[a], - r1 + y[a] * y[a] + x[a] * x[a])) return (false);
	if (!ok(1, -2 * x[a], - r1 + (H - y[a]) * (H - y[a]) + x[a] * x[a])) return (false);
	
	return (true);
}

int main()
{
	int N;
	
	scanf("%d %d %d", &N, &W, &H);
	
	for (int i = 0; i < N; i++){
		scanf("%d %d", x + i, y + i);
	}
	
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			if (i == j) continue;
			for (int k = 0; k < N; k++){
				if (i == k || j == k) continue;
				for (int l = 0; l < N; l++){
					if (i == l || j == l || k == l) continue;
					if (satisfy(i, j, k, l)) res++;
				}
			}
		}
	}
	
	printf("%d\n", res);
        return (0);
}