0294:Catch a Thief
問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0294
解説
http://web-ext.u-aizu.ac.jp/pc-concours/2014/download/pastexam/editorial2013_final.pdf
私は書籍「最新コンパイラ構成技法」のLengauer-Tarjanの擬似コードを参考にしました。
#include<iostream> #include<vector> #include<algorithm> #include<cassert> #define max_v 100010 using namespace std; int dfnum[max_v]; int vertex[max_v]; int parent[max_v]; int ancestor[max_v]; int idom[max_v]; int semi[max_v]; int samedom[max_v]; int best[max_v]; vector<int>bucket[max_v]; vector<int>G[max_v],rG[max_v]; void dfs(int p, int n,int &k){ if(dfnum[n]==0 && !(n==0 && p>0)){ dfnum[n]=k; vertex[k++]=n; parent[n]=p; for(int i=0;i<G[n].size();i++){ dfs(n,G[n][i],k); } } } int ancestorWithLowestSemi(int v){ int a=ancestor[v]; if(ancestor[a]>0){ int b=ancestorWithLowestSemi(a); ancestor[v]=ancestor[a]; if(dfnum[semi[b]] < dfnum[semi[best[v]]])best[v]=b; } return best[v]; } void link(int p,int n){ ancestor[n]=p; best[n]=n; } void dominator(int sz,int root){ for(int i=0;i<sz;i++){ bucket[i].clear(); dfnum[i]=semi[i]=ancestor[i]=idom[i]=samedom[i]=0; } int N=0; dfs(0,root,N); for(int i=N-1;i>0;i--){ int n=vertex[i],p=parent[n],s=p; for(int j=0;j<rG[n].size();j++){ int v=rG[n][j],s1; if(dfnum[v]<=dfnum[n])s1=v; else s1=semi[ancestorWithLowestSemi(v)]; if(dfnum[s1]<dfnum[s])s=s1; } semi[n]=s; bucket[s].push_back(n); link(p,n); for(int j=0;j<bucket[p].size();j++){ int v=bucket[p][j],y=ancestorWithLowestSemi(v); if(semi[y]==semi[v])idom[v]=p; else samedom[v]=y; } bucket[p].clear(); } for(int i=1;i<N;i++){ int n=vertex[i]; if(samedom[n]>0){ idom[n]=idom[samedom[n]]; } } for(int i=1;i<N;i++){ for(int j=0;j<rG[i].size();j++){ if(rG[i][j]==root)idom[i]=0; } } } int main(void){ int n,m; cin >> n >> m; for(int i=0;i<m;i++){ int s,t; cin >> s >> t; s--,t--; G[s].push_back(t); rG[t].push_back(s); } dominator(n,0); int q,r; cin >> q; while(q--){ cin >> r; r--; if(idom[r]==0)cout << r+1 << endl; else cout << idom[r]+1 << endl; } return 0; }
2201:Immortal Jewels
問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2201
金属棒の候補となる直線は
2円の共通内・外接線
2円の内一方の半径にmを足したものと他方の円の共通内・外接線
両方の半径にmを足したものの共通内・外接線
の3通り。これを全列挙して個数を数える。
のはずだが、自分のコードは3つ目の両方にmを足すパターンを試さなくても通ってしまっている。
#include<iostream> #include<vector> #include<algorithm> #include<cmath> #define all(c) (c).begin(),(c).end() using namespace std; typedef double Real; Real EPS = 1e-8; const Real PI = acos(-1); int sgn(Real a, Real b=0){return a<b-EPS?-1:a>b+EPS?1:0;} Real sqr(Real a){return sqrt(max(a,(Real)0));} struct Point{ Real add(Real a, Real b){ if(abs(a+b) < EPS*(abs(a)+abs(b)))return 0; return a+b; } Real x, y; Point(){} Point(Real x,Real y) : x(x) , y(y){} Point operator + (Point p){return Point(add(x,p.x), add(y,p.y));} Point operator - (Point p){return Point(add(x,-p.x), add(y,-p.y));} Point operator * (Real d){return Point(x*d,y*d);} Real norm(){return sqr(x*x+y*y);} Real dot(Point a){return x*a.x+y*a.y;} Real cross(Point a){return x*a.y-y*a.x;} Real arg(){ if(sgn(x)>0)return atan(y/x); if(sgn(x)<0)return atan(y/x)+PI; if(sgn(y)>0)return PI/2; if(sgn(y)<0)return 3*PI/2; return 0; } }; struct Line{ Point a,b; Line(){} Line(Point a,Point b):a(a),b(b){} Real dist(Point c){return abs((b-a).cross(c-a))/(b-a).norm();} }; struct Circle{ Point p; Real r; Circle(){} Circle(Point p, Real r) : p(p) , r(r){} Line tangent(Real theta){ Point a(r*cos(theta),r*sin(theta)); Point b(a.y,-a.x); return Line(p+a,p+a+b); } vector<Line> commonTangent(Circle x){ vector<Line>res; x.p=x.p-p; Real a=x.p.arg(); Real b[2]={(r-x.r),(r+x.r)}; for(int i=0;i<2;i++){ b[i]/=x.p.norm(); if(sgn(b[i],-1.0)<0 || sgn(b[i],1.0)>0)return res; Real c=asin(b[i])-asin(1.0); res.push_back(tangent(a-c)); res.push_back(tangent(a+c)); } return res; } }; int n; vector<Circle>c; vector<Real>m; vector<Line> enumerate(){ vector<Line>res; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i==j)continue; vector<Line>tmp=c[i].commonTangent(c[j]); for(int k=0;k<tmp.size();k++){ res.push_back(tmp[k]); } c[i].r+=m[i]; tmp=c[i].commonTangent(c[j]); for(int k=0;k<tmp.size();k++){ res.push_back(tmp[k]); } c[i].r-=m[i]; } } return res; } int count(Line l){ int cnt=0; for(int i=0;i<n;i++){ Real d=l.dist(c[i].p)-c[i].r; cnt+=(sgn(d)>=0 && sgn(d,m[i])<=0); } return cnt; } int main(void){ while(cin >> n,n){ c.resize(n); m.resize(n); for(int i=0;i<n;i++) cin >> c[i].p.x >> c[i].p.y >> c[i].r >> m[i]; vector<Line>res=enumerate(); int cnt=0; for(int i=0;i<res.size();i++){ cnt=max(cnt,count(res[i])); } cout << max(1,cnt) << endl; } return 0; }
0010:Circumscribed Circle of a Triangle
問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0010
前に通したコードを書き直したので。
#include<iostream> #include<vector> #include<algorithm> #include<cmath> #include<cstdio> using namespace std; typedef double Real; Real EPS = 1e-8; int sgn(Real a, Real b=0){return a<b-EPS?-1:a>b+EPS?1:0;} Real sqr(Real a){return sqrt(max(a,(Real)0));} struct Point{ Real add(Real a, Real b){ if(abs(a+b) < EPS*(abs(a)+abs(b)))return 0; return a+b; } Real x, y; Point(){} Point(Real x,Real y) : x(x) , y(y){} Point operator + (Point p){return Point(add(x,p.x), add(y,p.y));} Point operator - (Point p){return Point(add(x,-p.x), add(y,-p.y));} Point operator * (Real d){return Point(x*d,y*d);} Point operator / (Real d){return Point(x/d,y/d);} Real norm(){return sqr(x*x+y*y);} Real dist(Point a){return (*this-a).norm();} Real dot(Point a){return x*a.x+y*a.y;} Real cross(Point a){return x*a.y-y*a.x;} }; struct circle{ Point p; Real r; circle(){} circle(Point p, Real r) : p(p) , r(r){} }; circle circumscribedCircle(Point p, Point q, Point r){ Point a,b,c; a=(q-p)*2,b=(r-p)*2; c.x=p.dot(p)-q.dot(q); c.y=p.dot(p)-r.dot(r); circle res; res.p.x=a.y*c.y-b.y*c.x; res.p.y=b.x*c.x-a.x*c.y; res.p=res.p/a.cross(b); return circle(res.p, p.dist(res.p)); } int main(void){ int n; cin >> n; while(n--){ vector<Point>v(3); for(int i=0;i<3;i++) cin >> v[i].x >> v[i].y; circle res=circumscribedCircle(v[0],v[1],v[2]); printf("%.3f %.3f %.3f",res.p.x,res.p.y,res.r); cout << endl; } return 0; }
NPCA Judge 97:永続segtree
問題文
http://judge.npca.jp/problems/view/97
参考にさせていただきました
http://sigma425.hatenablog.com/entry/2014/12/30/164148
i回目のループで、x回目のループ終了時点での配列aの[l,r)の区間に含まれる数の個数を答えるので永続segtreeが必要。
#include<iostream> #include<vector> #include<algorithm> #include<cassert> using namespace std; typedef long long ll; struct node_t{ int num; node_t *lch,*rch; node_t(node_t *l,node_t *r,int n):num(n),lch(l),rch(r){} node_t(node_t *l,node_t *r):lch(l),rch(r){ num=(l?l->num:0)+(r?r->num:0); } node_t(){} }; node_t tree[5000000]; node_t *root[200005]; //root[number_of_query] struct PersistentSegmentTree{ private: int numOfNode,now,cur; node_t *nil; node_t *new_node(node_t *lch,node_t *rch,int num){ return &(tree[cur++]=node_t(lch,rch,num)); } node_t *new_node(node_t *lch,node_t *rch){ return &(tree[cur++]=node_t(lch,rch)); } node_t *update(int id, int l,int r, node_t *t){ if(r-l<=1)return new_node(nil,nil,t->num+1); int m=(l+r)/2; if(id<m)return new_node(update(id,l,m,t->lch),t->rch); else return new_node(t->lch,update(id,m,r,t->rch)); } int query(int a,int b,int l,int r,node_t *t){ if(t==nil)return 0; if(b<=l || r<=a)return 0; if(a<=l && r<=b)return t->num; int m=(l+r)/2; return query(a,b,l,m,t->lch)+query(a,b,m,r,t->rch); } public: PersistentSegmentTree(int n):numOfNode(n),now(0),cur(0){ root[0]=nil=new_node(0,0,0); nil->lch=nil->rch=nil; } void update(int id){ root[now+1]=update(id,0,numOfNode,root[now]); now++; } int query(int a,int b,int x){ return query(a,b,0,numOfNode,root[x]); } }; int main(void){ int n; cin >> n; vector<int>l(n),r(n); for(int i=0;i<n;i++)cin >> l[i]; for(int i=0;i<n;i++)cin >> r[i]; PersistentSegmentTree t(n); int x=0; for(int i=0;i<n;i++){ t.update(x); ll cnt=t.query(l[i],r[i],x+1); x=(cnt*l[i]+r[i])%(i+2); //cout << x << " " << cnt << endl; } cout << x << endl; return 0; }
3580:SuperMemo
問題文
http://poj.org/problem?id=3580
区間への加算
区間の反転
区間の右巡回シフト
挿入
削除
区間の最小値
のクエリがくるので処理する問題。
参考にしたもの
http://www.slideshare.net/iwiwi/2-12188757
mergeやsplitとかは参考スライドのもの。
区間 [l,r) の反転、挿入、削除
参考スライド通り。
この問題では指定されたidの直後に挿入なので注意。
区間 [l,r) への加算
参考スライドの反転と同じように。
自分のコードでは変数lazyに、区間へ一様に加算された値を持っている。
区間 [l,r) をt回だけ右巡回シフト
t%=(r-l)する。
木を場所l,r-t,rでsplit->左からa,b,c,dとする。
a,c,b,dとなるようにmerge。
区間 [l,r) の最小値
l,rでsplit->真ん中の木の根のmin
minとるときにlazy足す。
#include<iostream> #include<vector> #include<algorithm> #include<climits> #include<string> #include<ctime> #include<cstdio> #include<cstdlib> #define INF (1LL<<62) using namespace std; typedef long long ll; template<class T> struct Treap { public: struct node_t{ T val,mini,sum,lazy; node_t *lch,*rch; int pri,cnt; bool rev; node_t(T v,int p):val(v),mini(v),sum(v),pri(p),cnt(1){ lch=rch=NULL; lazy=0; rev=false; } }; node_t *root; Treap():root(NULL){} private: T val(node_t *t){return t->val+t->lazy;} int count(node_t *t){return !t?0:t->cnt;} T sum(node_t *t){return !t?0:t->sum+t->lazy*count(t);} T mini(node_t *t){return !t?INF:t->mini+t->lazy;} node_t *update(node_t *t){ if(!t)return t; t->cnt=count(t->lch)+count(t->rch)+1; //t->sum=sum(t->lch)+sum(t->rch)+val(t); t->mini=min(min(mini(t->lch),mini(t->rch)),val(t)); if(t->lazy){ t->val+=t->lazy; if(t->lch)t->lch->lazy+=t->lazy; if(t->rch)t->rch->lazy+=t->lazy; t->lazy=0; } if(t->rev){ swap(t->lch,t->rch); if(t->lch)t->lch->rev^=true; if(t->rch)t->rch->rev^=true; t->rev=false; } return t; } node_t *merge(node_t *l, node_t *r){ l=update(l), r=update(r); if(!l || !r)return l?l:r; if(l->pri > r->pri){ l->rch=merge(l->rch,r); return update(l); } else { r->lch=merge(l,r->lch); return update(r); } } //[0,k),[k,n) pair<node_t *,node_t *> split(node_t *t,int k){ if(!update(t))return make_pair((node_t *)NULL,(node_t *)NULL); if(k<=count(t->lch)){ pair<node_t *,node_t *>s=split(t->lch,k); t->lch=s.second; return make_pair(s.first,update(t)); } else { pair<node_t *,node_t *>s=split(t->rch,k-count(t->lch)-1); t->rch=s.first; return make_pair(update(t),s.second); } } node_t *insert(node_t *t,int k,T val,int pri){ pair<node_t *,node_t *>s=split(t,k); t=merge(s.first, new node_t(val,pri)); t=merge(t,s.second); return update(t); } node_t *erase(node_t *t,int k){ pair<node_t *,node_t *>s1,s2; s2=split(t,k+1); s1=split(s2.first,k); delete s1.second; return update((t=merge(s1.first,s2.second))); } node_t *find(node_t *t, int k){ int c=count(t->lch); if(k<c)return find(t->lch, k); if(k==c)return t; return find(t->rch, k-c-1); } public: void insert(int k,T val){ root=insert(root,k,val,rand()); } void erase(int k){ root=erase(root,k); } node_t *find(int k){ return find(root,k); } void add(int id,T val){ node_t *a=find(id); T tmp=val(a); erase(id); insert(id,tmp+val); } void rangeAdd(int l,int r,T v){ pair<node_t *,node_t *>s1,s2; s2=split(root,r); s1=split(s2.first,l); s1.second->lazy+=v; root=merge(s1.first,s1.second); root=merge(root,s2.second); } void update(int id,T val){ erase(id); insert(id,val); } //range query [l,r), 0-origin T rangeMinimumQuery(int l,int r){ pair<node_t *,node_t *>s1,s2; s2=split(root,r); s1=split(s2.first,l); T res=mini(s1.second); root = merge(s1.first,merge(s1.second,s2.second)); return res; } T rangeSumQuery(int l,int r){ pair<node_t *,node_t *>s1,s2; s2=split(root,r); s1=split(s2.first,l); T res=sum(s1.second); root = merge(s1.first,merge(s1.second,s2.second)); return res; } /* reverse(1,4) {1,2,3,4,5} -> {1,4,3,2,5} */ void reverse(int l,int r){ pair<node_t *,node_t *>s1,s2; s2=split(root,r); s1=split(s2.first,l); node_t *a=s1.first,*b=s1.second,*c=s2.second; b->rev^=true; root=merge(a,b); root=merge(root,c); } /* revolve(1,4,2) {1,2,3,4,5} -> {1,3,4,2,5} */ void revolve(int l,int r,int t){ t%=(r-l); pair<node_t*, node_t*>a,b,c; c=split(root, r); b=split(c.first, r-t); a=split(b.first, l); root=merge(a.first, b.second); root=merge(root, a.second); root=merge(root, c.second); } }; int main(void){ srand(time(NULL)); int n,m,in; Treap<ll> t; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&in); t.insert(i,in); } cin >> m; char com[10]; int x,y,T,D,P; for(int i=0;i<m;i++){ scanf("%s",com); if(com[0]=='A'){ scanf("%d %d %d",&x,&y,&D); t.rangeAdd(x-1,y,D); } else if(com[0]=='R' && com[3]=='E'){ scanf("%d %d",&x,&y); t.reverse(x-1,y); } else if(com[0]=='R' && com[3]=='O'){ scanf("%d %d %d",&x,&y,&T); t.revolve(x-1,y,T); } else if(com[0]=='I'){ scanf("%d %d",&x,&P); t.insert(x,P); } else if(com[0]=='D'){ scanf("%d",&x); t.erase(x-1); } else if(com[0]=='M'){ scanf("%d %d",&x,&y); printf("%lld\n",t.rangeMinimumQuery(x-1,y)); } } return 0; }
1131: Unit Fraction Partition
問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1131&lang=jp
解き直し。
y/x+1/z=(yz+x)/xz
だから、これを使って探索。枝刈りはしなくても通る。
#include<iostream> #include<vector> #include<algorithm> using namespace std; int p,q,a,n; int rec(int x,int y,int now,int dep){ if(x*p==q*y)return 1; if(dep==0)return 0; int sum=0; for(int z=now;z*x<=a;z++){ if(y/x+1/z<=p/q)sum+=rec(z*x,z*y+x,z,dep-1); } return sum; } int main(void){ while(cin >> p >> q >> a >> n,p|q|a|n){ cout << rec(1,0,1,n) << endl; } return 0; }
1156: Twirling Robot
問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156
g[現在の方向][Y][X]:=最短距離
でダイクストラ。
#include<iostream> #include<vector> #include<algorithm> #include<queue> #define rep(i,n) for(int i=0;i<(n);i++) #define INF (1<<29) #define Cost first.first #define Dir first.second #define X second.first #define Y second.second using namespace std; typedef pair<int,int> p2; typedef pair<p2,p2> p4; int w,h,g[4][31][31],s[31][31],c[4]; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; int dijkstra(){ priority_queue<p4,vector<p4>, greater<p4> >que; fill(*g[0],*g[4],INF); g[0][0][0]=0; p4 st = p4(p2(0,0),p2(0,0)); que.push(st); bool fg=false; while(!que.empty()){ p4 now = que.top(); que.pop(); if(now.Y==h-1 && now.X==w-1)return now.Cost; if(g[now.Dir][now.Y][now.X]<=now.Cost && fg)continue; fg=true; g[now.Dir][now.Y][now.X]=now.Cost; rep(d,4){ p4 next; next.Dir=(now.Dir+d)%4; next.X=now.X+dx[next.Dir],next.Y=now.Y+dy[next.Dir]; if(0<=next.X && next.X<w && 0<=next.Y && next.Y<h){ next.Cost=now.Cost+c[d]*(s[now.Y][now.X]!=d); que.push(next); } } } return -1; } int main(void){ while(cin >> w >> h,w|h){ rep(i,h)rep(j,w)cin >> s[i][j]; rep(i,4)cin >> c[i]; cout << dijkstra() << endl; } return 0; }