*0151 Grid http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0151 升目に01が与えられるので、その中で縦横斜めで最も1が長く連続している場所の長さを答えよという問題。 解法 memoに縦横斜めに分解して計算したら後は動的計画法で解けます。 memoに全部まとめたのでコードがコンパクトになった分少しわかりにくくなったかもしれません。 #include<stdio.h> #include<string.h> char row[258]; int memo[4][2][258];//0横,1上 2左斜め 3右斜め int dxs[]={-1,0,-1,1}; void search(int n){ int y,up,t,ans=0; memset(memo,0,4*2*258*4); for(int i=0;i<n;i++){ scanf("%s",&row[1]); y=i%2; for(int j=0;j<4;j++){ //j=0横,1上 2左斜め 3右斜め up=j==0?y:(y+1)%2; for(int x=1;x<=n;x++){ if(row[x]=='0'){ memo[j][y][x]=0; }else{ t=memo[j][up][x+dxs[j]]+1; ans=t>ans?t:ans; memo[j][y][x]=t; } } } } printf("%d\n",ans); } int main(){ int n; scanf("%d",&n); while(n!=0){ search(n); scanf("%d",&n); } } ---- *0152 Bowling http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0152 ボーリングのピンを倒したデータからその得点を計算し、得点の良い順番に表示するという問題。 解法 計算が少し頻雑です。 ターンごとに結果を追いかけて分岐します。 10ターン目以降とそれ以外で処理を分岐させます。 typeに何投目がストライク、スペア、10本倒せなかったかの結果を記録し,scoreに倒したピン数を記録します。 最後に集計して終わりです。 #include<stdio.h> #include <algorithm> struct menber{ int no,score; bool operator<(const menber m)const{ if(score!=m.score) return score>m.score; return no<m.no; } }; int calc(){ int p=0,turn=1,s,no; bool first=true; int score[22]; int type[22]; score[0]=type[0]=0; char re; while(re!='\n'){ scanf("%d%c",&s,&re); score[p]=s; if(turn>9){ type[p]=0; }else{ if(s==10 && first==true){ type[p]=2; turn++; }else if(first==false && score[p]+score[p-1]==10){ type[p]=1; turn++; first=true; }else{ score[p]=s; type[p]=0; if(first==true){ first=false; }else{ first=true; turn++; } } } p++; } int ans=0; for(int i=0;i<p;i++){ ans+=score[i]; for(int j=1;j<=type[i];j++){ ans+=score[i+j]; } } return ans; } int main(){ int m,no; menber menbers[41]; while(1){ scanf("%d",&m); if(m==0)break; for(int i=0;i<m;i++){ scanf("%d",&menbers[i].no); menbers[i].score=calc(); } std::sort(menbers,menbers+m); for(int i=0;i<m;i++){ printf("%d %d\n",menbers[i].no,menbers[i].score); } } } ---- *0157 Russian Dolls http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0157 マトリョーシカ(ロシアの入れ子人形)の中にできるだけたくさんより小さいマトリョーシカを入れたい。 マトリョーシカのサイズデータが与えられるので最も多く入る組み合わせを求めよという問題。 解法 人形の数も少ないので適当なメモ化探索でも十分計算量が安定します。 実装が楽な深さ優先探索のメモ化で実装してみましたが、より計算量を安定させるならナップザック法的な解き方もあると思います。 #include<stdio.h> #include<map> #include<vector> struct kumi{ int h,r; bool operator<(const kumi k)const{ if(h!=k.h) return h<k.h; return r<k.r; } }; std::map<kumi,int> memo; std::vector<int> hs; std::vector<int> rs; std::vector<bool> oks; int k; int saiki(kumi size,int deep){ if(memo.find(size)!=memo.end()){ return memo[size]+deep; } kumi next; int sum=deep+1,temp; for(int i=0;i<k;i++){ if(oks[i]==true && hs[i]<size.h && rs[i]<size.r){ oks[i]=false; next.h=hs[i]; next.r=rs[i]; temp=saiki(next,deep+1); sum=sum>temp?sum:temp; oks[i]=true; } } memo[size]=sum-deep; return sum; } void setData(int n){ memo.clear(); hs.clear(); rs.clear(); oks.clear(); int h,r; for(int i=0;i<n;i++){ scanf("%d %d",&h,&r); hs.push_back(h); rs.push_back(r); oks.push_back(true); } int m; scanf("%d",&m); for(int i=0;i<m;i++){ scanf("%d %d",&h,&r); hs.push_back(h); rs.push_back(r); oks.push_back(true); } kumi start; int ans=0,temp; k=m+n; for(int i=0;i<k;i++){ start.h=hs[i]; start.r=rs[i]; temp=saiki(start,0); ans=ans>temp?ans:temp; } printf("%d\n",ans); } int main(){ int n; while(1){ scanf("%d",&n); if(n==0) break; setData(n); } } ---- *0158 Collatz's Problem http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0158 コラッツの予想を計算して確かめましょうという問題。 解法 問題の方でアルゴリズムを指定しているのでそのまま実装します。 #include<stdio.h> int main(){ int n,c; while(1){ scanf("%d",&n); if(n==0) break; c=0; while(n!=1){ n=n%2==1?n*3+1:n/2; c++; } printf("%d\n",c); } } ---- *0159 The Best Body http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0159 n人の伸長と体重のデータが与えられるので、BMI値が22に最も近い人を探すという問題。 解法 計算するだけです。 3分で解くことを期待されてるような問題ですので気楽に解きましょう。 現実ではありえませんがBMI値は最悪200/0.0001=200万という値をとることにだけ注意しましょう。 #include<stdio.h> #include<math.h> int main(){ int n,no,ansNo; double h,w,ans,t; while(1){ scanf("%d",&n); ans=9999999; if(n==0)break; while(n--){ scanf("%d %lf %lf",&no,&h,&w); t=fabs(w/(h*h/10000.0)-22.0); if(ans>t){ ans=t; ansNo=no; } } printf("%d\n",ansNo); } } ---- *0160 Delivery Fee http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0160 郵便物の郵便料金を求める問題。 荷物はサイズと重さで郵便料金が変わるのでそれを考慮して郵便料金の総計を出力せよという問題。 解法 指定通りに実装するだけです。 #include <stdio.h> #include <algorithm> int main(){ int x,y,h,w,n,t,sum,s1; int size[6]={60,80,100,120,140,160}; int ws[6] ={2,5,10,15,20,25}; int ps[7] ={600,800,1000,1200,1400,1600,0}; scanf("%d",&n); while(n!=0){ sum=0; for(int i=0;i<n;i++){ t=6; scanf("%d %d %d %d",&x,&y,&h,&w); s1=x+y+h; for(int i=0;i<6;i++){ if(size[i]>=s1 && ws[i]>=w){ t=i; break; } } sum+=ps[t]; } printf("%d\n",sum); scanf("%d",&n); } }