JOI 2013-2014予選

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

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