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

aoj2400~2410 - (2012/07/04 (水) 14:28:33) の編集履歴(バックアップ)


2401 Equation

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2401
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


なにやら知らないうちに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);
}
}