今年の春合宿が鬼畜な件
毎日ダウンロードして問題眺めてるけど、多くの参加者が叫んでいるようにたしかに一完がめちゃくちゃ難しいセット
0170
添字ミスとかで時間かけてた
#include <cstdio> #include <climits> #include <iostream> #include <algorithm> #include <vector> #include <map> #define EPS 1e-9 using namespace std; string str; int w[10], s[10]; int main() { int n; while (scanf("%d",&n)) { if (n==0) break; string h[n]; int perm[n]; for (int i=0; i<n; i++) { cin>>str>>w[i]>>s[i]; h[i]=str; perm[i]=i; } double G=INT_MAX/2.0; string res[n]; do { int sum=w[perm[0]]; bool flag=true; for (int i=1; i<n; i++) { int x=perm[i]; if (s[x]<sum) { flag=false; break; } sum+=w[x]; } if (flag) { int sum2=0; for (int i=0; i<n; i++) sum2+=(n-i)*w[perm[i]]; if (G-EPS>(double)sum2/(double)sum) { G=(double)sum2/(double)sum; for (int i=0; i<n; i++) res[i]=h[perm[i]]; } } } while (next_permutation(perm, perm+n)); for (int i=n-1; i>=0; i--) cout<<res[i]<<endl; } }
0180
最小全域木やるだけ
#include <cstdio> #include <algorithm> using namespace std; struct unionfind { int par[100], rank[100]; unionfind(int n) { for (int i=0; i<n; i++) { par[i]=i; rank[i]=0; } } int find(int x) { if (par[x]==x) { return x; } else { return par[x]=find(par[x]); } } void unite(int x, int y) { x=find(x); y=find(y); if (x==y) return; if (rank[x]<rank[y]) { par[x]=y; } else { par[y]=x; if (rank[x]==rank[y]) rank[x]++; } } bool same(int x, int y) { return find(x)==find(y); } }; struct edge { int u, v, cost; edge(){} edge(int u, int v, int cost) : u(u), v(v), cost(cost) {} }; bool comp(const edge& e1, const edge& e2) { return e1.cost<e2.cost; } int main() { int n, m; while (scanf("%d%d",&n,&m)) { if (!n&&!m) break; unionfind uf(n); edge bridge[m]; for (int i=0; i<m; i++) { int a, b, cost; scanf("%d%d%d",&a,&b,&cost); bridge[i]=edge(a,b,cost); } sort(bridge,bridge+m,comp); int res=0; for (int i=0; i<m; i++) { edge e=bridge[i]; if (!uf.same(e.u,e.v)) { uf.unite(e.u,e.v); res+=e.cost; } } printf("%d\n",res); } }
0542
2008本選5
なかなか手応えあったけどやっぱり今年のとかと比べると楽な方
officeのセキュリティレベルをpriority_queueで行けるところをなめていきながらRまでのそれぞれの部屋数についてそれを達成できる最小の認証レベルを前計算して、それを最後に適度に足しながらやる
calcの最後の処理は正直いらなかったかもしれない
※追記:やっぱいらなかったので削除
#include <cstdio> #include <climits> #include <vector> #include <functional> #include <algorithm> #include <map> #include <queue> #define inf INT_MAX/2 using namespace std; typedef pair<int, int> P; typedef pair<int, P> PP; int dx[4]={0,0,-1,1}; int dy[4]={-1,1,0,0}; struct office { int minl[100001], w, h, is, js, maps[500][500]; bool used[500][500]; office () {} office (int w, int h, int is, int js) : w(w), h(h), is(is), js(js) { for (int i=0; i<h; i++) for (int j=0; j<w; j++) { used[i][j]=false; } } void calc(int r) { fill(minl, minl+(r+1), inf); if (maps[is][js]==0) return; minl[0]=0; draw(r); } bool isin(int x, int y) { return x>=0&&x<h&&y>=0&&y<w; } void draw(int r) { priority_queue<PP, vector<PP>, greater<PP> > que; que.push(make_pair(1,P(is,js))); int l=1, cnt=0; used[is][js]=true; while (!que.empty()) { PP p=que.top(); que.pop(); l=max(l, p.first); int x=p.second.first, y=p.second.second; cnt++; if (cnt>=r) minl[r]=min(minl[r], l); else minl[cnt]=min(minl[cnt], l); for (int i=0; i<4; i++) { int nx=x+dx[i], ny=y+dy[i]; if (isin(nx,ny)&&!used[nx][ny]) { que.push(make_pair(maps[nx][ny],P(nx,ny))); used[nx][ny]=true; } } } } }; int main() { int r; while (scanf("%d",&r)) { if (!r) break; office o1, o2; int w, h, x, y; scanf("%d%d%d%d",&w,&h,&x,&y); o1=office(w,h,y-1,x-1); for (int i=0; i<h; i++) for (int j=0; j<w; j++) { scanf("%d",&o1.maps[i][j]); } scanf("%d%d%d%d",&w,&h,&x,&y); o2=office(w,h,y-1,x-1); for (int i=0; i<h; i++) for (int j=0; j<w; j++) { scanf("%d",&o2.maps[i][j]); } o1.calc(r); o2.calc(r); int res=inf; for (int i=r; i>=0; i--) { res=min(res, o1.minl[i]+o2.minl[r-i]); } printf("%d\n",res); } }