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

aoj2400~2410 - (2012/07/04 (水) 17:41:52) の編集履歴(バックアップ)


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




2403 The Enemy of My Enemy is My Friend

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2403
動的計画法でギリギリアセプト。
これの上位版の別の問題は解けなかったがこれはサイズが小さいのでギリギリ解けた。
3回もタイムリミットくらったし,AOJで430問以上解いた現在残りの問題は苦手問題か難しいのばかり。
これからはWAやタイムリミットがどんどん増えるのは目に見えている。
成績はどんどん落ちていくだろう。
AOJでの自分の未来を考えると暗澹としてします。
この問題の賢い動的計画法ってなんだろう?
ビット演算で隣国を表現し、一国ずつ同盟に入れる入れないを選択。
残りの国で同盟を結べなくなった国のリストを基準に動的計画法(memo)に放り込んで解いた。
ビット演算でごまかしてるだけでアルゴリズム面は最低である。
やはり実質中卒の私はこのへんの問題が限界なのだろうか?
最近自分の限界を感じてばかりいる、、、

#include<stdio.h>
#include<map>
#include<string>
#include<iostream>
#include<vector>
#include<queue>
#define v std::vector
#define llmap std::map<long long int,int>
int calc(long long int f,v<long long int> cons,int n,int Bs[42]){
llmap memo[2];
long long int one=1;	
//まずはどこの国とも連結してない国と同盟を結ぶ
for(long long int i=1;i<n;i++){
	//printf("(%lld %lld)",cons[i],(long long int)1<<i);
	if(cons[i]==(one<<i)){
		f|=(one<<i);
		Bs[0]+=Bs[i];
	}
}
memo[0][f]=Bs[0];
llmap::iterator it;
long long int ans=Bs[0],nextP,p,no,mask=0;
int nextB;
for(int i=0;i<=n;i++)mask|=(one<<i);	
for(int i=1;i<n;i++){
	no=(one<<i);
	int now =(i+1)%2;
	int next=i%2;
	memo[next].clear();
	mask=(mask<<1);
	for(it=memo[now].begin();it!=memo[now].end();it++){
		p=((*it).first&mask);
		nextB=(*it).second;
		if(memo[next].find(p)==memo[next].end()){
			memo[next][p]=nextB;
		}else if(memo[next][p]<nextB){
			memo[next][p]=nextB;
		}
		if((p&no)==0){
			nextP=(p|cons[i])&mask;
			nextB+=Bs[i];
			if(memo[next].find(nextP)==memo[next].end()){
				memo[next][nextP]=nextB;
			}else if(memo[next][nextP]<nextB){
				memo[next][nextP]=nextB;
			}
		}
		
		
		ans=ans>nextB?ans:nextB;
	}
}
printf("%d\n",ans);
}
void setData(int n){
std::string A,D;
int B,C;
std::map<std::string,int> nameToNo;
v<std::string> conNames[42];
v<long long int> cons;//つながりを40ビットで表す
int Bs[42];	
for(int i=0;i<n;i++){
	std::cin>>A>>Bs[i]>>C;
	nameToNo[A]=i;
	for(int j=0;j<C;j++){
		std::cin>>D;
		conNames[i].push_back(D);
	}
}
long long int one=1;
for(long long int i=0;i<n;i++){
	cons.push_back(0);
	cons[i]=(one<<i);//自国
	for(int j=0;j<conNames[i].size();j++){
		//printf("(%d)",nameToNo[conNames[i][j]]);
		cons[i]|=(one<<nameToNo[conNames[i][j]]);
	}
	//printf("%lld\n",cons[i]);
}
calc(cons[0],cons,n,Bs);
}
int main(){
int n;
while(1){
	scanf("%d",&n);
	if(n==0)break;
	setData(n);
}
}










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