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

aoj2400～2410 - (2012/07/27 (金) 19:44:49) の１つ前との変更点

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

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

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





*2408　Social
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2408
兎がボートにわかれて乗ったのだが仲の悪い組み合わせがある。
同じボートに中の悪い組み合わせが乗っていると不満を持つが何匹の兎が不満を持つか答える問題。

皆この問題が追加されたことにまだ気づいてないのか、ほとんどだれも来ていない。
新雪の上を歩くような気分でとりあえずコードの短さ１位をゲット。
すぐに抜かれるんだろうなあ。
簡単すぎる問題なので特に解法もなし。


 #include<stdio.h>
 #include<string.h>
 int main(){
	int n,k,m,b,no[51],p,q,r;//no[i]はi番目の兎が乗ってるボートの番号
	bool outs[51];
	memset(outs,false,sizeof(outs));
	scanf("%d %d",&n,&k);
	for(int i=0;i<k;i++){
		scanf("%d",&m);
		while(m--){
			scanf("%d",&b);
			no[b]=i;
		}
	}
	scanf("%d",&r);
	while(r--){
		scanf("%d %d",&p,&q);
		if(no[p]==no[q]){
			outs[p]=outs[q]=true;//同じ船に乗っていた
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans+=outs[i];
	}
	printf("%d\n",ans);
 }

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





*2408　Social
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2408
兎がボートにわかれて乗ったのだが仲の悪い組み合わせがある。
同じボートに中の悪い組み合わせが乗っていると不満を持つが何匹の兎が不満を持つか答える問題。

皆この問題が追加されたことにまだ気づいてないのか、ほとんどだれも来ていない。
新雪の上を歩くような気分でとりあえずコードの短さ１位をゲット。
すぐに抜かれるんだろうなあ。
簡単すぎる問題なので特に解法もなし。


 #include<stdio.h>
 #include<string.h>
 int main(){
	int n,k,m,b,no[51],p,q,r;//no[i]はi番目の兎が乗ってるボートの番号
	bool outs[51];
	memset(outs,false,sizeof(outs));
	scanf("%d %d",&n,&k);
	for(int i=0;i<k;i++){
		scanf("%d",&m);
		while(m--){
			scanf("%d",&b);
			no[b]=i;
		}
	}
	scanf("%d",&r);
	while(r--){
		scanf("%d %d",&p,&q);
		if(no[p]==no[q]){
			outs[p]=outs[q]=true;//同じ船に乗っていた
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans+=outs[i];
	}
	printf("%d\n",ans);
 }




*2409　Power