「aoj2400～2410」の編集履歴（バックアップ）一覧はこちら

aoj2400～2410 - (2012/07/05 (木) 08:34:14) の１つ前との変更点

追加された行は緑色になります。

削除された行は赤色になります。

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




*2403 The Enemy of My Enemy is My Friend
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2403
どの隣国と同盟を結ぶべきかを問うグラフの問題。
各国は軍事力を持ち隣国とは同盟を結べず同盟を結んだ国の隣国とも同盟を結べない。
この条件下で軍事力の合計が最大になる同盟をした時の値を求める問題。
動的計画法でギリギリアセプト。
これの上位版問題は解けなかったがこれはサイズが小さいのでギリギリ解けた。
３回もタイムリミットくらってしまった。
AOJで４３０問以上解いた現在残りの問題は苦手問題か難しいのばかり。
これからは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
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);
	}
 }

*2401　Equation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2401
等号で結ばれた論理式が与えられるので
３回もタイムリミッドを食らった問題。
もしかして膨大なデータを処理しているのか、そんなに速度が要求されるのかと疑問を持つ？
どうしても合格できないので採点用データを入手してそれを使って解く。
採点結果を検討した結果一回目の投稿時点からアルゴリズムも実装もミスは無いことが判明。
データの読み込み部分にミスがあっただけだった、、、貴重な楽々アセプト問題を無駄にしてしまった。
各変数のtrue falseをsaiki1関数で設定しsaiki関数で再帰下降構文解析で論理式を評価してみた十分な速度が出て上位ランク入りしたので満足。
もっと賢い方法はありそうだが私には思いつかなかった。




 #include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 bool bPerm[12],isOK;
 bool hitSymbols[12];
 int p;
 bool saiki(char com[1002],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[1002],char comR[1002],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 com[1002],comL[1002],comR[1002],c1,c2;
	com[0]='\0';
	scanf("%s",com);
	if(com[0]=='#')return false;
	sscanf(com,"%1001[^=]%c%1001s",comL,&c1,comR);
	isOK=true;
	//printf("<%c><%s>=<%s>",c1,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
どの隣国と同盟を結ぶべきかを問うグラフの問題。
各国は軍事力を持ち隣国とは同盟を結べず同盟を結んだ国の隣国とも同盟を結べない。
この条件下で軍事力の合計が最大になる同盟をした時の値を求める問題。
動的計画法でギリギリアセプト。
これの上位版問題は解けなかったがこれはサイズが小さいのでギリギリ解けた。
３回もタイムリミットくらってしまった。
AOJで４３０問以上解いた現在残りの問題は苦手問題か難しいのばかり。
これからは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
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);
	}
 }