「aoj2400~2410」の編集履歴(バックアップ)一覧に戻る

aoj2400~2410 - (2012/07/04 (水) 14:33:16) のソース

*2401 Equation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2401
saiki1関数でa~kまでのtrue falseの全組み合わせを設定してその値で等号が成り立つかsaiki関数で再帰下降構文解析で両辺の式を評価しています。
恥ずかしいことに3連続でタイムリミッドの不正解を食らってしまいました。

左辺と右辺を式変形して同じになるか試した方がよいのでしょうか?




 #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

なにやら知らないうちに2400番台の問題が追加されていた。
もちろん記念すべき1問目は伝統にのっとり肩慣らしの簡単問題である。
こんな簡単な問題でコード実行速度差が出てくるというのが何とも不思議である。
どうやったらこの問題を遅く実行できるのか想像がつかない。


 #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);
	}
 }