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

2013-09-02

USACO 2012 December Contest Gold, Running Away From the Barn

USACO

N頂点の木が与えられるので各点について、距離がL以下かつ部分木に含まれる点の個数を出力せよ
(N <= 200000)

各点について距離L以内でどこまで上に上がれるかわかれば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;

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

//container util
//------------------------------------------
#define pb push_back
#define mp make_pair
#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++)

int n;
ll l;
ll d[200010];
vector<P> g[200010];
int par[200010][19];
int r[200010];

inline void build(int v, ll dep, int p){
    par[v][0] = p;
    d[v] = dep;
    rep(i, g[v].size()) build(g[v][i].fi, dep + g[v][i].se, v);
}

int main(){
    freopen("runaway.in", "r", stdin);
    freopen("runaway.out", "w", stdout);
    scanf("%d %lld", &n, &l);
    par[0][0] = -1;
    rep(i, n - 1){
	int p; ll len;
	scanf("%d %lld", &p, &len);
	--p;
	g[p].pb(mp(i + 1, len));
    }
    build(0, 0, -1);

    rep(i, 18){
	rep(j, n){
	    if(par[j][i] < 0) par[j][i + 1] = -1;
	    else par[j][i + 1] = par[par[j][i]][i];
	}
    }

    rep(i, n){
	int v = i;
	ll cur = 0;
	++r[v];

	for(int j = 18; j >= 0; --j){
	    if(par[v][j] == -1) continue;
	    if(cur + d[v] - d[par[v][j]] <= l){
		cur += d[v] - d[par[v][j]];
		v = par[v][j];
	    }
	}
	if(par[v][0] != -1) --r[par[v][0]];
    }
    for(int i = n - 1; i >= 0; --i) if(par[i][0] != -1) r[par[i][0]] += r[i];
    rep(i, n) printf("%d\n", r[i]);
    return 0;
}