JAG 2011 Day3
感想：すっごい楽しかったです
大体自分のレベル〜それより上ぐらいの問題でやるだけ感もなく楽しめました
英語問題でしたがいつもより英語の不快感が無かった気がします。 Japanese English???
A
N,Mが小さいので全パターン試します
int main(){ int n,m;scanf("%d%d",&n,&m); vector<pair<double,pair<double,double> > >col(n); REP(i,n) scanf("%lf%lf%lf",&col[i].fr,&col[i].sc.fr,&col[i].sc.sc); double res=0; vi c; REP(i,(1<<n)){ int cnt=0; c.clear(); REP(j,n) if(i>>j&1) { c.pb(j); } if(SZ(c)!=m) continue; double sum=0; REP(j,m) REP(k,j){ sum+=SPR(col[c[j]].fr-col[c[k]].fr)+SPR(col[c[j]].sc.fr-col[c[k]].sc.fr)+SPR(col[c[j]].sc.sc- col[c[k]].sc.sc); } res=max(res,sum); } printf("%.6f\n",res); return 0; }
B
全探索調にやりますが、T-EかT+Eの境界を跨いでいないものは確定してもOK
double p,e,t; int maxk; double dfs(int k,double l,double r){ if(t+e>=r && t-e<=l) return 1.0; if(t+e<l || t-e>r) return 0.0; double md=(l+r)/2; if(k==maxk){ if(md>=t-e && md<=t+e) return 1.0; return 0.0; } double pl=dfs(k+1,l,md),pr=dfs(k+1,md,r); if(md>=t){ return pl*(1.0-p)+pr*p; }else return pl*p+pr*(1.0-p); } int main(){ int k,r,l;scanf("%d%d%d",&k,&r,&l); maxk=k; swap(r,l); scanf("%lf%lf%lf",&p,&e,&t); printf("%.6f\n",dfs(0,l,r)); return 0; }
C
かなりじっそうがむずかしい
道が一意に定まるので、すべての点からすべての点へまずbfsして経路の長さを求める。
次に仕事部屋を順に探っていって、経路を保存
まず部屋を出る度に消すパターンで計算して、
部屋を二回目に通るときは、最初に消さなかった方がよかったかどうか比べて、小さい方になおす
int main(){ int r,c,m;scanf("%d%d%d",&r,&c,&m); vvi g(r,vi(c)),per=g,on=g,off=g; REP(i,r) REP(j,c){ char c;scanf("\n%c",&c); if(c=='#') g[i][j]=1; } REP(i,r) REP(j,c){ scanf("%d",&per[i][j]); } REP(i,r) REP(j,c) scanf("%d",&on[i][j]); REP(i,r) REP(j,c) scanf("%d",&off[i][j]); vector<vector<vvi> >cost(r,vector<vvi>(c,vvi(r,vi(c,INF)))); REP(i,r) REP(j,c){ cost[i][j][i][j]=0; queue<pi>q;q.push(mp(i,j)); while(!q.empty()){ pi cur=q.front();q.pop(); REP(k,4){ int px=cur.sc+dx[k],py=cur.fr+dy[k]; if(px<0|| py<0 || px>=c || py>=r || g[py][px] || cost[py][px][i][j]!=INF) continue; cost[py][px][i][j]=cost[cur.fr][cur.sc][i][j]+1; q.push(mp(py,px)); } } } vp path; vp point(m); REP(i,m){ scanf("%d%d",&point[i].fr,&point[i].sc); } path.pb(point[0]); REP(i,m-1){ pi p=point[i]; while(p!=point[i+1]){ REP(j,4){ int px=p.sc+dx[j],py=p.fr+dy[j]; if(px<0 || py<0 || px>=c || py>=r) continue; if(cost[py][px][point[i+1].fr][point[i+1].sc]+1== cost[p.fr][p.sc][point[i+1].fr][point[i+1].sc]){ p=mp(py,px); break; } } path.pb(p); } } int res=0; REP(i,SZ(path)){ res+=on[path[i].fr][path[i].sc]+off[path[i].fr][path[i].sc]; } vvi befvis(r,vi(c,-1)); REP(i,SZ(path)){ if(befvis[path[i].fr][path[i].sc]==-1){ befvis[path[i].fr][path[i].sc]=i;continue; } int time=i-befvis[path[i].fr][path[i].sc]; if(time*per[path[i].fr][path[i].sc]<on[path[i].fr][path[i].sc]+off[path[i].fr][path[i].sc]){ res-=on[path[i].fr][path[i].sc]+off[path[i].fr][path[i].sc]; res+=time*per[path[i].fr][path[i].sc]; } befvis[path[i].fr][path[i].sc]=i; } printf("%d\n",res); return 0; }
D
まず最初にどの人が何回休む確率がどれだけかを計算。
累積も求める。
あとはそれぞれの人のそれぞれ何回休むかごとに、誰がどのぐらい以上安めばよいかを計算する。
コーナーケースがやや面倒。
int main(){ int n,m,l;scanf("%d%d%d",&n,&m,&l); vector<pair<int,pi> >p(n); REP(i,n) scanf("%d%d%d",&p[i].fr,&p[i].sc.fr,&p[i].sc.sc); vector<double> base(n); vi never_get(n); REP(i,n) { if(p[i].sc.sc==0) never_get[i]=1; else base[i]=(double)l/p[i].sc.sc; } vector<double> win(n); vector<vector<double> > takerest(n,vector<double>(m+1)); vector<vector<double> > dp(m+1,vector<double>(m+1)); REP(i2,n){ REP(i,m+1) REP(j,m+1) dp[i][j]=0; dp[0][0]=1.0; REP(i,m) REP(j,m){ if(dp[i][j]==0) continue; dp[i+1][j+1]+=dp[i][j]*p[i2].fr/100.0; dp[i+1][j]+=dp[i][j]*(100-p[i2].fr)/100.0; } REP(j2,m+1) takerest[i2][j2]=dp[m][j2]; } vector<vector<double> >rest_sum(n,vector<double>(m+1)); REP(i,n){ for(int j=m;j>=0;--j){ rest_sum[i][j]=(j+1<=m?rest_sum[i][j+1]:0)+takerest[i][j]; } } REP(i,n){ if(never_get[i]) continue; double prob,dif; REP(j,m+1){ prob=takerest[i][j]; REP(k,n){ if(i==k || never_get[k]) continue; dif=base[i]+p[i].sc.fr*j-base[k]; int mustrest; if(p[k].sc.fr==0) mustrest=INF; else mustrest=dif/(double)p[k].sc.fr+1; if(dif<0) mustrest=0; if(mustrest>m){ prob=0; break; } prob*=rest_sum[k][mustrest]; } win[i]+=prob; } } REP(i,n) printf("%.8f\n",win[i]); return 0; }
E
フローです。
辺を逆にも張って、逆に張った辺は逆に張ったということを記録。
フロー流して、逆の辺が使われていれば、配列にでも突っ込んでid順にソート
ちょっと蟻本を見た気がする
struct edge{ int to,id,rev,cap,reved; edge(){} edge(int st,int si,int sr,int sc,int sred){ to=st;id=si;rev=sr;cap=sc;reved=sred; } }; vector<vector<edge> > g; vi rank,seen; int n,m; int s,t; void bfs(int v){ rank[v]=0; queue<int> q;q.push(v); while(!q.empty()){ int cur=q.front();q.pop(); REP(i,g[cur].size()){ edge e=g[cur][i]; if(rank[e.to]!=INF || e.cap==0) continue; rank[e.to]=rank[cur]+1; q.push(e.to); } } } int dfs(int v){ if(v==t) return 1; for(int &i=seen[v];i<g[v].size();++i){ edge &e=g[v][i]; if(e.cap==0 || rank[e.to]<=rank[v]) continue; int f=dfs(e.to); if(f>0){ e.cap-=f; g[e.to][e.rev].cap+=f; return f; } } return 0; } int main(){ scanf("%d%d",&n,&m); g.resize(n); REP(i,m){ int a,b;scanf("%d%d",&a,&b);--a;--b; g[a].pb(edge(b,i+1,g[b].size(),1,0)); g[b].pb(edge(a,i+1,g[a].size()-1,1,1)); } scanf("%d%d",&s,&t);--s;--t; int flow=0; rank.resize(n);seen.resize(n); while(1){ fill(ALL(rank),INF); bfs(s); if(rank[t]==INF) break; fill(ALL(seen),0); int f; while((f=dfs(s))>0){ flow+=f; } } printf("%d\n",flow); vi road; REP(i,n) REP(j,SZ(g[i])){ if(g[i][j].reved && g[i][j].cap==0){ road.pb(g[i][j].id); } } sort(ALL(road)); printf("%d\n",SZ(road)); REP(i,SZ(road)) printf("%d\n",road[i]); return 0; }
F
最初何だこれって思ってたけどDPだと思ってみると案外簡単だった
AOJコンテストってTimeLimit長いイメージ
int main(){ int n;scanf("%d",&n); vi a(n); REP(i,n) scanf("%d",&a[i]); double res=1e11; vector<vector<double> > dp(n+1,vector<double>(200001,1e11));dp[0][1]=0; REP(i,n) REPN(j,200001,1){ if(dp[i][j]==1e11) continue; for(int k=j;k<=200000;k+=j){ if(i==n-1){ res=min(res,max(dp[i][j],(double)abs(k-a[i])/a[i])); }else dp[i+1][k]=min(dp[i+1][k],max(dp[i][j],(double)abs(k-a[i])/a[i])); } } printf("%.9f\n",res); return 0; }
後は解いてません。Gとか完全グラフにすればいいのは分かったけどどうやって求めるか分からなかった。適当な貪欲書いたけどWAになりました
他は呼んですらいない
