「AOJ41~50」の編集履歴(バックアップ)一覧はこちら

AOJ41~50」(2011/08/21 (日) 18:47:03) の最新版変更点

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

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

*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){ 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 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 計算量が小さいので力づくで全探索。 行列演算で解けそうだけど、どう行列に落とし込めばいいかわからなかったので探索で解いた。 もう少し賢いコードがありそう。 #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(){ 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よりずっと大きな数になったらどうするか考えものの問題。 #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(){ 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(){ 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(){ 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とか意味不明すぎる。 #include <stdio.h> 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(){ 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(){ 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 文字数が同じことを利用して手抜き実装、適当です。 #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; }
*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){ 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 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){ 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(){ 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 ある数nに一番近い二つの素数を求めよという問題。 解法 素数の表を求め表をsetに入れて、setからupper_boundとlower_boundするだけで答えがもとまります。 #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(){ 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(){ 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(){ 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 カップゲームの入れ替えをシミュレートして最後にボールのはいってるカップの位置を出力する問題。 解法 今ボールのはいってるカップが交換されたらボールの位置nを交換するだけです。 3項演算子?がコード短縮のポイントです。 #include <stdio.h> 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 体重データからボクサーの階級を出力する問題です。 解法 簡単な問題なので愚直に実装します。 #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(){ 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(){ 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; }

表示オプション

横に並べて表示:
変化行の前後のみ表示: