*2401 Equation http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2401 saiki1関数でa～ｋまでのtrue falseの全組み合わせを設定してその値で等号が成り立つかsaiki関数で再帰下降構文解析で両辺の式を評価しています。 恥ずかしいことに３連続でタイムリミッドの不正解を食らってしまいました。 左辺と右辺を式変形して同じになるか試した方がよいのでしょうか？ #include<stdio.h> bool bPerm[12],isOK; bool hitSymbols[12]; int p; bool saiki(char com[1001],bool modeRe,int deep){ bool b; char s; while(com[p]!='\0'){ s=com[p]; if(s=='\0')break; p++; if('a'<=s&&s<='k'){ b=bPerm[s-'a']; }else if(s=='T'){ b=true; }else if(s=='F'){ b=false; }else if(s=='*'){ b=saiki(com,true,deep+1)&&b; }else if(s=='+'){ b=saiki(com,true,deep+1)||b; }else if(s=='-'&&com[p]=='>'){ p++; b=(saiki(com,true,deep+1)==false&&b==true)?false:true; }else if(s=='-'){ b=!saiki(com,true,deep+1); }else if(s=='('){ b=saiki(com,false,deep+1); }else if(s==')'){ return b; } //printf("(%s %c %d)",b?"t":"f",s,deep); if(modeRe==true){ return b; } } return b; } void saiki1(char comL[1001],char comR[1001],int deep){ if(deep==11){ p=0; bool b1=saiki(comL,false,0); p=0; //printf("\n\n"); bool b2=saiki(comR,false,0); //printf("<%s %s>\n",b1?"t":"f",b2?"t":"f"); if(b1!=b2)isOK=false; //isOK=false; }else{ bPerm[deep]=true; if(isOK==false)return; saiki1(comL,comR,deep+1); if(isOK==false)return; if(hitSymbols[deep]==false)return; bPerm[deep]=false; saiki1(comL,comR,deep+1); } } bool calc(){ char comL[1001],comR[1001],c1,c2; scanf("%[^=#]%c",comL,&c1); if(c1=='#')return false; scanf("%s%c",comR,&c2); isOK=true; //printf("<%s>=<%s>",comL,comR); //出現文字の種類を網羅する for(int i=0;i<12;i++)hitSymbols[i]=false; for(int i=0;comL[i]!='\0';i++){ char c=comL[i]; if('a'<=c&&c<='k'){ hitSymbols[c-'a']=true; } } for(int i=0;comR[i]!='\0';i++){ char c=comR[i]; if('a'<=c&&c<='k'){ hitSymbols[c-'a']=true; } } saiki1(comL,comR,0); printf("%s\n",isOK==true?"YES":"NO"); return true; } int main(){ while(calc()); } *2400 You Are the Judge http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2400 なにやら知らないうちに２４００番台の問題が追加されていた。 もちろん記念すべき１問目は伝統にのっとり肩慣らしの簡単問題である。 こんな簡単な問題でコード実行速度差が出てくるというのが何とも不思議である。 どうやったらこの問題を遅く実行できるのか想像がつかない。 #include <stdio.h> #include <algorithm> #include <vector> struct team{ int a,b[11],no,p;//正答数、誤答数 bool operator<(const team& t)const{ if(a!=t.a)return a>t.a; if(p!=t.p)return p<t.p; return no<t.no; } team(){ for(int i=0;i<11;i++)b[i]=0; a=p=0; } }; void calc(int t,int p,int r){ std::vector<team> teams; team t1; for(int i=0;i<t;i++){ t1.no=i+1; teams.push_back(t1); } int tID,pID,time; char com[20]; for(int i=0;i<r;i++){ scanf("%d %d %d %s",&tID,&pID,&time,com); tID--; if(com[0]=='C'){ teams[tID].a++; teams[tID].p+=1200*teams[tID].b[pID]+time; }else{ teams[tID].b[pID]++; } } std::sort(teams.begin(),teams.end()); for(int i=0;i<t;i++){ printf("%d %d %d\n",teams[i].no,teams[i].a,teams[i].p); } } int main(){ int t,p,r; while(1){ scanf("%d %d %d",&t,&p,&r); if(t==0&&p==0&&r==0)break; calc(t,p,r); } }
