AOJ-ICPC 700埋め(1)
700を埋め始めました。昨日今日でつぶした4問を載せます。全体的に(というか全部)筋肉。
- AOJ 1314 Matrix Calculator
ひたすら物量構文解析。行列積の結果が正方行列にしかならないクソバグを埋め込んだのに1ケースしか落ちず苦労した。テストケースが見えるのは正義。
#include<stdio.h> #include<vector> #include<algorithm> #include<string> #include<iostream> using namespace std; typedef vector<vector<int> >mat; int mod=32768; void matp(mat a) { for(int i=0;i<a.size();i++) { for(int j=0;j<a[i].size();j++) { if(j!=0)printf(" "); printf("%d",a[i][j]); } printf("\n"); } } mat pls(mat a,mat b) { for(int i=0;i<a.size();i++)for(int j=0;j<a[i].size();j++)a[i][j]=(a[i][j]+b[i][j])%mod; return a; } mat neg(mat a) { for(int i=0;i<a.size();i++)for(int j=0;j<a[i].size();j++)a[i][j]=(mod-a[i][j])%mod; return a; } mat tim(mat a,mat b) { if(a.size()==1&&a[0].size()==1) { swap(a,b); } if(b.size()==1&&b[0].size()==1) { for(int i=0;i<a.size();i++)for(int j=0;j<a[i].size();j++)a[i][j]=(a[i][j]*b[0][0])%mod; return a; } mat ret; ret.resize(a.size()); for(int i=0;i<ret.size();i++)ret[i].resize(b[0].size()); for(int i=0;i<a.size();i++)for(int j=0;j<b[0].size();j++)for(int k=0;k<b.size();k++)ret[i][j]=(ret[i][j]+a[i][k]*b[k][j])%mod; return ret; } mat trans(mat a) { mat ret; ret.resize(a[0].size()); for(int i=0;i<ret.size();i++)for(int j=0;j<a.size();j++)ret[i].push_back(a[j][i]); return ret; } mat ind(mat a,mat b,mat c) { mat ret; ret.resize(b[0].size()); for(int i=0;i<b[0].size();i++)ret[i].resize(c[0].size()); for(int i=0;i<b[0].size();i++)for(int j=0;j<c[0].size();j++)ret[i][j]=a[b[0][i]-1][c[0][j]-1]; return ret; } string str; int pt; mat dat[26]; mat ass(); mat expr(); mat term(); mat factor(); mat prim(); mat inum(); mat matrix(); mat row(); mat rowseq(); mat ass() { pt+=2; mat x=expr(); dat[str[0]-'A']=x; return x; } mat expr() { //printf("expr %d\n",pt); mat now=term(); for(;;) { if(str[pt]=='+') { pt++; now=pls(now,term()); } else if(str[pt]=='-') { pt++; now=pls(now,neg(term())); } else break; } //printf("rexpr %d\n",pt); //matp(now); return now; } mat term() { //printf("term %d\n",pt); mat now=factor(); for(;;) { if(str[pt]=='*') { pt++; now=tim(now,factor()); } else break; } //printf("rterm %d\n",pt); //matp(now); return now; } mat factor() { //printf("fact %d\n",pt); mat ret; if(str[pt]=='-') { pt++; ret=neg(factor()); } else { ret=prim(); } //printf("rfact %d\n",pt); //matp(ret); return ret; } mat inum() { int now=0; for(;;) { if(str[pt]<'0'||'9'<str[pt])break; now*=10; now+=str[pt]-'0'; pt++; } mat a; a.resize(1); a[0].push_back(now); return a; } mat prim() { //printf("prim %d\n",pt); mat ret; if('0'<=str[pt]&&str[pt]<='9')ret=inum(); else if('A'<=str[pt]&&str[pt]<='Z') { ret=dat[str[pt]-'A']; pt++; } else if(str[pt]=='[')ret=matrix(); else { pt++; ret=expr(); pt++; } //printf("mprim %d\n",pt); for(;;) { if(str[pt]=='\'') { ret=trans(ret); pt++; } else if(str[pt]=='(') { pt++; mat a=expr(); pt++; mat b=expr(); pt++; ret=ind(ret,a,b); } else break; } //printf("rprim %d\n",pt); //matp(ret); return ret; } mat matrix() { //printf("mat %d\n",pt); pt++; mat ret=rowseq(); pt++; //printf("rmat %d\n",pt); //matp(ret); return ret; } mat rowseq() { //printf("rseq %d\n",pt); mat ret; ret=row(); for(;;) { if(str[pt]==';') { pt++; mat z=row(); for(int i=0;i<z.size();i++) { ret.push_back(z[i]); } } else break; } //printf("rrseq %d\n",pt); //matp(ret); return ret; } mat row() { mat ret=expr(); for(;;) { if(str[pt]==' ') { pt++; mat z=expr(); for(int i=0;i<z.size();i++) { for(int j=0;j<z[i].size();j++) { ret[i].push_back(z[i][j]); } } } else break; } return ret; } int main() { for(;;) { int num; scanf("%d",&num); if(num==0)break; getchar(); for(int p=0;p<num;p++) { str.clear(); pt=0; for(;;) { char z; z=getchar(); if(z=='\n')break; str.push_back(z); } matp(ass()); } printf("-----\n"); } }
- AOJ 1143 六角大蛇
適当な幅優先+超適当枝刈り。闇問題として有名だったので身構えたが、これが一番実装が楽だった気がする。枝刈りはクッソ適当でも通るので精神衛生に良い。
#include<stdio.h> #include<vector> #include<algorithm> #include<queue> #include<map> #include<set> #include<math.h> #include<stdlib.h> using namespace std; typedef pair<int,int>pii; typedef pair<int,vector<pii> >piv; int dx[6]={0,-1,-1,0,1,1}; int dy[6]={-1,0,1,1,0,-1}; set<pii>se; vector<vector<pii> >dat; bool isad(pii a,pii b) { if(abs(a.first-b.first)+abs(a.second-b.second)<=1)return true; if(abs(a.first-b.first)+abs(a.second-b.second)==2&&(a.first-b.first)+(a.second-b.second)==0)return true; return false; } void get(vector<pii>now,int pt,bool flag) { if(pt==now.size()) { dat.push_back(now); return; } //for(int i=0;i<now.size();i++)printf("%d %d ",now[i].first,now[i].second);printf("\n"); bool f=true; for(int i=0;i<pt-1;i++)if(isad(now[pt],now[i]))f=false; if(pt!=0)if((!isad(now[pt-1],now[pt]))||now[pt-1]==now[pt])f=false; if(f)get(now,pt+1,true); if(flag) { for(int i=0;i<6;i++) { now[pt].first+=dx[i]; now[pt].second+=dy[i]; bool fl=true; if(pt!=0)if((!isad(now[pt-1],now[pt]))||now[pt-1]==now[pt])fl=false; if(se.find(now[pt])!=se.end())fl=false; for(int j=0;j<pt-1;j++)if(isad(now[pt],now[j]))fl=false; if(fl) { //printf(" %d %d %d\n",pt,now[pt].first,now[pt].second); get(now,pt+1,false); } now[pt].first-=dx[i]; now[pt].second-=dy[i]; } } } int main() { for(;;) { int num; scanf("%d",&num); if(num==0)break; vector<pii>beg; se.clear(); for(int i=0;i<num;i++) { int za,zb; scanf("%d%d",&za,&zb); beg.push_back(make_pair(za,zb)); } int ob; scanf("%d",&ob); for(int i=0;i<ob;i++) { int za,zb; scanf("%d%d",&za,&zb); se.insert(make_pair(za,zb)); } int gx,gy; scanf("%d%d",&gx,&gy); queue<piv>que; que.push(make_pair(0,beg)); map<vector<pii>,int>ma; for(;;) { if(que.empty())break; piv zan=que.front(); que.pop(); if(max(abs(zan.second[0].first-gx),abs(zan.second[0].second-gy))>20-zan.first)continue; if(ma[zan.second]!=0)continue; ma[zan.second]=1; //printf("%d\n",zan.first); //for(int i=0;i<num;i++)printf("%d %d ",zan.second[i].first,zan.second[i].second);printf("\n"); if(zan.second[0]==make_pair(gx,gy)) { printf("%d\n",zan.first); break; } dat.clear(); get(zan.second,0,true); for(int i=0;i<dat.size();i++) { que.push(make_pair(zan.first+1,dat[i])); } } } }
- AOJ 2017 Karakuri Doll
やることは変な深さ優先探索。最初の1手は方向転換ができないということを見落としていて困っていた。サンプルを間違えてもどう間違えてるのかを判断するのすら難しい。そこそこ強いけどデバッグの役にはたたないサンプル。
#include<stdio.h> #include<vector> #include<algorithm> #include<iostream> using namespace std; typedef pair<int,int>pii; typedef pair<pii,int>pi3; typedef pair<pi3,pi3>pi6; int map[16][64]; pii pat[16][64][4]; vector<pii>rpat[16][64][4]; bool flag[16][64][4][16][64][4]; bool flag2[16][64][4]; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; vector<pair<pi3,pi3> >deb; int cnt=0; void calc(int nx1,int ny1,int nd1,int nx2,int ny2,int nd2,int t) { if(flag[nx1][ny1][nd1][nx2][ny2][nd2])return; flag[nx1][ny1][nd1][nx2][ny2][nd2]=true; //printf("%d %d %d %d %d %d\n",nx1,ny1,nd1,nx2,ny2,nd2); /*deb.push_back(make_pair(make_pair(make_pair(nx1,ny1),nd1),make_pair(make_pair(nx2,ny2),nd2))); if(nx1==2&&ny1==5&&nx2==2&&ny2==5) { for(int i=0;i<deb.size();i++)printf("%d: %d %d %d %d %d %d\n",cnt,deb[i].first.first.first,deb[i].first.first.second,deb[i].first.second,deb[i].second.first.first,deb[i].second.first.second,deb[i].second.second); cnt++; }*/ for(int i=0;i<4;i++) { if((i%2==0&&t!=0)||(t==0&&i!=0))continue; for(int j=0;j<rpat[nx2][ny2][(nd2+i)%4].size();j++) { pii n1=pat[nx1][ny1][(nd1+i)%4]; pii n2=rpat[nx2][ny2][(nd2+i)%4][j]; //printf("%d %d %d %d\n",n1.first,n1.second,n2.first,n2.second); calc(n1.first,n1.second,(nd1+i)%4,n2.first,n2.second,(nd2+i)%4,t+1); } } //deb.pop_back(); } void calc2(int nx1,int ny1,int nd1,int t) { if(flag2[nx1][ny1][nd1])return; flag2[nx1][ny1][nd1]=true; //printf("%d %d %d\n",nx1,ny1,nd1); /*deb.push_back(make_pair(make_pair(make_pair(nx1,ny1),nd1),make_pair(make_pair(nx2,ny2),nd2))); if(nx1==2&&ny1==5&&nx2==2&&ny2==5) { for(int i=0;i<deb.size();i++)printf("%d: %d %d %d %d %d %d\n",cnt,deb[i].first.first.first,deb[i].first.first.second,deb[i].first.second,deb[i].second.first.first,deb[i].second.first.second,deb[i].second.second); cnt++; }*/ for(int i=0;i<4;i++) { if((i%2==0&&t!=0)||(t==0&&i!=0))continue; pii n1=pat[nx1][ny1][(nd1+i)%4]; //printf("%d %d %d %d\n",n1.first,n1.second,n2.first,n2.second); calc2(n1.first,n1.second,(nd1+i)%4,t+1); } //deb.pop_back(); } int main() { for(;;) { int my,mx; scanf("%d%d",&my,&mx); if(mx==0&&my==0)break; int sx,sy,gx,gy; for(int i=0;i<mx;i++) { for(int j=0;j<my;j++) { char zan; scanf(" %c",&zan); if(zan=='#')map[i][j]=-1; else map[i][j]=0; if(zan=='K')sx=i,sy=j; if(zan=='M')gx=i,gy=j; } } for(int i=0;i<mx;i++)for(int j=0;j<my;j++)for(int k=0;k<4;k++)for(int l=0;l<mx;l++)for(int m=0;m<my;m++)for(int n=0;n<4;n++)flag[i][j][k][l][m][n]=false; for(int i=0;i<mx;i++)for(int j=0;j<my;j++)for(int k=0;k<4;k++)rpat[i][j][k].clear(); for(int i=0;i<mx;i++)for(int j=0;j<my;j++)for(int k=0;k<4;k++)flag2[i][j][k]=false; for(int i=0;i<mx;i++) { for(int j=0;j<my;j++) { for(int k=0;k<4;k++) { if(map[i][j]!=0)continue; int nx=i,ny=j; for(;;) { if(map[nx+dx[k]][ny+dy[k]]!=0)break; nx+=dx[k]; ny+=dy[k]; } pat[i][j][k]=make_pair(nx,ny); rpat[nx][ny][(k+2)%4].push_back(make_pair(i,j)); //printf("%d %d %d %d %d %d\n",i,j,k,nx,ny,(k+2)%4); } } } int sd,gd; for(int i=0;i<4;i++)if(map[sx+dx[i]][sy+dy[i]]==0)sd=i; for(int i=0;i<4;i++)if(map[gx-dx[i]][gy-dy[i]]==0)gd=i; //printf("%d %d\n",sd,gd); for(int i=0;i<4;i++)calc(sx,sy,sd,sx,sy,i,0); calc2(sx,sy,sd,0); int fl=0; for(int k=0;k<4;k++)if(flag2[gx][gy][k])fl=1; for(int k=0;k<4;k++)if(flag[gx][gy][k][gx][gy][gd])fl=2; if(fl==0)printf("He cannot bring tea to his master.\n"); if(fl==1)printf("He cannot return to the kitchen.\n"); if(fl==2)printf("He can accomplish his mission.\n"); } }
- AOJ 1152 部陪博士
構文解析+木の同型性判定+...みたいな問題。一個一個は軽いけどひたすらやることが多い。DFSをしている関数が無限にある。
木の形は最初は全部左が大きいとしておいて、出力の時にいじるのが楽。
#include<stdio.h> #include<vector> #include<algorithm> #include<string> #include<iostream> using namespace std; typedef pair<int,int>pii; pii ko[128]; bool map[128][128]; string str; int pt; int vpt; void dfs() { if(str[pt]=='(') { pt++; int now=vpt; ko[now].first=++vpt; dfs(); pt++; ko[now].second=++vpt; dfs(); pt++; } else { pt++; } return; } void calc(int na,int nb) { if(ko[nb].first==-1) { if(ko[na].first==-1)map[na][nb]=true; else map[na][nb]=false; } else { calc(na,ko[nb].first); calc(na,ko[nb].second); if(ko[na].first==-1)map[na][nb]=false; else if((map[ko[na].first][ko[nb].first]&&map[ko[na].second][ko[nb].second])||(map[ko[na].first][ko[nb].second]&&map[ko[na].second][ko[nb].first]))map[na][nb]=true; else map[na][nb]=false; } } void func(int node) { if(ko[node].first!=-1) { func(ko[node].first); func(ko[node].second); } calc(node,0); } typedef pair<int,int>pii; class unionfind { public: int par[128]; void init() { for(int i=0;i<128;i++)par[i]=i; } int find(int a) { if(a==par[a])return a; else return a=find(par[a]); } void unite(int a,int b) { a=find(a); b=find(b); if(a==b)return; par[a]=b; } }; vector<int>zv; void get(int node) { zv.push_back(node); if(ko[node].first!=-1) { get(ko[node].first); get(ko[node].second); } } pii lr[128]; void getlr(int node) { if(ko[node].first==-1) { lr[node]=make_pair(0,1); return; } zv.clear(); get(ko[node].first); vector<int>n1=zv; zv.clear(); get(ko[node].second); vector<int>n2=zv; unionfind uf; uf.init(); vector<int>vec; for(int i=0;i<n1.size();i++)vec.push_back(n1[i]); for(int i=0;i<n2.size();i++)vec.push_back(n2[i]); for(int i=0;i<vec.size();i++)for(int j=0;j<vec.size();j++)if(map[vec[i]][vec[j]])uf.unite(vec[i],vec[j]); //printf("%d:",node); //for(int i=0;i<vec.size();i++)printf("%d ",vec[i]);printf("\n"); int cnt=0; for(int i=0;i<vec.size();i++)if(uf.find(vec[i])==vec[i])cnt++; int fl[128]; fill(fl,fl+128,0); for(int i=0;i<n1.size();i++)fl[uf.find(n1[i])]|=1; for(int i=0;i<n2.size();i++)fl[uf.find(n2[i])]|=2; int c2=0; for(int i=0;i<128;i++)if(fl[i]==3)c2++; lr[node]=make_pair(c2,cnt); } int comp(int na,int nb) { pii za=lr[na],zb=lr[nb]; if(za.first*zb.second<zb.first*za.second)return 1; if(za.first*zb.second>zb.first*za.second)return -1; if(ko[na].first==-1)return 0; int z=comp(ko[na].first,ko[nb].first); if(z!=0)return z; return comp(ko[na].second,ko[nb].second); } void solve(int node) { if(ko[node].first==-1) { getlr(node); return; } solve(ko[node].first); solve(ko[node].second); getlr(node); int l=ko[node].first,r=ko[node].second; int t=comp(l,r); if(t==-1)swap(ko[node].first,ko[node].second); } string ans; void make(int node,int t) { if(ko[node].first==-1)ans.push_back('x'); else { ans.push_back('('); if(t==0)make(ko[node].first,0); else make(ko[node].second,0); ans.push_back(' '); if(t==0)make(ko[node].second,1); else make(ko[node].first,1); ans.push_back(')'); } } int main() { for(;;) { str.clear(); pt=vpt=0; for(;;) { char zan; scanf("%c",&zan); if(zan=='\n')break; if(zan=='0')return 0; str.push_back(zan); } fill(ko,ko+128,make_pair(-1,-1)); dfs(); func(0);/* for(int i=0;i<vpt+1;i++) { for(int j=0;j<vpt+1;j++) { if(map[i][j])printf("1 "); else printf("0 "); } printf("\n"); }*/ solve(0); //for(int i=0;i<vpt+1;i++)printf("%d/%d\n",lr[i].first,lr[i].second); ans.clear(); make(0,0); cout<<ans<<endl; } }
筋肉が足りてない。こういうのがぱぱっと実装できるようになれば強いんだけどなぁ。
引き続き埋めていきます。
