JOI 2010-2011 本選
結果がきたので安心して参加記がかける
1番
2次元累積和やるだけ。10分
#include <cstdio> int m, n, q; int js[1001][1001]; int os[1001][1001]; int is[1001][1001]; int main() { char v[1005]; scanf("%d%d%d", &m, &n, &q); for(int i=0;i<=m;i++) for(int j=0;j<=n;j++) js[i][j] = os[i][j] = is[i][j] = 0; for(int i=1;i<=m;i++){ scanf("%s", v); for(int j=1;j<=n;j++){ if(v[j-1]=='J') js[i][j]++; if(v[j-1]=='O') os[i][j]++; if(v[j-1]=='I') is[i][j]++; } } for(int i=0;i<=m;i++){ for(int j=1;j<=n;j++){ js[i][j] += js[i][j-1]; os[i][j] += os[i][j-1]; is[i][j] += is[i][j-1]; } } for(int i=1;i<=m;i++){ for(int j=0;j<=n;j++){ js[i][j] += js[i-1][j]; os[i][j] += os[i-1][j]; is[i][j] += is[i-1][j]; } } int a, b, c, d; for(;q--;){ scanf("%d%d%d%d", &a, &b, &c, &d); a--; b--; printf("%d %d %d\n", js[c][d] - js[a][d] - js[c][b] + js[a][b], os[c][d] - os[a][d] - os[c][b] + os[a][b], is[c][d] - is[a][d] - is[c][b] + is[a][b]); } return 0; }
2番
ナップザックっぽいDPやるだけ。10分
#include <cstdio> #include <vector> #include <algorithm> using namespace std; vector<int> books[10]; vector<int> price[10]; int N, K; int dp[2][2000]; int main() { int c, g; scanf("%d%d", &N, &K); for(int i=0;i<N;i++){ scanf("%d%d", &c, &g); books[--g].push_back(c); } for(int i=0;i<10;i++){ sort(books[i].begin(), books[i].end()); reverse(books[i].begin(), books[i].end()); int sum = 0; price[i].push_back(0); for(int j=0;j<books[i].size();j++){ sum += books[i][j]; price[i].push_back(sum + j*(j+1)); } } int t = 0; for(int i=0;i<=K;i++){ dp[t][i] = dp[1-t][i] = 0; } for(int i=0;i<10;i++){ for(int j=0;j<=K;j++) dp[1-t][j] = 0; for(int j=0;j<price[i].size();j++){ //sell j books that series is i for(int k=j;k<=K;k++){ dp[1-t][k] = max(dp[1-t][k], dp[t][k-j]+price[i][j]); } } t = 1-t; } printf("%d\n", dp[t][K]); return 0; }
3番
Dijkstraやるだけ。10分
#include <cstdio> #include <vector> using namespace std; int N, M, K; int dist[3000]; vector<int> to[3000], len[3000]; bool visited[3000]; int main() { int a, b, l; scanf("%d%d%d", &N, &M, &K); for(int i=0;i<M;i++){ scanf("%d%d%d", &a, &b, &l); --a; --b; to[a].push_back(b); to[b].push_back(a); len[a].push_back(l); len[b].push_back(l); } for(int i=0;i<N;i++){ dist[i] = 1000000000; visited[i] = false; } for(;K--;){ scanf("%d", &a); dist[--a] = 0; } for(int i=0;i<N;i++){ int bp = -1; for(int j=0;j<N;j++){ if(!visited[j] && (bp==-1 || dist[bp] > dist[j])) bp = j; } visited[bp] = true; for(int j=0;j<to[bp].size();j++){ int t = to[bp][j], nl = dist[bp] + len[bp][j]; if(dist[t] > nl) dist[t] = nl; } } int ret = 0; for(int i=0;i<N;i++){ for(int j=0;j<to[i].size();j++) ret = max(ret, dist[i] + dist[to[i][j]] + len[i][j]); } printf("%d\n", (ret+1)/2); return 0; }
4番
1〜3と「比べると」急に難しくなる。
終点を固定した場合は、X方向、Y方向ごとに、「中央値から始めると最良だよの法則」を用いて、（終点以外の点を倍にして）最良値がわかる。
終点を動かしても、いろいろがんばると答えが出る。
このコードはO(N log N)の中でも頭悪いので、各終点について最良値をSegment Treeを使って求めてる
#include <cstdio> #include <algorithm> using namespace std; struct seg_tree { long long *data[25]; int size[25], len; seg_tree(int N) { len = 0; size[len++] = N; while(size[len-1] > 1){ size[len] = (size[len-1]+1)/2; len++; } for(int i=0;i<len;i++){ int l = (size[i]+1)/2*2; data[i] = new long long[l]; for(int j=0;j<l;j++) data[i][j] = 0; } } void add(int P, int V) { for(int i=0;i<len;i++){ data[i][P] += V; P >>= 1; } } void set(int P, int V) { data[0][P] = V; P >>= 1; for(int i=1;i<len;i++){ data[i][P] = data[i-1][P*2] + data[i-1][P*2+1]; P >>= 1; } } long long total(int left, int right) { long long ret = 0; for(int i=0;left!=right;i++){ if(left&1){ ret += data[i][left++]; } if(right&1){ ret += data[i][--right]; } left >>= 1; right >>= 1; } return ret; } int ith(long long v) { //find smallest x that total(0, x) >= v int ret = 0; for(int i=len-1;i>0;i--){ if(data[i-1][ret*2] < v){ v -= data[i-1][ret*2]; ret = (ret*2)+1; }else{ ret *= 2; } } return ret; } }; int N, X[100000], Y[100000]; int xs[100000], ys[100000]; int main() { scanf("%*d%*d%d", &N); for(int i=0;i<N;i++){ scanf("%d%d", X+i, Y+i); xs[i] = X[i]; ys[i] = Y[i]; } sort(xs, xs+N); sort(ys, ys+N); seg_tree sumX(2*N), sumY(2*N); for(int i=0;i<N;i++){ sumX.set(i*2, xs[i]); sumX.set(i*2+1, xs[i]); sumY.set(i*2, ys[i]); sumY.set(i*2+1, ys[i]); } long long ret = 1LL << 62LL; int bx=0, by=0; for(int i=0;i<N;i++){ long long tmp = 0; //prepare int xsp = lower_bound(xs, xs+N, X[i]) - xs; int ysp = lower_bound(ys, ys+N, Y[i]) - ys; //erase sumX.set(xsp*2, 0); sumY.set(ysp*2, 0); int mx = (xsp*2<N)?N:(N-1); int my = (ysp*2<N)?N:(N-1); tmp += (long long)xs[mx/2] * mx - sumX.total(0, mx); if(xsp*2 < mx) tmp -= xs[mx/2]; tmp += sumX.total(mx+1, 2*N) - (long long)xs[mx/2] * (2*N - mx - 1); if(xsp*2 > mx) tmp += xs[mx/2]; tmp += (long long)ys[my/2] * my - sumY.total(0, my); if(ysp*2 < my) tmp -= ys[my/2]; tmp += sumY.total(my+1, 2*N) - (long long)ys[my/2] * (2*N - my - 1); if(ysp*2 > my) tmp += ys[my/2]; //restore sumX.set(xsp*2, X[i]); sumY.set(ysp*2, Y[i]); //ret = min(ret, tmp); if(ret > tmp){ ret = tmp; bx = xs[mx/2]; by = ys[my/2]; } if(ret == tmp){ if(bx > xs[mx/2]){ bx = xs[mx/2]; by = ys[my/2]; }else if(bx == xs[mx/2] && by > ys[my/2]){ by = ys[my/2]; } } } printf("%lld\n%d %d\n", ret, bx, by); return 0; }
5番
二分探索×Segment Tree。これも１〜３に比べると難しいが似たような問題がIOI2009「Hiring」にあったような
二分探索で答えを固定し（例えばKとする）、許容量の大きいほうからK個をまず放出量setに追加し、上限を下げるときには下げたやつを使って放出量setを更新したり更新しなかったりする。setは実際にはSegment Treeを使って書いてる。
#include <cstdio> #include <algorithm> using namespace std; struct bug { int out, able; }; struct seg_tree { int *data[25], size[25], len; seg_tree(int N) { len = 0; size[len++] = N; while(size[len-1] > 1){ size[len] = (size[len-1]+1)/2; len++; } for(int i=0;i<len;i++){ int l = (size[i]+1)/2*2; data[i] = new int[l]; for(int j=0;j<l;j++) data[i][j] = 0; } } ~seg_tree() { for(int i=0;i<len;i++) delete [] data[i]; } void set(int p, int v) { data[0][p] = v; p >>= 1; for(int i=1;i<len;i++){ data[i][p] = max(data[i-1][p*2], data[i-1][p*2+1]); p >>= 1; } } int max_pos() { int ret = 0; for(int i=len-1;i>0;i--){ if(data[i][ret] == data[i-1][ret*2]) ret *= 2; else ret = ret*2+1; } return ret; } int get(int p) { return data[0][p]; } }; int N; bug bg[300000]; inline bool operator<(const bug& a, const bug& b) { return a.able > b.able; } bool test(int K) { seg_tree seg(K); //minimal K long long sum = 0; for(int i=0;i<K-1;i++){ seg.set(i, bg[i].out); sum += bg[i].out; } for(int i=K-1;i<N;i++){ if(i == K-1){ seg.set(K-1, bg[i].out); sum += bg[i].out; }else{ int mp = seg.max_pos(); if(seg.get(mp) > bg[i].out){ sum -= seg.get(mp); sum += bg[i].out; seg.set(mp, bg[i].out); } } if(sum <= (long long)K * bg[i].able) return true; } return false; } int main() { scanf("%d", &N); for(int i=0;i<N;i++) scanf("%d%d", &(bg[i].out), &(bg[i].able)); sort(bg, bg+N); int left=0, right=N; while(left < right){ if(right - left == 1){ if(!test(right)) right = left; break; } int mid = (left + right) / 2; if(test(mid)){ left = mid; }else{ right = mid; } } printf("%d\n", right); return 0; }
結果
3番でDijkstraをO(N^2+M)で書いたり、5番でO(N*(logN)^2)で解いたりしてTLEが怖かった。ほかにもバグが怖かった。
結果20+20+20+20+20=100で満点だったので満点詐欺は回避できました
