USACO 2014 January Contest, Gold

今月と見せかけて先月のGoldを解きました。

Problem 1. Cow Curling
N点から3点選んでできる三角形の領域の和集合が凸包になっていることがわかるので、凸包を作る。
N <= 50000なためN^2ができずつらぽよするが、凸包の点を始点から見た角度でsortすると二分探索で含まれそうな三角形がわかり、外積を使って三角形の内外判定をすると判定できる。
これはテストケースがもっと強いと落ちるかもナアと思う

O(N log N)

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

typedef long long ll;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#undef DEBUG

int n;
int sa, sb;

struct PO{
    ll x, y;
    PO(){}
    PO(ll x, ll y) : x(x), y(y){}
    ll cross(PO p){ return x * p.y - y * p.x; }
    PO operator - (PO p){ return PO(x - p.x, y - p.y); }
    bool operator < (const PO& p) const{ return x == p.x ? y < p.y : x < p.x; }
};

PO a[50010], b[50010];

vector<PO> conhull(PO* p){
    sort(p, p + n);
    int now = 0; 
    vector<PO> vec(n * 2);
    rep(i, n){
	while(now > 1 && (vec[now - 1] - vec[now - 2]).cross(p[i] - vec[now - 1]) <= 0) --now;
	vec[now++] = p[i];
    }
    for(int i = n - 2, la = now; i >= 0; --i){
	while(now > la && (vec[now - 1] - vec[now - 2]).cross(p[i] - vec[now - 1]) <= 0) --now;
	vec[now++] = p[i];
    }
    vec.resize(now - 1);
    return vec;
}

bool in(PO g, PO gg, PO ggg, PO ob){
    if((gg - g).cross(ob - g) < 0) return false;
    if((ggg - gg).cross(ob - gg) < 0) return false;
    if((g - ggg).cross(ob - ggg) < 0) return false;
    return true;
}

int main(){
    freopen("curling.in", "r", stdin);
    freopen("curling.out", "w", stdout);   
    scanf("%d", &n);
    rep(i, n) scanf("%lld %lld", &a[i].x, &a[i].y);
    rep(i, n) scanf("%lld %lld", &b[i].x, &b[i].y);
    vector<PO> aa = conhull(a);
    vector<PO> bb = conhull(b);

#ifdef DEBUG
    puts("\naa");
    rep(i, aa.size()) printf("%lld %lld\n", aa[i].x, aa[i].y);
    puts("\nbb");
    rep(i, bb.size()) printf("%lld %lld\n", bb[i].x, bb[i].y);    
#endif

    PO st = aa[0];
    vector<double> v;
    rep(i, aa.size()) if(i) v.pb(atan2(aa[i].y - st.y, aa[i].x - st.x));
    //rep(i, v.size()) cout << 180 * v[i] / PI << endl;

    rep(i, n){
	double r = atan2(b[i].y - st.y, b[i].x - st.x);
	if(r < v[0] || r > v.back()) continue;
	if(v.size() == 1){
	    sa += (b[i] < aa[1]);
	    continue;
	}
	vector<double>::iterator it;
	it = lower_bound(v.begin(), v.end(), r);
	bool f = false;
	if(it != v.begin()){
	    int t = it - v.begin() + 1;
	    f |= in(st, aa[t-1], aa[t], b[i]);
	}
	if(it + 1 != v.end()){
	    int t = it - v.begin() + 1;	    
	    f |= in(st, aa[t], aa[t+1], b[i]);
	}
	sa += f;
    }
    //debug(sa);

    v.clear();
    st = bb[0];
    rep(i, bb.size()) if(i) v.pb(atan2(bb[i].y - st.y, bb[i].x - st.x));
    //rep(i, v.size()) cout << 180 * v[i] / PI << endl;

    rep(i, n){
	double r = atan2(a[i].y - st.y, a[i].x - st.x);
	if(r < v[0] || r > v.back()) continue;
	if(v.size() == 1){
	    sb += (a[i] < bb[1]);
	    continue;
	}
	vector<double>::iterator it;
	it = lower_bound(v.begin(), v.end(), r);
	bool f = false;

	if(it != v.begin()){
	    int t = it - v.begin() + 1;
	    f |= in(st, bb[t-1], bb[t], a[i]);
	}
	if(it + 1 != v.end()){
	    int t = it - v.begin() + 1;	    
	    f |= in(st, bb[t], bb[t+1], a[i]);
	}
	sb += f;
    }
    //debug(sb);
    printf("%d %d\n", sa, sb);
    return 0;
}

Problem 2. Building a Ski Course
明らかに二分探索できるので、判定を考えると、逆から辿っていくと簡単に調べることができる。
こういうのは計算量がわからない

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)

int n, m;
int lb = 1, ub;
char gri[110][110];
int gr[110][110];
bool done[110][110];
bool pr[110][110];

bool ok(int x){
    memset(done, 0, sizeof(done));
    memset(pr, 0, sizeof(pr));

    while(true){
	bool f = false;
	for(int i = 0; i <= n - x; ++i){
	    for(int j = 0; j <= m - x; ++j){
		if(pr[i][j]) continue;
		bool s[2]; 
		s[0] = s[1] = false;
		rep(k, x) rep(l, x) if(!done[i+k][j+l]){
		    s[gr[i+k][j+l]] = true;
		    if(s[0] && s[1]) break;
		}
		if(!(s[0] || s[1])) continue;
		if(s[0] && s[1]) continue;
		rep(k, x) rep(l, x) done[i+k][j+l] = true;
		f = true;
		pr[i][j] = true;
	    }
	}
	if(!f) break;
    }

    rep(i, n) rep(j, m) if(!done[i][j]) return false;
    return true;
}

int main(){
    freopen("skicourse.in", "r", stdin);
    freopen("skicourse.out", "w", stdout);
    scanf("%d %d", &n, &m);
    ub = min(n, m) + 1;
    rep(i, n){
	scanf("%s", gri[i]);
	rep(j, m) gr[i][j] = (gri[i][j] == 'R');
    }
    
    while(ub - lb > 1){
	int mid = (ub + lb) / 2;
	if(ok(mid)) lb = mid;
	else ub = mid;
    }

    printf("%d\n", lb);
    return 0;
}

Problem 3. Ski Course Rating
結構面白かった。辺のコストをelevationの差の絶対値としたグリッドグラフを考える。
コストが小さい順に頂点を併合していき、集合のサイズが一定値以上に初めてなった時のコストを頑張ってunionfindに覚えさせる。つらぽよ。
O(NM*hoge)っぽい

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

typedef pair<int, int> P;
typedef long long ll;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)

int n, m, t;

struct unionfind{
    vector<int> par, rank, sz, ra;
    unionfind(){}

    void init(int n_){
	par.resize(n_);
	rank.resize(n_);
	sz.resize(n_);
	ra.resize(n_);
	rep(i, n_){
	    par[i] = i;
	    rank[i] = 0;
	    sz[i] = 1;
	    ra[i] = -1;
	}
    }
    
    inline int find(int x){
	if(par[x] != x) find(par[x]);
	if(ra[x] == -1) ra[x] = ra[par[x]] == -1 ? ra[par[par[x]]] : ra[par[x]];
	return par[x] = par[par[x]];
    }

    void unite(int x, int y){
	x = find(x); y = find(y);
	if(x == y) return ;

	if(rank[x] < rank[y]){
	    par[x] = y;
	    sz[y] += sz[x];
	}else{
	    par[y] = x;
	    sz[x] += sz[y];
	    rank[x] += (rank[x] == rank[y]);    
	}
    }

    inline bool same(int x, int y){ return find(x) == find(y); }
    inline int get_rate(int x){ return ra[x]; }
    inline int get_sz(int x){ return sz[find(x)]; }
}uf;

pair<int, P > e[500010];
int val[510][510];
int st[250010];
int now;
ll ret;

int main(){
    freopen("skilevel.in", "r", stdin);
    freopen("skilevel.out", "w", stdout);
    scanf("%d %d %d", &n, &m, &t);
    rep(i, n) rep(j, m)	scanf("%d", &val[i][j]);
    rep(i, n * m) scanf("%d", &st[i]);
    rep(i, n){
	rep(j, m){
	    if(j < m - 1) e[now++] = mp(abs(val[i][j] - val[i][j+1]), mp(i * m + j, i * m + j + 1));
	    if(i < n - 1) e[now++] = mp(abs(val[i][j] - val[i+1][j]), mp(i * m + j, (i + 1) * m + j));
	}
    }
    sort(e, e + now);
    uf.init(n * m);

    rep(i, now){
	int cost = e[i].fi;
	int a = e[i].se.fi, b = e[i].se.se;
	if(uf.same(a, b)) continue;
	a = uf.find(a); b = uf.find(b);
	int as = uf.get_sz(a), bs = uf.get_sz(b);
	if(as + bs >= t){
	    if(as < t) uf.ra[a] = cost;
	    if(bs < t) uf.ra[b] = cost;
	}
	uf.unite(a, b);
    }
    rep(i, n * m) if(st[i]){
	uf.find(i);
	ret += uf.get_rate(i);
    }
    printf("%lld\n", ret);
    return 0;
}