*0111 Doctor's Memorable Codes http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0111 ひたすら対応表を作るのがめんどくさい問題。 変換表に何か規則があるらしく自動生成ができるようなのだけど？ #include<iostream> #include<map> #include<string> using namespace std; map<char,string> e; map<string,char> d; std::string noToCode(int no){ std::string ans="01234"; for(int i=0;i<5;i++){ ans[4-i]=no%2+'0'; no=no/2; } return ans; } void setMap(){ for(int i=0;i<26;i++){ e['A'+i]=noToCode(i); } e[' '] = "11010"; e['.'] = "11011"; e[','] = "11100"; e['-'] = "11101"; e['\'']= "11110"; e['?'] = "11111"; d["101"] = ' '; d["000000"] = '\''; d["000011"] = ','; d["10010001"] = '-'; d["010001"] = '.'; d["000001"] = '?'; d["100101"] = 'A'; d["10011010"] = 'B'; d["0101"] = 'C'; d["0001"] = 'D'; d["110"] = 'E'; d["01001"] = 'F'; d["10011011"] = 'G'; d["010000"] = 'H'; d["0111"] = 'I'; d["10011000"] = 'J'; d["0110"] = 'K'; d["00100"] = 'L'; d["10011001"] = 'M'; d["10011110"] = 'N'; d["00101"] = 'O'; d["111"] = 'P'; d["10011111"] = 'Q'; d["1000"] = 'R'; d["00110"] = 'S'; d["00111"] = 'T'; d["10011100"] = 'U'; d["10011101"] = 'V'; d["000010"] = 'W'; d["10010010"] = 'X'; d["10010011"] = 'Y'; d["10010000"] = 'Z'; } int main(){ setMap(); string line,put1,ans; int p,k,size; while(getline(cin,line)){ put1=""; for(int i=0;i<line.size();i++){ put1.append(e[line[i]]); } ans=""; p=0; size=put1.size(); while(p<size){ for(int k=3;k<9;k++){ if(p+k>size){ p=size; break; } line=put1.substr(p,k); if(d.find(line)!=d.end()){ ans+=d[line]; p=p+k-1; break; } } p++; } cout<<ans<<"\n"; } } ---- *0112 A Milk Shop http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0112 long long intを使わないとintだとあふれるということにさえ注意すれば中学生でも解ける問題. しかし新鮮ミルクじゃないよなもう。 #include <algorithm> #include <iostream> long long int t[10001]; void calc(int n){ long long int ans=0; for(int i=0;i<n;i++){ std::cin>>t[i]; } std::sort(t,t+n); for(int i=0;i<n;i++){ ans+=t[i]*(n-i-1); } std::cout<<ans<<"\n"; } int main(){ int n; while(1){ scanf("%d",&n); if(n==0)break; calc(n); } } ---- *0113 Period http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0113 うーんなんだか分岐式が冗長になった気がする？ #include<stdio.h> #include<map> void calc(int p,int q){ std::map<int,int> memo; int t,i=0; memo[p]=-1; while(1){ p*=10; t=(p/q)%10; p=p%q; if(p==0){ printf("%d\n",t); return; }else if(memo.find(p)==memo.end()){ printf("%d",t); memo[p]=i; }else{ printf("%d\n",t); break; } i++; } for(q=0;q<=i;q++){ printf("%c",q<=memo[p]?' ':'^'); } printf("\n"); } int main(){ int p,q; while(scanf("%d %d",&p,&q)!=EOF){ calc(p,q); } } ---- *0114 Electro-Fly http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0114 intだと桁あふれが起こるらしいので置き換えで全部long long intにしたら合格できた。 #include <iostream> #include<stdio.h> long long int gcd(long long int a, long long int b) { long long int c; while (b != 0) { c = a % b; a = b; b = c; } return a; } long long int re(long long int x,long long int m){ long long int ans=1,t=x%m; while(t!=1){ t=(t*x)%m; ans++; } return ans; } int main(){ long long int a1,a2,a3,m1,m2,m3,t,n1,n2,n3,c; while(1){ std::cin>>a1>>m1>>a2>>m2>>a3>>m3; if(a1==0) break; n1=re(a1,m1); n2=re(a2,m2); n3=re(a3,m3); c=n1*(n2/gcd(n1,n2)); c=c*(n3/gcd(n3,c)); std::cout<<c<<"\n"; } } ---- *0116 Rectangular Searching http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0116 うーん、漸化式の立て方が分からず線形時間で計算が終わらない方法で解いてしまった。 1行単位 #include<stdio.h> #include<string.h> int map[2][503]; char row[503]; void setMap(int h,int w){ char t; int lp,rp,cp,sum,max=0,up,y; memset(map,0,2*503*4); for(int i=0;i<h;i++){ y=i%2; up=(i+1)%2; scanf("%s",row); for(int x=0;x<w;x++){ map[y][x+1]=row[x]=='.'?map[up][x+1]+1:0; } for(int x=1;x<=w;x++){ if(map[y][x]!=0){ cp=map[y][x]; lp=rp=0; while(map[y][x-lp-1]>=cp) lp++; while(map[y][x+rp+1]>=cp) rp++; sum=cp*(rp+lp+1); max=max<sum ? sum:max; } } } printf("%d\n",max); } int main() { int w,h; scanf("%d %d",&h,&w); while(h!=0 && w!=0){ setMap(h,w); scanf("%d %d",&h,&w); } } ---- *0117 A reward for a Carpenter http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0117 サイズが小さいので手抜きダイクストラで解。 もしグラフが大きくなったら高速化のためにノードをvectorに持たせるし、ノードの取り出しや計算済みポイントの取り出しに優先順位付きキューを使いコードが少し膨らむ。 #include<stdio.h> int max=1000000000; int g[21][21]; int Dijkstras(int start,int goal,int n){ int cost[21],flag[21]={0},p,min; for(int i=1;i<=n;i++){ cost[i]=max; flag[i]=0; } cost[start]=0; while(1){ min=max; p=-1; for(int i=1;i<=n;i++){ if(cost[i]<min && flag[i]==0){ min=cost[i]; p=i; } } if(p==-1) break; flag[p]=1; for(int j=1;j<=n;j++){ if(g[p][j]+cost[p]<cost[j]){ cost[j]=g[p][j]+cost[p]; } } } return cost[goal]; } int main(){ int n,m,a1,b1,c1,d1,x1,x2,y1,y2; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ g[i][j]=max; } } for(int i=0;i<m;i++){ scanf("%d,%d,%d,%d",&a1,&b1,&c1,&d1); g[a1][b1]=c1; g[b1][a1]=d1; } scanf("%d,%d,%d,%d",&x1,&x2,&y1,&y2); int ans=y1-y2-Dijkstras(x1,x2,n)-Dijkstras(x2,x1,n); printf("%d\n",ans); } ---- *0118 Property Distribution http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0118 何も考えずに探索するだけ。 しかしこの問題マップサイズが数万*数万とかになったらどんなアルゴリズムがあるのだろうか？ http://mainly-coding.blogspot.com/2011/02/aizu-online-judge-0118-property.html #include<stdio.h> char map[101][101]; int dxs[]={1,0,-1,0}; int dys[]={0,1,0,-1}; int h,w; void saiki(int x,int y,char t){ int nx,ny; map[y][x]='.'; for(int i=0;i<4;i++){ nx=x+dxs[i]; ny=y+dys[i]; if(nx<0 || w<=nx || ny<0 || h<=ny || map[ny][nx]!=t) continue; saiki(nx,ny,t); } } void calc(){ for(int i=0;i<h;i++){ scanf("%s",map[i]); } int count=0; for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ if(map[i][j]!='.'){ count++; saiki(j,i,map[i][j]); } } } printf("%d\n",count); } int main(){ while(1){ scanf("%d %d",&h,&w); if(w==0 && h==0) break; calc(); } } ---- *0119 Taro's Obsession http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0119 この問題はジャッジデータが存在しないために飛ばし。 入った順番を示す→付きグラフをたどるのだろうけど多分順番を決定できない場合があるのでジャッジしない問題になったと思われる。 ---- 0120 Patisserie 3か月ほどまえにどこのサイトか忘れたけどこの問題一度答えを見ちゃったのよね。 なのでカンニングしたのと同じ。
