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

「AOJ1081～1090」(2013/02/14 (木) 23:16:51) の最新版変更点

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

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

*1082　http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1082
特殊なルールで変換される携帯電話の変換結果候補の組み合わせ数を求める問題。

解法
トライアンドエラーで解いた問題。
連続した数字の長さがｎ文字だとして、ｎ-1文字目までの組み合わせからｎ文字目の組み合わせをボトムアップで求めることが出来ます。
n-1文字の末尾がイになる組み合わせだったら次はウになる組み合わせかアになる組み合わせにしか分岐しません。
memo[n][1](1は1文字のア)かmemo[n][3]に足されます。
ここまでは当たり前にできたのですが。
なんでn%5==1とn%3==1の時だけ１を足さないといけないのか理由が分かりません。
直感的にn%5==1になるとき+１が必要なのではと理由もわからず思いつき試してみたらうまくいきました。



 #include<stdio.h>
 #include<iostream>
 #include<string.h>
 
 long long int memo5[100001][6];
 long long int memo3[100001][4];
 long long int perm5[100001],perm3[100001];
 long long int mod=100000007;
 int main(){
 	memset(memo5,0,sizeof(memo5));
 	memset(memo3,0,sizeof(memo3));
 	memo5[1][1]=1;
 	memo3[1][1]=1;
 	perm5[1]=perm3[1]=1;
 	for(int n=2;n<=100000;n++){
 		int i=n-1;
 		memo5[n][1]=(memo5[i][1]+memo5[i][2]+memo5[i][3]+memo5[i][4]+memo5[i][5]+(n%5==1))%mod;
 		memo5[n][2]=memo5[i][1];
 		memo5[n][3]=memo5[i][2];
 		memo5[n][4]=memo5[i][3];
 		memo5[n][5]=memo5[i][4];
 		perm5[n]=(memo5[n][1]+memo5[n][2]+memo5[n][3]+memo5[n][4]+memo5[n][5])%mod;
 		
 		memo3[n][1]=(memo3[i][1]+memo3[i][2]+memo3[i][3]+(n%3==1))%mod;
 		memo3[n][2]=memo3[i][1];
  		memo3[n][3]=memo3[i][2];
 		perm3[n]=(memo3[n][1]+memo3[n][2]+memo3[n][3])%mod;
 	}
 	
 	char text[100001];
 	while(1){
 		scanf("%s",text);
 		if(text[0]=='#')break;
 		int count=0;
 		char c=text[0];
 		long long int ans=1;
 		for(int i=0;i<strlen(text)+1;i++){
 			if(text[i]==c){
 				count++;
 			}else{
 				if(c=='8'||c=='0')ans=(ans*perm3[count])%mod;
 				else ans=(ans*perm5[count])%mod;
 				c=text[i];
 				count=1;
 			}
 			
 		}
 		std::cout<<ans<<"\n";
 	}
 }





*1084　
数字を並べたカードを入れ替えて連続した数の掛け算を行うとき最大の数を求める問題。

仮説
この問題はある２枚のカードを入れ替えるというよりも、注目しているｋ枚の範囲のカードのうち一番小さいカードを、ｋ枚の外側にある一番大きなカードと入れ替えたらどうなるかという点に注目して解く。
問題はカードの入れ替えを何度も行ってもよいらしいということです。
つまり途中までカードの得点を下げて最後に一気に成績点を上げる可能性が残されています。





*1085　Spellcasters
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1085
魔法使いがペアを組んで戦うとき相手に勝てるペアの組み方がいくらあるかを求める問題。

各魔法使いについて自分とペアを組める人の最低値を二分探索で探すだけです。
後はそれより大きな人とは必ずペアが組めるので足しこめば計算終了です。


 #include<stdio.h>
 #include<algorithm>
 #include<vector>
 struct wiz{
	int no,r;
	bool operator<(const wiz& w)const{
		return r<w.r;
	}
 };
 void calc(int n,int s){
	std::vector<wiz> vs;
	std::vector<wiz>::iterator it;
	int r;
	wiz w;
	for(int i=0;i<n;i++){
		scanf("%d",&r);
		w.r=r;
		vs.push_back(w);
	}
	std::sort(vs.begin(),vs.end());
	for(int i=0;i<n;i++)vs[i].no=i;
	int ans=0,m;
	for(int i=0;i<n-1;i++){
		w.r=s-vs[i].r;
		it=std::upper_bound(vs.begin(),vs.end(),w);
		if(it==vs.end())continue;
		m=std::max((*it).no,i);
		if(i==m)m++;//自分自身とはペアは組めないのでひいておく
		ans+=n-m;
	}
	
	printf("%d\n",ans);
 }
 int main(){
	int n,s;
	while(1){
		scanf("%d %d",&n,&s);
		if(n==0&&s==0)break;
		calc(n,s);
	}
 }




*1086　Live Schedule
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1086
ツアーのスケジュールデータから利益を最大化するツアー計画を立てた時の最大利益を求める問題。

日数、連続公演の数、疲労度を基準にした動的計画法で合格。
暑い、、夏バテ、アイスがないなら死んでるな。



 #include<stdio.h>
 #include<string.h>
 #include<algorithm>
 int memo[32][7][52];//日数、連続公演の数、疲労度
 void setData(int c,int d,int w,int x){	
	int Es[32][32];//売り上げ[地域の数][日数]
	int Fs[32][32];//疲労度[地域の数][日数]
	memset(memo,-1,sizeof(memo));
	//収益の読み込み
	for(int i=0;i<c;i++){
		for(int j=0;j<d;j++){
			scanf("%d",&Es[i][j]);
		}
	}
	//疲労度の読み込み
	for(int i=0;i<c;i++){
		for(int j=0;j<d;j++){
			scanf("%d",&Fs[i][j]);
		}
	}
	//日数、連続公演回数、疲労度を基準に動的計画法を適用する
	int ans=0,sumE,sumF;
	memo[0][0][0]=0;
	for(int i=0;i<d;i++){
		for(int j=0;j<=x;j++){
			for(int k=0;k<=w;k++){
				//日数、連続公演回数、疲労度のループ
				if(memo[i][j][k]==-1)continue;
				memo[i+1][j][k]=std::max(memo[i][j][k],memo[i+1][j][k]);//この日は公演を行わない
				ans=std::max(memo[i+1][j][k],ans);
				for(int l=0;l<c;l++){
					sumE=memo[i][j][k];
					sumF=k;
					for(int m=l;m>=0;m--){
						if(Es[m][i]==0)break;
						sumE+=Es[m][i];
						sumF+=Fs[m][i];
						if(w<sumF)break;
						int add=(m!=l?1:0);
						if(add==1&&x==j)break;
						memo[i+1][j+add][sumF]=std::max(sumE,memo[i+1][j+add][sumF]);
						ans=std::max(memo[i+1][j+add][sumF],ans);
					}
				}
			}
		}
	}
	for(int j=0;j<=x;j++){
		for(int k=0;k<=w;k++){
			ans=std::max(memo[d][j][k],ans);
		}
	}
	printf("%d\n",ans);
 }
 int main(){
	int c,d,w,x;
	while(1){
		scanf("%d %d %d %d",&c,&d,&w,&x);
		if(c==0&&d==0&&w==0&&x==0)break;
		setData(c,d,w,x);
	}
 }

*1082　http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1082
特殊なルールで変換される携帯電話の変換結果候補の組み合わせ数を求める問題。

解法
トライアンドエラーで解いた問題。
連続した数字の長さがｎ文字だとして、ｎ-1文字目までの組み合わせからｎ文字目の組み合わせをボトムアップで求めることが出来ます。
n-1文字の末尾がイになる組み合わせだったら次はウになる組み合わせかアになる組み合わせにしか分岐しません。
memo[n][1](1は1文字のア)かmemo[n][3]に足されます。
ここまでは当たり前にできたのですが。
なんでn%5==1とn%3==1の時だけ１を足さないといけないのか理由が分かりません。
直感的にn%5==1になるとき+１が必要なのではと理由もわからず思いつき試してみたらうまくいきました。



 #include<stdio.h>
 #include<iostream>
 #include<string.h>
 
 long long int memo5[100001][6];
 long long int memo3[100001][4];
 long long int perm5[100001],perm3[100001];
 long long int mod=100000007;
 int main(){
 	memset(memo5,0,sizeof(memo5));
 	memset(memo3,0,sizeof(memo3));
 	memo5[1][1]=1;
 	memo3[1][1]=1;
 	perm5[1]=perm3[1]=1;
 	for(int n=2;n<=100000;n++){
 		int i=n-1;
 		memo5[n][1]=(memo5[i][1]+memo5[i][2]+memo5[i][3]+memo5[i][4]+memo5[i][5]+(n%5==1))%mod;
 		memo5[n][2]=memo5[i][1];
 		memo5[n][3]=memo5[i][2];
 		memo5[n][4]=memo5[i][3];
 		memo5[n][5]=memo5[i][4];
 		perm5[n]=(memo5[n][1]+memo5[n][2]+memo5[n][3]+memo5[n][4]+memo5[n][5])%mod;
 		
 		memo3[n][1]=(memo3[i][1]+memo3[i][2]+memo3[i][3]+(n%3==1))%mod;
 		memo3[n][2]=memo3[i][1];
  		memo3[n][3]=memo3[i][2];
 		perm3[n]=(memo3[n][1]+memo3[n][2]+memo3[n][3])%mod;
 	}
 	
 	char text[100001];
 	while(1){
 		scanf("%s",text);
 		if(text[0]=='#')break;
 		int count=0;
 		char c=text[0];
 		long long int ans=1;
 		for(int i=0;i<strlen(text)+1;i++){
 			if(text[i]==c){
 				count++;
 			}else{
 				if(c=='8'||c=='0')ans=(ans*perm3[count])%mod;
 				else ans=(ans*perm5[count])%mod;
 				c=text[i];
 				count=1;
 			}
 			
 		}
 		std::cout<<ans<<"\n";
 	}
 }





*1084　
数字を並べたカードを入れ替えて連続した数の掛け算を行うとき最大の数を求める問題。

仮説
この問題はある２枚のカードを入れ替えるというよりも、注目しているｋ枚の範囲のカードのうち一番小さいカードを、ｋ枚の外側にある一番大きなカードと入れ替えたらどうなるかという点に注目して解く。
問題はカードの入れ替えを何度も行ってもよいらしいということです。
つまり途中までカードの得点を下げて最後に一気に成績点を上げる可能性が残されています。





*1085　Spellcasters
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1085
魔法使いがペアを組んで戦うとき相手に勝てるペアの組み方がいくらあるかを求める問題。

各魔法使いについて自分とペアを組める人の最低値を二分探索で探すだけです。
後はそれより大きな人とは必ずペアが組めるので足しこめば計算終了です。


 #include<stdio.h>
 #include<algorithm>
 #include<vector>
 struct wiz{
	int no,r;
	bool operator<(const wiz& w)const{
		return r<w.r;
	}
 };
 void calc(int n,int s){
	std::vector<wiz> vs;
	std::vector<wiz>::iterator it;
	int r;
	wiz w;
	for(int i=0;i<n;i++){
		scanf("%d",&r);
		w.r=r;
		vs.push_back(w);
	}
	std::sort(vs.begin(),vs.end());
	for(int i=0;i<n;i++)vs[i].no=i;
	int ans=0,m;
	for(int i=0;i<n-1;i++){
		w.r=s-vs[i].r;
		it=std::upper_bound(vs.begin(),vs.end(),w);
		if(it==vs.end())continue;
		m=std::max((*it).no,i);
		if(i==m)m++;//自分自身とはペアは組めないのでひいておく
		ans+=n-m;
	}
	
	printf("%d\n",ans);
 }
 int main(){
	int n,s;
	while(1){
		scanf("%d %d",&n,&s);
		if(n==0&&s==0)break;
		calc(n,s);
	}
 }




*1086　Live Schedule
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1086
ツアーのスケジュールデータから利益を最大化するツアー計画を立てた時の最大利益を求める問題。

日数、連続公演の数、疲労度を基準にした動的計画法で合格。
暑い、、夏バテ、アイスがないなら死んでるな。



 #include<stdio.h>
 #include<string.h>
 #include<algorithm>
 int memo[32][7][52];//日数、連続公演の数、疲労度
 void setData(int c,int d,int w,int x){	
	int Es[32][32];//売り上げ[地域の数][日数]
	int Fs[32][32];//疲労度[地域の数][日数]
	memset(memo,-1,sizeof(memo));
	//収益の読み込み
	for(int i=0;i<c;i++){
		for(int j=0;j<d;j++){
			scanf("%d",&Es[i][j]);
		}
	}
	//疲労度の読み込み
	for(int i=0;i<c;i++){
		for(int j=0;j<d;j++){
			scanf("%d",&Fs[i][j]);
		}
	}
	//日数、連続公演回数、疲労度を基準に動的計画法を適用する
	int ans=0,sumE,sumF;
	memo[0][0][0]=0;
	for(int i=0;i<d;i++){
		for(int j=0;j<=x;j++){
			for(int k=0;k<=w;k++){
				//日数、連続公演回数、疲労度のループ
				if(memo[i][j][k]==-1)continue;
				memo[i+1][j][k]=std::max(memo[i][j][k],memo[i+1][j][k]);//この日は公演を行わない
				ans=std::max(memo[i+1][j][k],ans);
				for(int l=0;l<c;l++){
					sumE=memo[i][j][k];
					sumF=k;
					for(int m=l;m>=0;m--){
						if(Es[m][i]==0)break;
						sumE+=Es[m][i];
						sumF+=Fs[m][i];
						if(w<sumF)break;
						int add=(m!=l?1:0);
						if(add==1&&x==j)break;
						memo[i+1][j+add][sumF]=std::max(sumE,memo[i+1][j+add][sumF]);
						ans=std::max(memo[i+1][j+add][sumF],ans);
					}
				}
			}
		}
	}
	for(int j=0;j<=x;j++){
		for(int k=0;k<=w;k++){
			ans=std::max(memo[d][j][k],ans);
		}
	}
	printf("%d\n",ans);
 }
 int main(){
	int c,d,w,x;
	while(1){
		scanf("%d %d %d %d",&c,&d,&w,&x);
		if(c==0&&d==0&&w==0&&x==0)break;
		setData(c,d,w,x);
	}
 }









*1087 Dimensional Analysis
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1087
次元量をもつ変数の四則演算が適正なものかどうか判断する問題。

解法
再帰下降構文解析に*と/のオペレータを組み込み、+と-が適切に行われているか試すだけの問題です。
素直に実装します。


 #include<stdio.h>
 #include<string>
 #include<map>
 #include<iostream>
 #include<vector>
 
 struct D{
 	int ds[10];
 	int size;
 	bool isAddOrDellOK(const D& d){
 		for(int i=0;i<size;i++)if(d.ds[i]!=ds[i])return false;
 		return true;
 	}
 	D mult(const D& d){
 		D re;
 		for(int i=0;i<size;i++)re.ds[i]=ds[i]+d.ds[i];
 		re.size=size;
 		return re;
 	}
 	D div(const D& d){
 		D re;
 		for(int i=0;i<size;i++)re.ds[i]=ds[i]-d.ds[i];
 		re.size=size;
 		return re;
 	}
 };
 std::map<std::string,D> deriveds,vds;
 bool isAllOK;
 D saiki(std::string formula,int& p,int pr,int n){
 	D re,a;
 	re.size=a.size=n;
 	while(formula.size()>p){
 		char c=formula[p];
 		if(c=='('){
  			p++;
 			re=saiki(formula,p,0,n);
 			p++;
 		}else if(c==')'){
 			return re;
 		}else if(c=='+' || c=='-'){
 			if(pr>=1){
 				return re;
 			}
 			p++;
 			a=saiki(formula,p,1,n);
 			if(re.isAddOrDellOK(a)==false){
 				isAllOK=false;
 			}
 		}else if(c=='*'){
 			if(pr>=2){
 				return re;
 			}
 			p++;
 			a=saiki(formula,p,2,n);
  			re=re.mult(a);
 		}else if(c=='/'){
 			if(pr>=2){
 				return re;
 			}
 			p++;
 			a=saiki(formula,p,2,n);
 			re=re.div(a);
  		}else{
 			std::string str="";
 			int k=0;
 			while(formula[k+p]!='\0'){
 				str+=formula[k+p];
 				if(vds.find(str)!=vds.end())break;
 				k++;
 			}
 			re=vds[str];
 			p=p+k+1;
 		}
 	}
 	return re;
 }
 
 
 void setData(int n,int m,int p){
 	deriveds.clear();
 	vds.clear();
 	std::string name,dName;
 	isAllOK=true;
 	D d;
 	std::vector<std::string> vec;
 	std::string formula;
 	for(int i=0;i<m;i++){
 		std::cin>>name;
 		d.size=n;
 		for(int i=0;i<n;i++){
 			std::cin>>d.ds[i];
 		}
 		vec.push_back(name);
 		deriveds[name]=d;
 	}
	std::cin>>formula;
 	for(int i=0;i<p;i++){
 		std::cin>>name>>dName;
 		vds[name]=deriveds[dName];
 	}
 	int point=0;
  	D kekka=saiki(formula,point,0,n);
	if(isAllOK==false){
  		//std::cout<<">>>>>>>>>>error\n";
 		//for(int i=0;i<n;i++){
 		//	std::cout<<" "<<kekka.ds[i];
 		//}
 		std::cout<<"error\n";
 	}else{
 		std::string ans="undefined";
 		for(int i=0;i<vec.size();i++){
 			if(kekka.isAddOrDellOK(deriveds[vec[i]])==true){
 				ans=vec[i];
 			}
 		}
  		std::cout<<ans<<"\n";
 		//std::cout<<"\n\n>>>>>>>"<<ans<<"\n>>>>>>>";
 		//for(int i=0;i<n;i++){
 		//	std::cout<<" "<<kekka.ds[i];
 		//}
 		//std::cout<<"\n";
 	}
 }
 
 int main(){
 	int n,m,p;
 	while(1){
 		scanf("%d %d %d",&n,&m,&p);
 		if(n==0&&m==0&&p==0)break;
 		setData(n,m,p);
 	}
 }