「AOJ41~50」の編集履歴(バックアップ)一覧に戻る

AOJ41~50 - (2011/08/12 (金) 09:09:29) の最新版との変更点

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

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

 *41 Expression
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0041
-難しそうなのでパス。
-丁寧に場合分けしたらいいのだろうか?
+難しそうなのでパスしました。
+どう解いたらいいのかちょっと思いつきません。
 
 
 
 
 ----
 *0042 A Thief
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0042
-典型的なナップザック問題、メモ化探索で計算。
-計算量が小さいのでメモ化も適当。
-メモは大きい方から足しこむことで、同じ荷物を何度も入れることを防いでいる。
-もう少し賢いコードがありそうだけど?
+典型的なナップザック問題です。
+重量制限付きナップザックに荷物を詰め込んで価値を最大化するという問題です。
+
+解法
+動的計画法で解きます。
+この時大きい方から足しこむことで、同じ荷物を何度も入れることを防ぎます。
 
 
  #include<stdio.h>
-void calc(int max,int i){
+ void calc(int max,int i){
 	int memo[1001]={0},n,v,w,tMax,ansV=0,ansW=0;
 	
 	scanf("%d",&n);
 	for(int i=0;i<n;i++){
 		scanf("%d,%d",&v,&w);
 		for(int j=max;j>=w;j--){
 			if((j==w || memo[j-w]>0) && memo[j]<memo[j-w]+v){
 					memo[j]=memo[j-w]+v;
 			}
 		}
 	}
 	for(int i=0;i<=max;i++){
 		if(memo[i]>ansV){
 			ansV=memo[i];
 			ansW=i;
 		}
 	}
 	
 	printf("Case %d:\n",i);
 	printf("%d\n%d\n",ansV,ansW);
-}
-
-int main(){
+ }
+ int main(){
 	int w,i=1;
 	scanf("%d",&w);
 	while(w!=0){
 		calc(w,i);
 		i++;
 		scanf("%d",&w);
 	}
-}
+ }
 
 
 
 
 
 
 
 
 ----
 *0043 Puzzle
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0043
-計算量が小さいので力づくで全探索。
-行列演算で解けそうだけど、どう行列に落とし込めばいいかわからなかったので探索で解いた。
-もう少し賢いコードがありそう。
+数字を組み合わせて指定された役を5つ作るという問題です。
+数字の書かれた13枚のカードに一枚カードを加えて、数字の連番3つか同じ数3つの役を4つ、同じ数2つの役を一つ作ります。
 
- #include<stdio.h>
-bool ans,first;
-int  m[10];
+解法
+計算量も組み合わせ数も小さいので力づくの探索で求めます。
 
-void saiki(int deep){
+
+ #include<stdio.h>
+ bool ans,first;
+ int  m[10];
+ void saiki(int deep){
 	if(deep==4){
 		for(int i=1;i<10;i++){
 			if(m[i]==2){
 				ans=true;
 				break;
 			}
 		}
 		return ;
 	}
 	for(int i=1;i<10;i++){
 		if(m[i]>2){
 			m[i]-=3;
 			saiki(deep+1);
 			m[i]+=3;
 			if(ans==true) return;
 		}
 	}
 	for(int i=1;i<8;i++){
 		if(m[i]>0 && m[i+1]>0 && m[i+2]>0){
 			m[i]--;
 			m[i+1]--;
 			m[i+2]--;
 			saiki(deep+1);
 			m[i]++;
 			m[i+1]++;
 			m[i+2]++;
 			if(ans==true) return;
 		}
 	}
 	
-}
-
-int main(){
+ }
+ int main(){
 	char t[14];
 	
 	while(scanf("%s",t)>0){
 		for(int i=1;i<10;i++)m[i]=0;
 		for(int i=0;i<13;i++)m[t[i]-'0']++;
 		first=true;
 		for(int i=1;i<10;i++){
 			ans=false;
 			if(m[i]<4){
 				m[i]++;
 				saiki(0);
 				m[i]--;
 				if(ans==true){
 					if(first==true){
 						printf("%d",i);
 						first=false;
 					}else{
 						printf(" %d",i);
 					}
 				}
 			}
 		}
 		if(first==true){
 			printf("0");
 		}
 		printf("\n");
 	}
-}
+ }
 
 
 
 
 
 
 
 
 
 ----
 *0044 Prime Number II
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0044
-素数を求めて、setに入れてupper_boundとlower_boundで求めるだけ。
-もしnが50000よりずっと大きな数になったらどうするか考えものの問題。
+ある数nに一番近い二つの素数を求めよという問題。
 
-#include<stdio.h>
-#include<set>
-std::set<int> s;
+解法
+素数の表を求め表をsetに入れて、setからupper_boundとlower_boundするだけで答えがもとまります。
 
-void setSo(){
-	int so[50023]={0};
-	
+
+ #include<stdio.h>
+ #include<set>
+ std::set<int> s;
+ void setSo(){
+	int so[50023]={0};	
 	s.insert(2);
 	for(int i=3;i<50023;i+=2){
 		if(so[i]!=0) continue;
 		s.insert(i);
 		for(int j=i*3;j<50023;j+=i*2){
 			so[j]=1;
 		}
 	}
-}
-
-int main(){
+ }
+ int main(){
 	setSo();
 	int n;
 	while(scanf("%d",&n)>0){
 		printf("%d %d\n",*(--s.lower_bound(n)),*(s.upper_bound(n)));
 	}
-}
+ }
 
 
 
 
 
 
 ----
 *0045 Sum and Average
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0045
-何も考えずに足しこむだけ。
-#include<stdio.h>
-int main(){
+販売単価と販売数量の合計を求めるだけの問題です。
+簡単なので肩慣らしにどうぞ。
+ 
+ #include<stdio.h>
+ int main(){
 	int m,t,s=0,i=0;
 	double c=0;
 	while(scanf("%d,%d",&m,&t)>0){
 		s+=m*t;
 		c+=t;
 		i++;
 	}
 	printf("%d\n%d\n",s,(int)(c/i+0.5));
-}
+ }
 
 
 
 
 
 ----
 *0046 Differential
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0046
-一番大きいのと小さいのをメモして差分をとるだけ。
-#include<stdio.h>
-int main(){
+数字列が与えられるので列の中で一番大きな数字と小さな数字の差を出力してください。
+解法
+一つずつ読みながら一番大きいのと小さいのをメモして差分をとるだけです。
+
+ #include<stdio.h>
+ int main(){
 	double max,min,t;
 	scanf("%lf",&max);
 	min=max;
 	while(scanf("%lf",&t)!=EOF){
 		min=min>t?t:min;
 		max=max<t?t:max;
 	}
 	printf("%lf\n",max-min);
-}
+ }
 
 
 
 
 
 
 
 
 ----
 *0047 Cup Game
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0047
-今ボールのはいってるカップが交換されたらボールの位置を交換するだけ。
-3項演算子?がコード短縮のポイント。
-コードの短さでは結構自信があったのだが、この問題半分の短さのコードで書けるらしい、、、ちょっと想像がつかない。
-70byteとか意味不明すぎる。
+カップゲームの入れ替えをシミュレートして最後にボールのはいってるカップの位置を出力する問題。
+
+解法
+今ボールのはいってるカップが交換されたらボールの位置nを交換するだけです。
+3項演算子?がコード短縮のポイントです。
 
 
  #include <stdio.h>
-int main(void)
-{
+ int main(void)
+ {
 	char n='A',a,b;
 	while(scanf("%c,%c",&a,&b)!=EOF){
 		n=n==a?b:n==b?a:n;
 	}
 	printf("%c\n",n);
-}
+ }
 
 
 
 ----
 *0048 Class
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0048
-簡単な問題なので愚直に実装。
-if文で分岐してもよかったかも。
-体重分岐の部分を?演算子を何個も連ねる解法もあり少し面白い。
+体重データからボクサーの階級を出力する問題です。
+解法
+簡単な問題なので愚直に実装します。
 
-#include<stdio.h>
-#include<map>
-#include<string>
 
-int main(){
+ #include<stdio.h>
+ #include<map>
+ #include<string>
+ int main(){
 	std::map<double,std::string> c;
 	std::map<double,std::string>::iterator it;
 	c[48.0]="fly";
 	c[51.0]="bantam";
 	c[54.0]="feather";
 	c[57.0]="light";
 	c[60.0]="light welter";
 	c[64.0]="welter";
 	c[69.0]="light middle";
 	c[75.0]="middle";
 	c[81.0]="light heavy";
 	double w;
 	while(scanf("%lf",&w)!=EOF){
 		if(w<=48.0){
 			printf("light fly\n");
 		}else if(w>91.0){
 			printf("heavy\n");
 		}else{
 			it=c.lower_bound(w);
 			if(c.begin()!=it) it--;
 			printf("%s\n",(*it).second.c_str());
 		}
 	}
-}
+ }
 
 
 
 
 
 
 
 ----
 *0049 Blood Groups
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0049
-簡単な問題なので一番楽な方法で実装。
-もう少しコード削れたかな?
+生徒の血液型のデータが与えられる。
+どの血液型が何人いるか出力せよという問題。
+解法
+簡単なのでそのまま実装。
 
-#include<stdio.h>
-#include<map>
-#include<string>
 
-int main(){
+ #include<stdio.h>
+ #include<map>
+ #include<string>
+ int main(){
 	std::map<std::string,int> memo;
 	int s;
 	char d[3];
 	memo["A"]=memo["B"]=memo["AB"]=memo["O"]=0;
 	while(scanf("%d,%s",&s,d)!=EOF){
 		memo[d]++;
 	}
 	printf("%d\n%d\n%d\n%d\n",memo["A"],memo["B"],memo["AB"],memo["O"]);
-}
+ }
 
 
 
 
 
 ----
 *0050 Apple and Peach
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0050
-文字数が同じことを利用して手抜き実装、適当です。
+文字列の中のAppleをPeachにPeachをAppleに置き換える問題。
+解法
+文字列型の基本機能を使いこなすだけです。
 
-#include <iostream>
-#include<string>
-int main(){
+ #include <iostream>
+ #include<string>
+ int main(){
 	std::string s;
 	std::string t;
 	getline(std::cin,s);
 	int len=s.size();
 	for(int i=0;i<len-4;i++){
 		if(s[i]=='a' || s[i]=='p'){
 			t=s.substr(i,5);
 			if(t=="apple"){
 				s.replace(i,5,"peach");
 			}else if(t=="peach"){
 				s.replace(i,5,"apple");
 			}
 		}
 	}
 	std::cout<<s;
-}
+ }