JOI2012本選5番
#include <vector> #include <queue> #include <stdio.h> #include <algorithm> #include <string.h> #include <queue> #define MAX_V 100000+10 #define MAX_Q 100000+10 #define INF (1<<28) #define ROOT 1 using namespace std; struct Edge{ int to,cost; }; Edge makeE(int t,int c){ Edge e;e.to=t,e.cost=c; return e; } bool operator < (const Edge &e,const Edge &f){ return e.cost>f.cost; } struct Biedge{ int a,b,cost; }; Biedge makeB(int aa,int bb,int c){ Biedge e;e.a=aa,e.b=bb,e.cost=c; return e; } bool operator < (const Biedge &e,const Biedge &f){ return e.cost>f.cost; } class Unionfind{ public: vector<int> data; Unionfind(int n){ for(int i=0;i<n;i++) data.push_back(i); } int root(int a){ //printf("root(%d)\n",a); if(data[a]==a) return a; else return data[a]=root(data[a]); } void set(int a,int b){ if(root(a)==root(b)) return; else data[root(a)]=root(b); } }; int fest[MAX_V],dist[MAX_V],qa[MAX_Q],qb[MAX_Q],qr[MAX_Q],depth[MAX_V],score[32][MAX_V],parent[32][MAX_V]; vector<Biedge> biedge; vector<Edge> G[MAX_V]; vector<Edge> MG[MAX_V]; void dfs(int v,int p,int s,int d){ parent[0][v]=p; score[0][v]=s; depth[v]=d; for(int i=0;i<(int)MG[v].size();i++) if(MG[v][i].to!=p) dfs(MG[v][i].to,v,MG[v][i].cost,d+1); } void init(int n){ dfs(ROOT,-1,dist[ROOT],0); for(int k=0;k+1<32;k++) for(int i=0;i<n;i++){ if(parent[k][i]<0) parent[k+1][i]=-1; else{ score[k+1][i]=min(score[k][parent[k][i]],score[k][i]); parent[k+1][i]=parent[k][parent[k][i]]; } } } int lca(int u,int v){ int res=INF; if(depth[u]>depth[v]) swap(u,v); for(int k=0;k<32;k++) if((depth[v]-depth[u])>>k&1){ res=min(res,score[k][v]); v=parent[k][v]; } //printf("lca-m\n");fflush(stdout); if(u==v) return res; for(int k=31;0<=k;k--) if(parent[k][u]!=parent[k][v]){ res=min(res,score[k][u]); u=parent[k][u]; res=min(res,score[k][v]); v=parent[k][v]; } res=min(res,score[0][u]); res=min(res,score[0][v]); return res; } int main(){ int n,m,k,q; scanf("%d%d%d%d",&n,&m,&k,&q); for(int i=0;i<m;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); G[a].push_back(makeE(b,c)); G[b].push_back(makeE(a,c)); biedge.push_back(makeB(a,b,0)); } for(int i=0;i<k;i++) scanf("%d",fest+i); for(int i=0;i<q;i++) scanf("%d%d",qa+i,qb+i); for(int i=0;i<MAX_V;i++) dist[i]=INF; priority_queue<Edge> que; for(int i=0;i<k;i++){ que.push(makeE(fest[i],0)); dist[fest[i]]=0; } while(!que.empty()){ int t=que.top().to,c=que.top().cost; que.pop(); if(dist[t]<c) continue; for(int i=0;i<(int)G[t].size();i++){ int tt=G[t][i].to,cc=c+G[t][i].cost; if(cc<dist[tt]){ que.push(makeE(tt,cc)); dist[tt]=cc; } } } for(int i=0;i<m;i++) biedge[i].cost=min(dist[biedge[i].a],dist[biedge[i].b]); sort(biedge.begin(),biedge.end()); memset(qr,-1,sizeof(qr)); Unionfind un(n+1); for(int i=0;i<m;i++){ if(un.root(biedge[i].a)!=un.root(biedge[i].b)){ un.set(biedge[i].a,biedge[i].b); MG[biedge[i].a].push_back(makeE(biedge[i].b,biedge[i].cost)); MG[biedge[i].b].push_back(makeE(biedge[i].a,biedge[i].cost)); } } init(n+1); for(int i=0;i<q;i++) printf("%d\n",lca(qa[i],qb[i])); return 0; }
JOI2012本選４番
講義資料 - いもす研 (imos laboratory)
↑参照。
累積和を使ったコード
#include <stdio.h> int nails[5010][5010]; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ int a,b,x; scanf("%d%d%d",&a,&b,&x); nails[a][b]++,nails[a][b+1]--; nails[a+x+1][b]--,nails[a+x+2][b+1]++; nails[a+x+1][b+x+2]++,nails[a+x+2][b+x+2]--; } for(int i=0;i<5010;i++){ int a=0; for(int j=0;j<5010;j++){ a+=nails[i][j]; nails[i][j]=a; } } for(int i=0;i<5010;i++){ int a=0; for(int j=0;j<5010;j++){ a+=nails[j][i]; nails[j][i]=a; } } for(int i=0;i<5010;i++){ int a=0; for(int j=0;i+j<5010;j++){ a+=nails[i+j][j]; nails[i+j][j]=a; } } int ans=0; for(int i=0;i<5010;i++) for(int j=0;j<5010;j++) if(0<nails[i][j]) ans++; printf("%d\n",ans); return 0; }
最大値の伝搬を使ったコード（ただし後ろから）。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int nails[5010][5010]; int main(){ int n,m; scanf("%d%d",&n,&m); memset(nails,0,sizeof(nails)); for(int i=0;i<m;i++){ int a,b,x; scanf("%d%d%d",&a,&b,&x); nails[a+x][b+x]=max(nails[a+x][b+x],x+1); } int ans=0; for(int y=n;0<=y;y--) for(int x=n;0<=x;x--){ if(0<nails[y][x]) ans++; if(0<x) nails[y][x-1]=max(nails[y][x-1],nails[y][x]-1); if(0<x&&0<y) nails[y-1][x-1]=max(nails[y-1][x-1],nails[y][x]-1); } printf("%d\n",ans); return 0; }
JOI2012本選3番
時間がSにかぶるときだけ気をつけてdpすればOK。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int n,S,T; int A[3010],B[3010]; int dp[3010][3010]; int rec(int store,int time){ if(store==n) return 0; else if(dp[store][time]!=-1) return dp[store][time]; else{ int res=rec(store+1,time); if(time<S&&S<time+B[store]){ if(S+B[store]<=T){ res=max(res,rec(store+1,S+B[store])+A[store]); } }else{ if(time+B[store]<=T){ res=max(res,rec(store+1,time+B[store])+A[store]); } } return dp[store][time]=res; } } int main(){ scanf("%d%d%d",&n,&T,&S); for(int i=0;i<n;i++) scanf("%d%d",A+i,B+i); memset(dp,-1,sizeof(dp)); int ans=rec(0,0); printf("%d\n",ans); return 0; }
JOI2012本選2番
dp[ap=Aの何枚目か][bp=Bの何枚目か]でDPした。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int dp[5010][5010]; int ac[5010],bc[5010]; int rec(int ap,int bp){ if(ap<0||bp<0) return 0; else if(dp[ap][bp]!=-1) return dp[ap][bp]; else{ int r=rec(ap-1,bp); if(ac[ap]==bc[bp]) r=max(r,rec(ap-1,bp-1)+1); return dp[ap][bp]=r; } } int main(){ int an,bn; scanf("%d%d",&an,&bn); for(int i=0;i<an;i++) scanf("%d",ac+i); for(int i=0;i<bn;i++) scanf("%d",bc+i); memset(dp,-1,sizeof(dp)); int ans=0; for(int i=0;i<an;i++) for(int j=0;j<bn;j++) ans=max(ans,rec(i,j)); printf("%d\n",ans); return 0; }
JOI2012本選1番
解説を聞いてから自分のやっていたことがRunLength圧縮と同じであると気づいた。
#include <stdio.h> #include <vector> using namespace std; char in[10000000+10]; int main(){ scanf("%s",in); vector<int> ch,sq; int c=in[0],s=1; for(int i=1;in[i]!=0&&in[i]!='\n';i++){ if(c!=in[i]){ ch.push_back(c); sq.push_back(s); c=in[i]; s=1; }else{ s++; } } ch.push_back(c); sq.push_back(s); int ans=0; for(int i=0;i+2<(int)ch.size();i++){ if(ch[i]=='J'&&ch[i+1]=='O'&&ch[i+2]=='I'&&sq[i+1]<=min(sq[i],sq[i+2])) ans=max(ans,min(sq[i],sq[i+1])); } printf("%d\n",ans); return 0; }
JOI2012本選まとめ
↑の大会に参加してきました。
実力を限界まで発揮できたと思います。
合宿は問題を楽しむだけにしようと思います。
JOI2011本選5番
kについて二分探索した後、その判定を頑張ってO(n)で出来るようにする。
#include <stdio.h> #include <utility> #include <set> #include <algorithm> #include <vector> #define MAX_V 1000100 using namespace std; int n; int ai[MAX_V],can[MAX_V],bi2ai[MAX_V]; pair<int,int> bi[MAX_V]; int ok(int k) { if(k==0) return 1; double sumA=0; for(int i=0;i<n;i++) can[i]=1; for(int i=0;i<k;i++) sumA+=ai[i]; int lastA=k-1; for(int b=0;b+k<=n;b++) { if(sumA/(double)k<=(double)bi[b].first) return 1; int tP=bi2ai[b]; can[tP]=0; if(tP<=lastA) { sumA-=ai[tP]; lastA++; if(lastA>=n) return 0; while(!can[lastA]) lastA++; sumA+=ai[lastA]; } } return 0; } int main() { scanf("%d",&n); for(int i=0;i<n;i++) { int a,b; scanf("%d%d",&a,&b); ai[i]=a; can[i]=1; bi2ai[i]=-1; bi[i]=make_pair(b,-a); } sort(ai,ai+n); sort(bi,bi+n); for(int i=0;i<n;i++) { int a=-bi[i].second; int tB=lower_bound(ai,ai+n,a)-ai; int tE=upper_bound(ai,ai+n,a)-ai; int tP; for(tP=tB;tP<tE;tP++) if(can[tP]) break; can[tP]=0; bi2ai[i]=tP; } int b=0,c=n; while(1<c-b) { int m=(b+c)/2; if(ok(m)) b=m; else c=m; } if(ok(c)) printf("%d\n",c); else printf("%d\n",b); return 0; }
