「1221～1230」の編集履歴（バックアップ）一覧に戻る

1221～1230 - (2012/07/01 (日) 15:45:56) のソース

*1222　Telescope
円周上に散らばったｎ個の点を繋げ合わせてｍ角形を作るとき面積が最大になるｍ角形の面積を求めよ。
という問題。
スタート地点を決めて反時計回りに点を決めていくだけである。
反時計回りにｒ点目でｋ点使ってるという集合の中で一番面積が多い組だけ残せば後は動的計画法となる。
もっと賢い方法を思いついたが実装に時間がかかりそうなので断念。




 #include<stdio.h>
 #include<math.h>
 #include <string.h>
 #include <algorithm>
 double calc(double points[41],int startPoint,int size,int selectSize){
	//スタートポイントを決めて動的計画法を適用する
	double memo[41][41];
	double pCopy[41];
	//計算を楽にするために円盤をスタート地点に回転させる。
	//計算誤差なんてないさ、誤差なんて嘘さ。
	//おどけたコボラーが見間違えたのさ。
	//だけどちょっとだけどちょっと引き算の誤差が怖いな、、、
	for(int i=0;i<size;i++){
		int p=(i+startPoint)%size;
		if(startPoint<=p){
			pCopy[i]=2*M_PI*(points[p]-points[startPoint]);
		}else{
			pCopy[i]=2*M_PI*(1.0-(points[startPoint]-points[p]));
		}
		//printf("%lf ",pCopy[i]);
	}
	//printf("\n");
	for(int i=0;i<=size;i++){
		for(int j=0;j<=size;j++){
			memo[i][j]=-1;
		}
	}
	pCopy[size]=2*M_PI;//終わりを番兵代わりに追加
	memo[0][0]=0;//1点目	
	double r1,s1,s2;
	for(int i=0;i<=selectSize;i++){
		//点の数iだけ実行
		//printf("\n%d",i);
		for(int j=0;j<size;j++){
			//円の中心をOとして三角形OJKを追加した場合を計算する
			s1=memo[i][j];
			if(s1==-1.0)continue;
			for(int k=j+1;k<=size;k++){
				r1=pCopy[k]-pCopy[j];
				s2=sin(r1)*0.5+s1;
				//printf("(%d %d %lf)",j,k,s2);
				memo[i+1][k]=std::max(memo[i+1][k],s2);
			}
		}
	}
	return memo[selectSize][size];
 }
 void setData(int n,int m){
	double points[41];
	for(int i=0;i<n;i++){
		scanf("%lf",&points[i]);
	}
	double ans=0;
	for(int i=0;i<n;i++){
		ans=std::max(ans,calc(points,i,n,m));
	}
	printf("%lf\n",ans);
 }
 int main(){
	int n,m;
	while(1){
		scanf("%d %d",&n,&m);
		if(n==0&&m==0)break;
		setData(n,m);
	}
 }


*1227 77377
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1227
文字列を数字で符号化した時、何通りの復号化が出来るかを答える問題。
この程度の問題なら楽々解けるようになった今日この頃。
ブラインドタッチほとんどよどみなく文字を打って一発合格。
ショートコードを狙ったわけでもないけどコードの短さ2位を達成。
文字を数文字削れば一位が狙える。


 #include<stdio.h>
 #include<iostream>
 #include<string>
 #include<vector>
 std::vector<std::string> words,noWords;
 std::string text,ans;
 void saiki(unsigned int p,std::string temp){
	if(p==text.size()){
		std::cout<<temp<<".\n";
	}else {
		std::string str,str2;
		for(unsigned int i=0;i<words.size();i++){
			str =words[i];
			str2=noWords[i];
			if(text.find(str2,p)==p){
				saiki(p+str.size(),temp+(p==0?"":" ")+str);
			}
		}
	}
 }
 int main(){
	char textToNo[30]="22233344455566677778889999";
	std::string str;
	int n;
	while(scanf("%d",&n)){
		if(n==0)break;
		words.clear();
		noWords.clear();
		for(int i=0;i<n;i++){
			std::cin>>str;
			text=str;
			for(unsigned int j=0;j<str.size();j++){
				text[j]=textToNo[str[j]-'a'];
			}
			words.push_back(str);
			noWords.push_back(text);
		}
		std::cin>>text;
		saiki(0,"");
		std::cout<<"--\n";
	}
 }