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