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