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

「2351～2360」(2013/01/28 (月) 12:07:48) の最新版変更点

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

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

*2360　Sharp 2SAT
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2360
論理式が与えられるのでそれを真にする真偽値の組み合わせを求める問題。
基本的な考え方は考え始めて最初の50分で思いついたものの、実装が大変な問題でした。

基本的な考え方は論理式の連鎖が
(X1,X4)(X4,X2)(X2,X5)(X5,X1)というループか
(X6,X7)(X7,X8),,となる鎖かしかない。
鎖なら鎖を順にたどって組み合わせ数をメモ化で求めていきます。
ループならメモ化のスタート時がtrueだったかfalseだったかを覚えておきながら論理式のチェインでできる組み合わせ数を求め最後にTでおわるＦで終わるものだけを合計する。
というシンプルな発想です。






 #include<stdio.h>
 #include<string.h>
 #include<map>
 #include<math.h>
 #include <stdlib.h>
 std::map<int,int> perm[1003];//問題をグラフとして見て解く[今の番号}、<次の番号,種類>
 std::map<int,int> conCount[1003];
 int count[1003];
 int TT=1,TF=2,FT=4,FF=8;
 long long int mode=1000000007;
 long long int calc(int deep,int s,int no,long long int ttCount,long long int tfCount,long long int ftCount,long long int ffCount){
	std::map<int,int>::iterator it=perm[no].begin();
	count[no]=0;
	long long int tAns=(ttCount+tfCount+ftCount+ffCount)%mode;
	long long int nextTT,nextTF,nextFT,nextFF;	
	while(it!=perm[no].end()){
		int next=(*it).first;
		int p   =(*it).second;
		if(deep==0){
			nextTT=((p&TT)!=0);
			nextTF=((p&TF)!=0);
			nextFT=((p&FT)!=0);
			nextFF=((p&FF)!=0);
			if(conCount[no][next]==2){
				count[next]=0;
				return nextTT+nextTF+nextFT+nextFF;
			}else{
				return calc(deep+1,s,next,nextTT,nextTF,nextFT,nextFF);
			}
		}else if(s==next&&deep>1){
			nextTT=(ttCount*((p&TT)!=0)+tfCount*((p&FT)!=0))%mode;
			nextFF=(ftCount*((p&TF)!=0)+ffCount*((p&FF)!=0))%mode;
			return nextTT+nextFF;
		}else if(count[next]==0){
			it++;
		}else{
			nextTT=(ttCount*((p&TT)!=0)+tfCount*((p&FT)!=0))%mode;
			nextTF=(ttCount*((p&TF)!=0)+tfCount*((p&FF)!=0))%mode;
			nextFT=(ftCount*((p&TT)!=0)+ffCount*((p&FT)!=0))%mode;
			nextFF=(ftCount*((p&TF)!=0)+ffCount*((p&FF)!=0))%mode;
			return calc(deep+1,s,next,nextTT,nextTF,nextFT,nextFF);
		}
	}
	return tAns;
 }
 int main(){
	int n,m,y1,y2,t1,t2;
	long long int ans=1,temp;
	memset(count,0,sizeof(count));	
	scanf("%d %d",&n,&m);
	while(m--){
		scanf("%d %d",&y1,&y2);
		t1=abs(y1);
		t2=abs(y2);
		
		if(y1==y2){
			//一通りしかないので何もしない
		}else if(y1==-y2){
			ans=(ans*2)%mode;
		}else{
			count[t1]++;
			count[t2]++;
			if(conCount[t1].find(t2)==conCount[t1].end()){
				conCount[t1][t2]=1;
			}else{
				conCount[t1][t2]=2;
			}
			if(conCount[t2].find(t1)==conCount[t2].end()){
				conCount[t2][t1]=1;
			}else{
				conCount[t2][t1]=2;
			}
			if(perm[t1].find(t2)==perm[t1].end()){
				perm[t1][t2]=15;
			}
			if(perm[t2].find(t1)==perm[t2].end()){
				perm[t2][t1]=15;
			}
			if(y1<0&&y2<0){
				perm[t1][t2]&=(FF+FT+TF);
				perm[t2][t1]&=(FF+FT+TF);
			}else if(y1>0&&y2<0){
				perm[t1][t2]&=(TT+TF+FF);
				perm[t2][t1]&=(TT+FT+FF);
			}else if(y1<0&&y2>0){
				perm[t1][t2]&=(TT+FT+FF);
				perm[t2][t1]&=(TT+TF+FF);
			}else{
				perm[t1][t2]&=(TT+FT+TF);
				perm[t2][t1]&=(TT+FT+TF);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(count[i]==1){
			temp=calc(0,i,i,0,0,0,0);
			ans=(ans*temp)%mode;
		}
	}
	for(int i=1;i<=n;i++){
		if(count[i]==2){
			temp=calc(0,i,i,0,0,0,0);
			ans=(ans*temp)%mode;
		}
	}
	printf("%lld\n",ans);
 }

*2360　Sharp 2SAT
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2360
論理式が与えられるのでそれを真にする真偽値の組み合わせを求める問題。
基本的な考え方は考え始めて最初の50分で思いついたものの、実装が大変な問題でした。

基本的な考え方は論理式の連鎖が
(X1,X4)(X4,X2)(X2,X5)(X5,X1)というループか
(X6,X7)(X7,X8),,となる鎖かしかない。
鎖なら鎖を順にたどって組み合わせ数をメモ化で求めていきます。
ループならメモ化のスタート時がtrueだったかfalseだったかを覚えておきながら論理式のチェインでできる組み合わせ数を求め最後にTでおわるＦで終わるものだけを合計する。
というシンプルな発想です。






 #include<stdio.h>
 #include<string.h>
 #include<map>
 #include<math.h>
 #include <stdlib.h>
 std::map<int,int> perm[1003];//問題をグラフとして見て解く[今の番号}、<次の番号,種類>
 std::map<int,int> conCount[1003];
 int count[1003];
 int TT=1,TF=2,FT=4,FF=8;
 long long int mode=1000000007;
 long long int calc(int deep,int s,int no,long long int ttCount,long long int tfCount,long long int ftCount,long long int ffCount){
	std::map<int,int>::iterator it=perm[no].begin();
	count[no]=0;
	long long int tAns=(ttCount+tfCount+ftCount+ffCount)%mode;
	long long int nextTT,nextTF,nextFT,nextFF;	
	while(it!=perm[no].end()){
		int next=(*it).first;
		int p   =(*it).second;
		if(deep==0){
			nextTT=((p&TT)!=0);
			nextTF=((p&TF)!=0);
			nextFT=((p&FT)!=0);
			nextFF=((p&FF)!=0);
			if(conCount[no][next]==2){
				count[next]=0;
				return nextTT+nextTF+nextFT+nextFF;
			}else{
				return calc(deep+1,s,next,nextTT,nextTF,nextFT,nextFF);
			}
		}else if(s==next&&deep>1){
			nextTT=(ttCount*((p&TT)!=0)+tfCount*((p&FT)!=0))%mode;
			nextFF=(ftCount*((p&TF)!=0)+ffCount*((p&FF)!=0))%mode;
			return nextTT+nextFF;
		}else if(count[next]==0){
			it++;
		}else{
			nextTT=(ttCount*((p&TT)!=0)+tfCount*((p&FT)!=0))%mode;
			nextTF=(ttCount*((p&TF)!=0)+tfCount*((p&FF)!=0))%mode;
			nextFT=(ftCount*((p&TT)!=0)+ffCount*((p&FT)!=0))%mode;
			nextFF=(ftCount*((p&TF)!=0)+ffCount*((p&FF)!=0))%mode;
			return calc(deep+1,s,next,nextTT,nextTF,nextFT,nextFF);
		}
	}
	return tAns;
 }
 int main(){
	int n,m,y1,y2,t1,t2;
	long long int ans=1,temp;
	memset(count,0,sizeof(count));	
	scanf("%d %d",&n,&m);
	while(m--){
		scanf("%d %d",&y1,&y2);
		t1=abs(y1);
		t2=abs(y2);
		
		if(y1==y2){
			//一通りしかないので何もしない
		}else if(y1==-y2){
			ans=(ans*2)%mode;
		}else{
			count[t1]++;
			count[t2]++;
			if(conCount[t1].find(t2)==conCount[t1].end()){
				conCount[t1][t2]=1;
			}else{
				conCount[t1][t2]=2;
			}
			if(conCount[t2].find(t1)==conCount[t2].end()){
				conCount[t2][t1]=1;
			}else{
				conCount[t2][t1]=2;
			}
			if(perm[t1].find(t2)==perm[t1].end()){
				perm[t1][t2]=15;
			}
			if(perm[t2].find(t1)==perm[t2].end()){
				perm[t2][t1]=15;
			}
			if(y1<0&&y2<0){
				perm[t1][t2]&=(FF+FT+TF);
				perm[t2][t1]&=(FF+FT+TF);
			}else if(y1>0&&y2<0){
				perm[t1][t2]&=(TT+TF+FF);
				perm[t2][t1]&=(TT+FT+FF);
			}else if(y1<0&&y2>0){
				perm[t1][t2]&=(TT+FT+FF);
				perm[t2][t1]&=(TT+TF+FF);
			}else{
				perm[t1][t2]&=(TT+FT+TF);
				perm[t2][t1]&=(TT+FT+TF);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(count[i]==1){
			temp=calc(0,i,i,0,0,0,0);
			ans=(ans*temp)%mode;
		}
	}
	for(int i=1;i<=n;i++){
		if(count[i]==2){
			temp=calc(0,i,i,0,0,0,0);
			ans=(ans*temp)%mode;
		}
	}
	printf("%lld\n",ans);
 }





*2356　Palindromic Anagram
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2356
文字列が与えられるのでその文字列のアナグラムかつ回文になっている文字列の組み合わせ数を求める問題。

解法
高校数学で習った順列組み合わせの公式を適用するだけです。
計算途中で桁あふれが起こるのを防ぐために分母と分子をｇｃｄで既約分数にしてから計算するくらいです。

 #include<stdio.h>
 #include<vector>
 #include<string.h>
 #include<iostream>
 
 long long int gcd (long long int a,long long int b ){
	long long int c;
 	while ( a != 0 ) {
     		c = a; a = b%a;  b = c;
  	}
   	return b;
 } 
 
 int main(){
 	char text[41];
 	int count[30]={0};
 	scanf("%s",text);
 	int len=strlen(text);
 	for(int i=0;i<len;i++)count[text[i]-'a']++;
 	std::vector<int> v;
 	int ki=0;
 	int size=0;
 	for(int i=0;i<30;i++){
 		if(count[i]%2==1){
 			ki++;
 			count[i]--;
 		}
 		if(count[i]>0){
 			size+=count[i]/2;
 			v.push_back(count[i]/2);
 		}
 	}
 	if((ki>0&&len%2==0)||(ki!=1&&len%2==1)||(ki>1)){
 		printf("0\n");
 		return 0;
 	}
 	std::vector<long long int> vUp,vDown;
 	long long int ans=1;
 	for(int i=1;i<=size;i++)vUp.push_back(i);
 	for(int i=0;i<v.size();i++){
 		for(int j=1;j<=v[i];j++)vDown.push_back(j);
 	}
 	
 	for(int i=0;i<vUp.size();i++){
 		for(int j=0;j<vDown.size();j++){
 			long long int g=gcd(vUp[i],vDown[j]);
 			vUp[i]/=g;
 			vDown[j]/=g;
 		}
 	}
 	for(int i=0;i<vUp.size();i++)ans*=vUp[i];
 	std::cout<<ans<<"\n";
 }