2014-02-16

USACO 2014 January Contest, Gold

USACO

今月と見せかけて先月の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;
}

2013-12-15

JOI 2013-2014予選

JOI

予選敗退したのでソースだけ貼っておきます.

1. 読む

int ret;

int main(){
    rep(i, 5){
	int t;
	cin >> t;
	ret += max(t, 40);
    }
    cout << ret / 5 << endl;
    return 0;
}

2. 制約緩いし普通に上から見ればいいです

int n, m;
int piv, now;
int v[1010];
int c[1010];

int main(){
    cin >> n >> m;
    rep(i, n) cin >> c[i];
    rep(i, m){
	int b; 
	cin >> b;
	rep(j, n){
	    if(c[j] <= b){
		++v[j];
		break;
	    }
	}
    }
    rep(i, n){
	if(v[i] > now){
	    now = v[i];
	    piv = i + 1;
	}
    }
    cout << piv << endl;
    return 0;
}

3. 場合分け

int calc(P a, P b){
    if(a > b) swap(a, b);
    if(a.se <= b.se){
	int t = min(b.se - a.se, b.fi - a.fi);
	a.fi += t; a.se += t;
	return (t + b.se - a.se + b.fi - a.fi);
    }else{
	return (b.fi - a.fi + a.se - b.se);
    }

}

int main(){
    cin >> w >> h >> n;
    cin >> x >> y;
    rep(i, n - 1){
	int a, b;
	cin >> a >> b;
	ret += calc(mp(x, y), mp(a, b));
	x = a; y = b;
    }
    cout << ret << endl;
    return 0;
}

4. dp[i][j] : i日目, 出席している人の集合が2進数表示でj　でやる

const int MOD = 10007;

int n, ret;
string sa;
int s[1010];
int dp[1010][8];

int main(){
    cin >> n >> sa;
    rep(i, n){
	if(sa[i] == 'J') s[i] = 0;
	else if(sa[i] == 'O') s[i] = 1;
	else s[i] = 2;
    }

    for(int i = 1; i < 8; ++i) if((i & 1) && (i & (1 << s[0]))) dp[0][i] = 1;
    
    for(int i = 1; i < n; ++i){
	for(int j = 1; j < 8; ++j){
	    if(!(j & (1 << s[i]))) continue;
	    for(int k = 1; k < 8; ++k){
		int mask = (j & k);
		if(mask) dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD;
	    }
	}
    }

    rep(i, 8) ret = (ret + dp[n-1][i]) % MOD;
    cout << ret << endl;
    return 0;
}

5. 予選でグラフが出て驚く.

int n, k;
P ta[5010];
vector<int> g[5010];
int d[5010][5010];
int dd[5010];

struct edge{
    int to, co;
    edge(int to, int co) : to(to), co(co){}
    edge(){}
};

vector<edge> ng[5010];

void get_dist(){
    rep(i, n){
	rep(j, n) d[i][j] = INT_MAX;
	d[i][i] = 0;
	queue<int> q;
	q.push(i);
	
	while(!q.empty()){
	    int v = q.front(); q.pop();
	    rep(j, g[v].size()){
		if(d[i][g[v][j]] != INT_MAX) continue;
		d[i][g[v][j]] = d[i][v] + 1;
		q.push(g[v][j]);
	    }
	}
    }
}

void build_graph(){
    rep(i, n){
	rep(j, n){
	    if(i == j) continue;
	    if(d[i][j] <= ta[i].se) ng[i].pb(edge(j, ta[i].fi));
	}
    }
}

void dijk(){
    fill(dd, dd + n, INT_MAX);
    dd[0] = 0;
    priority_queue<P, vector<P>, greater<P> > q;
    q.push(mp(0, 0));

    while(!q.empty()){
	P p = q.top(); q.pop();
	int v = p.se;
	if(dd[v] < p.fi) continue;
	rep(i, ng[v].size()){
	    edge e = ng[v][i];
	    if(dd[e.to] > dd[v] + e.co){
		dd[e.to] = dd[v] + e.co;
		q.push(mp(dd[e.to], e.to));
	    }
	}
    }

}

int main(){
    scanf("%d %d", &n, &k);
    rep(i, n) scanf("%d %d", &ta[i].fi, &ta[i].se);
    rep(i, k){
	int a, b;
	scanf("%d %d", &a, &b);
	--a; --b;
	g[a].pb(b); g[b].pb(a);
    }

    get_dist();
    build_graph();
    dijk();

    printf("%d\n", dd[n-1]);
    return 0;
}

6. opened

2013-12-13

JOI 模擬予選

JOI

期末とはなんだったのか.
500/600点でした. 6の部分点取りに行かなかったのは良くない....

1. 平均*5 - 残り.

int s, a;

int main(){
    rep(i, 4){
	int t;
	scanf("%d", &t);
	s += t;
    }
    scanf("%d", &a);
    printf("%d\n", a * 5 - s);
    return 0;
}

2. 素直に計算してsort.

int n, m;
int ex[110];
P a[110];

int calc(int i){
    int now = 1, r = ex[i];
    while(r){
	if(r < 100 * now) break;
	r -= 100 * now++;
    }
    return now;
}

int main(){
    scanf("%d %d", &n, &m);
    while(m--){
	int p, q;
	scanf("%d %d", &p, &q);
	ex[p-1] += q;
    }
    rep(i, n) a[i] = mp(-calc(i), i + 1);
    sort(a, a + n);
    rep(i, n) printf("%d\n", a[i].se);
    return 0;
}

3. 特別な仕事をどこまでするかを試す.

int n;
ll c, s, t;
ll ret = LLONG_MAX;
pair<ll, ll> wo[110];

ll calc(int idx){
    ll nc = c, ns = s, mo = 0;
    rep(i, idx){
	if(ns >= wo[i].fi){
	    ns -= wo[i].fi;
	    nc += wo[i].se;
	}else{
	    ll nes = wo[i].fi - ns;
	    ll d = (nes + nc - 1) / nc;
	    mo += d;
	    ns += d * nc;
	    ns -= wo[i].fi;
	    nc += wo[i].se;
	}
    }
    if(ns >= t) return mo;
    ll d = (t - ns + nc - 1) / nc;
    mo += d;
    return mo;
}

int main(){
    scanf("%lld %lld %lld %d", &c, &s, &t, &n);
    rep(i, n) scanf("%lld %lld", &wo[i].fi, &wo[i].se);
    for(int i = 0; i <= n; ++i) ret = min(ret, calc(i));
    printf("%lld\n", ret);
    return 0;
}

4. dp[i][j][k] : 場所, 最後から2番目, 最後(最後から2番目は別に同じかどうかだけで良いが)

int n, m, l;
const ll MOD = 100000LL;
bool ban[110][110];
vector<int> v[110];
ll dp[110][110][110];
ll ret;

int main(){
    scanf("%d %d %d", &n, &m, &l);
    rep(i, l){
	int a, b;
	scanf("%d %d", &a, &b);
	ban[a-1][b-1] = true;
    }
    rep(i, n){
	rep(j, m){
	    if(!ban[i][j]) v[i].pb(j);
	}
    }
    rep(i, v[0].size()){
	rep(j, v[1].size()){
	    if(v[0][i] == v[1][j]) dp[1][v[0][i]][v[0][i]] = 1;
	}
    }

    for(int i = 1; i < n; ++i){
	rep(j, v[i-1].size()){
	    int p = v[i-1][j];
	    rep(k, v[i].size()){
		int q = v[i][k];
		if(p == q) rep(id, v[i+1].size()) dp[i+1][q][v[i+1][id]] = (dp[i+1][q][v[i+1][id]] + dp[i][p][q]) % MOD;
		else if(!ban[i+1][q]) dp[i+1][q][q] = (dp[i+1][q][q] + dp[i][p][q]) % MOD;
	    }
	}
    }

    rep(i, v[n-2].size()){
	rep(j, v[n-1].size()){
	    if(v[n-2][i] == v[n-1][j]) ret = (ret + dp[n-1][v[n-2][i]][v[n-1][j]]) % MOD;
	}
    }
    printf("%lld\n", ret);
    return 0;
}

5. コンビネーションを適当にやってもできるが, 予選形式なのでサボった

int n, s, t;
const ll MOD = 1000000007LL;

int main(){
    scanf("%d %d %d", &n, &s, &t);
    if(abs(s - t) >= n){
	puts("0");
	return 0;
    }
    if(n == 1){
	if(s == t) puts("1");
	else puts("0");
	return 0;
    }
    t = abs(t - s);
    s = 0;
    vector<ll> v;
    v.pb(1LL);

    rep(i, n - 1){
	vector<ll> nv((int)v.size() + 2);
	rep(j, v.size()){
	    nv[j] = (nv[j] + v[j]) % MOD;
	    nv[j+1] = (nv[j+1] + v[j]) % MOD;
	    nv[j+2] = (nv[j+2] + v[j]) % MOD;	    
	}
	v = nv;
    }
    printf("%lld\n", v[n - 1 - t]);
    return 0;
}

2013-11-24

USACO 2013 November Contest

USACO

BronzeとSilverを解きました.

まずBronze

Combination Lock

全部調べるだけ

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <climits>
using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define fi first
#define se second

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,1,-1};

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

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

int a, b, c, d, e, f, n;
set<pair<P, int> > s;

int modify(int x){
    while(x <= 0) x += n;
    while(x > n) x -= n;
    return x;
}

int main(){
    freopen("combo.in", "r", stdin);
    freopen("combo.out", "w", stdout);
    scanf("%d", &n);
    scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f);

    for(int i = a - 2; i <= a + 2; ++i){
	for(int j = b - 2; j <= b + 2; ++j){
	    for(int k = c - 2; k <= c + 2; ++k){
		int p, q, r;
		p = i;
		q = j;
		r = k;
		i = modify(i);
		j = modify(j);
		k = modify(k);
		s.insert(mp(mp(i, j), k));
		i = p;
		j = q;
		k = r;
	    }
	}
    }

    for(int i = d - 2; i <= d + 2; ++i){
	for(int j = e - 2; j <= e + 2; ++j){
	    for(int k = f - 2; k <= f + 2; ++k){
		int p, q, r;
		p = i;
		q = j;
		r = k;	
		i = modify(i);
		j = modify(j);
		k = modify(k);
		s.insert(mp(mp(i, j), k));
		i = p;
		j = q;
		k = r;		
	    }
	}
    }

    printf("%d\n", (int)s.size());
    return 0;
}

Goldilocks and the N Cows
座標圧縮+imos法.

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <climits>
using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define fi first
#define se second

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,1,-1};

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

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

int n;
ll x, y, z;
int r[100010];
vector<int> v;
P cow[20010];
map<int, int> m;
int ma;

int main(){
    freopen("milktemp.in", "r", stdin);
    freopen("milktemp.out", "w", stdout);
    
    scanf("%d", &n);
    scanf("%lld %lld %lld", &x, &y, &z);
    v.pb(0); v.pb(1000000000);

    rep(i, n){
	scanf("%d %d", &cow[i].fi, &cow[i].se);
	v.pb(cow[i].fi);
	v.pb(cow[i].se);
    }

    sort(v.begin(), v.end());
    rep(i, v.size()) m[v[i]] = i;
    rep(i, n){
	cow[i].fi = m[cow[i].fi];
	cow[i].se = m[cow[i].se];
    }

    rep(i, n){
	r[0] += x;
	r[cow[i].fi] += (y - x);
	r[cow[i].se + 1] += (z - y);
    }

    rep(i, 100000) r[i+1] += r[i];

    rep(i, 100000) ma = max(ma, r[i]);
    printf("%d\n", ma);
    return 0;
}

これはsilverとの共通問題
再帰して数えると終わる

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <climits>
using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define fi first
#define se second

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,1,-1};

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

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

int n, zan, va;
vector<string> a[50];
vector<vector<string> > lackk;
vector<vector<int> > la;
map<string, int> m[50];
int siz[50];

int main(){
    freopen("nocow.in", "r", stdin);
    freopen("nocow.out", "w", stdout);
    cin >> n >> zan;
    cin.ignore();
    rep(i, n){
	string s;
	getline(cin, s);
	s = s.substr(19);
	s = s.substr(0, s.size() - 5);
	//cout << s << endl;

	int now = 0;
	string t = "";
	vector<string> info;
	rep(j, s.size()){
	    if(s[j] != ' ') t.pb(s[j]);
	    else{
		a[now++].pb(t);
		info.pb(t);
		t = "";
	    }
	}
	a[now++].pb(t);
	info.pb(t);
	va = now;
	lackk.pb(info);
    }

    rep(i, va){
	sort(a[i].begin(), a[i].end());
	a[i].erase(unique(a[i].begin(), a[i].end()), a[i].end());
	rep(j, a[i].size()) m[i][a[i][j]] = j;
    }

    sort(lackk.begin(), lackk.end());
    rep(i, n){
	vector<int> info;
	rep(j, lackk[i].size()) info.pb(m[j][lackk[i][j]]);
	la.pb(info);
    }

    /*
    rep(i, n){
	rep(j, va) cout << la[i][j] << " ";
	cout << endl;
    }*/

    siz[va] = 1;
    for(int i = va - 1; i >= 0; --i) siz[i] = siz[i + 1] * (int)a[i].size();

    vector<int> sel;

    rep(i, va){
	int sum = 0;

	rep(j, a[i].size()){
	    int ad = siz[i + 1];
	    rep(k, n){
		bool f = true;
		rep(l, i) if(la[k][l] != sel[l]) f = false;
		if(la[k][i] != j) f = false;
		ad -= f;
	    }
	    if(sum + ad >= zan){
		zan -= sum;
		sel.pb(j);
		break;
	    }else sum += ad;
	}

	//cout << sel[i] << endl;
    }

    rep(i, va){
	cout << a[i][sel[i]] << flush;
	if(i == va - 1) cout << endl;
	else cout << " ";
    }
    return 0;
}

/*
3 5
Farmer John has no large brown noisy cow.
Farmer John has no small white silent cow.
Farmer John has no large spotted noisy cow.
*/

次にsilver
Crowded Cows
segment treeを使ってRMQ

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <climits>
using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define fi first
#define se second

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

int n, d, ret;
int sz = 1;
const int SZ = 1 << 19;
vector<P> cow;

struct segtree{
    int dat[SZ * 2];
    void init(){
	CLR(dat); 
	while(sz < n) sz *= 2;
    }
    
    void upd(int pos, int x){
	pos += sz - 1;
	dat[pos] = x;
	while(pos > 0){
	    pos = (pos - 1) / 2;
	    dat[pos] = max(dat[pos*2+1], dat[pos*2+2]);
	}
    }

    int ask(int a, int b, int k = 0, int l = 0, int r = sz){
	if(r <= a || b <= l) return 0;
	if(a <= l && r <= b) return dat[k];
	return max(ask(a, b, k * 2 + 1, l, (l + r) / 2), ask(a, b, k * 2 + 2, (l + r) / 2, r));
    }
}seg;

int main(){
    freopen("crowded.in", "r", stdin);
    freopen("crowded.out", "w", stdout);
    scanf("%d %d", &n, &d);
    seg.init();
    rep(i, n){
	int x, h;
	scanf("%d %d", &x, &h);
	cow.pb(mp(x, h));
    }
    sort(cow.begin(), cow.end());
    rep(i, n) seg.upd(i, cow[i].se);

    rep(i, n){
	int x = cow[i].fi;
	int lb, rb, ma1, ma2;
	lb = lower_bound(cow.begin(), cow.end(), mp(x - d, 0)) - cow.begin();
	rb = lower_bound(cow.begin(), cow.end(), mp(x + d, INT_MAX)) - cow.begin();
	ma1 = seg.ask(lb, i);
	ma2 = seg.ask(i + 1, rb);
	if(ma1 >= cow[i].se * 2 && ma2 >= cow[i].se * 2) ++ret;
    }

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

Pogo-Cow
dp[i][j] :-> 最後にi番目, その前にj番目を使った時の最大値としてdp,
連続した範囲をしらべるのでうまくmaxを持つとO(N^2)で解けるが, O(N^3)でも枝を刈ると通る.

//include
//------------------------------------------
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

#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)

typedef pair<int, int> P;

int n, ret;
int dpL[1010][1010], dpR[1010][1010]; //(now, prev) -> max
int a[1010];
P tar[1010];

int main(){
    freopen("pogocow.in", "r", stdin);
    freopen("pogocow.out", "w", stdout);    
    scanf("%d", &n);
    rep(i, n) scanf("%d %d", &tar[i].fi, &tar[i].se);
    sort(tar, tar + n);

    rep(i, n) dpL[i][i] = tar[i].se;

    rep(i, n){
	rep(j, i){
	    for(int k = j; k >= 0; --k){
		if(tar[i].fi - tar[j].fi >= tar[j].fi - tar[k].fi) dpL[i][j] = max(dpL[i][j], dpL[j][k]);
		else break;
	    }
	    dpL[i][j] += tar[i].se;
	}
    }

    sort(tar, tar + n, greater<P>());
    rep(i, n) dpR[i][i] = tar[i].se;
 
    rep(i, n){
	rep(j, i){
	    for(int k = j; k >= 0; --k){
		if(tar[j].fi - tar[i].fi >= tar[k].fi - tar[j].fi) dpR[i][j] = max(dpR[i][j], dpR[j][k]);
		else break;
	    }
	    dpR[i][j] += tar[i].se;
	}
    }

    rep(i, n) rep(j, i+1){
	ret = max(ret, dpL[i][j]);
	ret = max(ret, dpR[i][j]);
    }
    printf("%d\n", ret);
    return 0;
}

2013-10-07

SRM593 Div1

Topcoder

easyだけ通った

easy : 絵を書くと、N * N全てを塗る場合でも3色で済むことがわかるので、二部グラフ判定するだけ. 六角座標はクソ(確信)

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

class HexagonalBoard{
    public:
	int n;
	vector<string> v;
	int st[60][60];

	bool dfs(int y, int x, int c){
	    st[y][x] = c;
	    rep(i, 6){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(!(ny >= 0 && ny < n && nx >= 0 && nx < n && v[ny][nx] == 'X')) continue;

		if(st[ny][nx] == c) return false;
		if(st[ny][nx] == 0 && !dfs(ny, nx, -c)) return false;
	    }

	    return true;
	}

	bool ch(){
	    bool ok = true;
	    rep(i, n){
		rep(j, n){
		    if(v[i][j] == '-') continue;
		    if(st[i][j] == 0){
			if(!dfs(i, j, 1)) ok = false;
		    }
		}
	    }
	    return ok;
	}

	int minColors(vector <string> b){
	    n = b.size();
	    v = b;
	    bool a1 = false, a2 = false;

	    memset(st, 0, sizeof(st));
	    rep(i, n){
		rep(j, n){
		    if(b[i][j] == '-') continue;
		    a1 = true;
		    rep(k, 6){
			int ny = i + dy[k];
			int nx = j + dx[k];
			if(ny >= 0 && ny < n && nx >= 0 && nx < n && b[ny][nx] == 'X') a2 = true;
		    }
		}
	    }
	    if(a1 == false) return 0;
	    if(a2 == false) return 1;
	    if(ch()) return 2;
	    return 3;
	}
};

Med :
まず、Sに含まれる方が最速で走り, Tに含まれる方が最遅で走る時またはその逆の時の、差の絶対値の大きい方がmaxdiff(S, T)となることがわかる。
次に式変形をすると
sum(B of S) - sum(A of T) = sum(B of all) - sum(A + B of T)
sum(A of S) - sum(B of T) = sum(A of all) - sum(A + B of T)
がわかるので、
部分集合で作りうるA + Bの和をdpで計算して調べるだけ。

class MayTheBestPetWin{
    public:
	int n;
	int sa, sb;
	int a[60], b[60], s[60];
	bool dp[1010010];

	int calc(vector <int> A, vector <int> B){
	    n = A.size();
	    sa = 0; sb = 0;
	    int ret = INT_MAX;
	    memset(dp, false, sizeof(dp));
	    dp[0] = true;

	    rep(i, n){
		a[i] = A[i]; b[i] = B[i];
		sa += a[i]; sb += b[i];
		s[i] = a[i] + b[i];
		for(int j = sa + sb; j >= 0; --j) if(dp[j]) dp[j + s[i]] = true;
	    }

	    for(int i = 0; i <= sa + sb; ++i) if(dp[i]) ret = min(ret, max(abs(sb - i), abs(sa - i)));

	    return ret;
	}
};

2013-09-12

JOI春合宿倉庫番(Sokoban)

JOI

グリッドグラフだ〜〜〜という気持ちになって頑張る.
コードだけ上げておきます O(MN)

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

using namespace std;

typedef long long ll;

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

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

int n, m, sx, sy, zen;
ll ret;
int deg[1000010];
int dt[1000010];
int g[1000010][4];
int tr[1000010][4];
char ban[1010][1010];
bool can[1010][1010];
bool vis[1000010];
bool inv[1010][1010][4];
int ord[1000010], out[1000010], low[1000010];
int sz[1000010];
int par[1000010];
int now;
bool adj[1000010][4][4];

inline void pre(int y, int x){
    can[y][x] = true;
    rep(i, 4){
	int ny = y + dy[i];
	int nx = x + dx[i];
	if(ny >= 0 && ny < m && nx >= 0 && nx < n && ban[ny][nx] != '#' && !can[ny][nx]) pre(ny, nx);
    }
}

void pro(int v, int p){
    low[v] = ord[v] = now++;
    sz[v] = 1;
    par[v] = p;
    vis[v] = true;
    rep(i, deg[v]) if(g[v][i] != p){
	if(!vis[g[v][i]]){
	    tr[v][dt[v]++] = g[v][i];
	    pro(g[v][i], v);
	    sz[v] += sz[g[v][i]];
	    low[v] = min(low[v], low[g[v][i]]);
	}else{
	    low[v] = min(low[v], ord[g[v][i]]);
	}
    }
    out[v] = now++;
}

inline bool dec(int p, int q){ // p : ancestor of q
    return ord[p] <= ord[q] && out[q] <= out[p];
}

void set(int v){ //remove v
    int ap[4] = {-1};
    rep(i, deg[v]){
	int a = g[v][i];	
	if(dec(v, a)){
	    rep(j, dt[v]){
		if(dec(tr[v][j], a)){
		    ap[i] = tr[v][j];
		    break;
		}
	    }
	}
    }

    rep(i, deg[v]){
	int a = g[v][i];
	rep(j, deg[v]) if(i != j){
	    int b = g[v][j];
	    if(!(dec(v, a) || dec(v, b))) adj[v][i][j] = adj[v][j][i] = true;
	    else if(dec(v, a) && !dec(v, b)){
		adj[v][i][j] = adj[v][j][i] = (low[ap[i]] < ord[v]);
	    }else if(dec(v, a) && dec(v, b)){
		if(ap[i] == ap[j] || (low[ap[i]] < ord[v] && low[ap[j]] < ord[v])){
		    adj[v][i][j] = adj[v][j][i] = true;
		}
	    }
	}
    }
}

void calc(int y, int x, int dir){
    if(inv[y][x][dir]) return ;
    //printf("y : %d, x : %d, dir : %d\n", y, x, dir);
    inv[y][x][dir] = true;
    int v = y * n + x;
    if(!can[y][x]) set(v);
    can[y][x] = true;
    int px = x + dx[dir], py = y + dy[dir];
    int nv = py * n + px;
    int whi = -1;
    rep(i, deg[v]){
	if(g[v][i] == nv){
	    whi = i;
	    break;
	}
    }

    int kou[4];
    int piv = 0;
    //printf("whi : %d\n", whi);
    ll mi = 0;
    bool f = false;
    //printf("y : %d, x : %d, py : %d, px : %d\n", y, x, py, px);
    rep(i, deg[v]) {
	if((i == whi) || adj[v][whi][i]){
	    int dev = g[v][i];
	    if(dec(g[v][i], v)) f = true;
	    //printf("(%d %d) ", dev / n, dev % n);
	    kou[piv++] = g[v][i];
	}
    }
    //puts("");

    ll tmp = 0;
    if(par[v] != -1){
	rep(i, piv){
	    if(par[v] == kou[i]){
		tmp += zen - sz[v] - 1;
	    }
	}
    }

    rep(i, dt[v]){
	rep(j, piv){
	    if(tr[v][i] == kou[j]) tmp += sz[tr[v][i]];
	}
    }
    
    if(y != sy || x != sx) ret += tmp;
    //printf("y : %d, x : %d, dir : %d, add : %lld\n", y, x, dir, tmp);

    int d[4] = {-1};

    rep(i, piv){
	int ny = kou[i] / n, nx = kou[i] % n;
	int ndir = -1;
	int dify = ny - y, difx = nx - x;
	if(difx == 1 && dify == 0) ndir = 0;
	else if(difx == -1 && dify == 0) ndir = 1;
	else if(difx == 0 && dify == 1) ndir = 2;
	else ndir = 3;
	inv[y][x][ndir] = true;
	d[i] = ndir;
    }

    rep(i, piv){
	int ny = kou[i] / n, nx = kou[i] % n;
	py = ny + dy[d[i]];
	px = nx + dx[d[i]];
	if(px < 0 || py < 0 || px >= n || py >= m || ban[py][px] == '#') continue;
	//printf("(py, px) : (%d, %d), (ny, nx) : (%d, %d), ndir : %d\n", py, px, ny, nx, ndir);
	calc(ny, nx, d[i]);
    }
}

int main(){
    scanf("%d %d", &m, &n);
    rep(i, m){
	scanf("%s", ban[i]);
	rep(j, n) if(ban[i][j] == 'X'){
	    sy = i;
	    sx = j;
	    ban[i][j] = '.';
	}
    }
    pre(sy, sx);
    rep(i, m) rep(j, n) if(!can[i][j]) ban[i][j] = '#';
    memset(can, 0, sizeof(can));
    rep(i, m) rep(j, n){
	int y = i, x = j, v = i * n + j;
	if(ban[i][j] == '#') continue;
	rep(k, 4){
	    int ny = y + dy[k], nx = x + dx[k], nv = ny * n + nx;
	    if(ny >= 0 && ny < m && nx >= 0 && nx < n && ban[ny][nx] != '#'){
		g[v][deg[v]++] = nv;
	    }
	}
    }
    pro(n * sy + sx, -1);
    zen = sz[n * sy + sx];
    rep(i, 4){
	int nx = sx + dx[i], ny = sy + dy[i];
	if(nx < 0 || ny < 0 || nx >= n || ny >= m || ban[ny][nx] == '#') continue;
	int px = nx + dx[i], py = ny + dy[i];
	if(px < 0 || py < 0 || px >= n || py >= m || ban[py][px] == '#') continue;
	calc(ny, nx, i);
    }
    printf("%lld\n", ret);
    return 0;
}

2013-09-08

PKU 3177 Redundant Paths

PKU

無向グラフが与えられて辺を追加して、各点間に二通りの経路ができるようにする時(その経路は同じ辺を使わってはいけない)　追加する辺の個数を最小化

二重連結であれば2通り経路があるのでlowlinkを用いて適当に現在のグラフの二重連結成分を頂点にしたグラフを考えた時の(葉の個数+1)/2が答え

入力に同じ辺が2回含まれてるケースがあったらしく訴訟

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <climits>
using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define fi first
#define se second

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,1,-1};

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

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

int f, r, ret;
vector<int> g[5010];
int now;
int low[5010], ord[5010];
bool vis[5010];
P e[10010];
int deg[5010];
bool use[5010][5010];

void dfs(int v){
    vis[v] = true;
    ord[v] = low[v] = now++;

    rep(i, g[v].size()){
	if(!vis[g[v][i]]){
	    use[v][g[v][i]] = true;
	    dfs(g[v][i]);
	    low[v] = min(low[v], low[g[v][i]]);
	}
	else if(!use[g[v][i]][v]) low[v] = min(low[v], ord[g[v][i]]);
    }
}

int main(){
    scanf("%d %d", &f, &r);
    rep(i, r){
	int a, b;
	scanf("%d %d", &a, &b);
	--a; --b;
	if(use[a][b]) continue;
	use[a][b] = use[b][a] = true;
	g[a].pb(b);
	g[b].pb(a);
	e[i] = mp(a, b);
    }
    memset(use, 0, sizeof(use));
    dfs(0);
    rep(i, r){
	if(low[e[i].fi] != low[e[i].se]){
	    deg[low[e[i].fi]]++;
	    deg[low[e[i].se]]++;
	}
    }
    rep(i, f) ret += (deg[i] == 1);
    //rep(i, f) printf("%d %d\n", low[i], ord[i]);
    printf("%d\n", (ret + 1) / 2);
    return 0;
}