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;
}