AOJ Volume 0 (0060-0079)
はい。
http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?volumeNo=0
0060: Card Game
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<queue> #include<algorithm> #include<map> #include<cmath> #include<complex> using namespace std; int main(){ int mod=1000000007; int c1,c2,c3; while (scanf("%d %d %d",&c1,&c2,&c3)!=EOF) { bool x[10]={0}; x[c1-1]=1; x[c2-1]=1; x[c3-1]=1; int cnt=0; for (int i=0;i<10;++i) { if (x[i]==0 && c1+c2+i<20) cnt++; } printf((cnt>3)?"YES\n":"NO\n"); } return 0; }
自分の手持ちカード2枚の和と残りカード7枚(相手側の見えないカードも残りとして扱った)との和で20以下になるものの件数を数えた。件数が3件より多いならばYES、3件以下ならNOという判定にした。
0061: Rank Checker
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<queue> #include<algorithm> #include<cmath> #include<complex> using namespace std; int main(){ int mod=1000000007; int p,s,q; bool x[31]={0}; map<int,int> m; for (;;){ scanf("%d,%d",&p,&s); if (p==0 && s==0) break; m[p]=s; x[s]=1; } while (scanf("%d",&q)!=EOF) { int cnt=0; for (int i=31;i>-1;--i) { if (x[i]==1) cnt++; if (i==m[q]) { printf("%d\n",cnt); break; } } } return 0; }
その点数の参加者が存在するか、存在するなら全体で何番目になるかをbool配列で管理した。それぞれの参加者が何点なのかはmapを使ったが、これは2元配列とかでも代用できると思う。
0062: What is the Bottommost?
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<algorithm> #include<cmath> #include<complex> using namespace std; int main(){ int mod=1000000007; char str[11]; int a[10][10]; while (scanf("%s ",str)!=EOF) { for (int i=0;i<10;++i) { a[0][i]=str[i]-'0'; } for (int i=1;i<10;++i) { for (int j=0;j<10-i;++j) { a[i][j]=(a[i-1][j]+a[i-1][j+1])%10; } } printf("%d\n",a[9][0]); } return 0; }
配列を10 * 10で用意して1行目で入力を受取して下の行で上の行の2つの和を入れていく。
0063: Palindrome
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<algorithm> #include<cmath> #include<complex> using namespace std; int main() { char s[111]; int ans=0; while(scanf("%s",s)!=EOF) { int tmp=strlen(s); int f=1; for (int i=0;i<tmp/2;++i) { if (s[i]!=s[tmp-(i+1)]) { f=0; break; } } if (f) ans++; } printf("%d\n",ans); return 0; }
受取にscanfだけでなくてfgetsも使えるがその場合は末尾に改行コードが入ることなど注意。
0064: Secret Number
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<algorithm> #include<cmath> #include<complex> using namespace std; int main(){ char str[102]; int len,n=0,ans=0; while (fgets(str,102,stdin)!=NULL) { len=strlen(str)-1; for (int i=0;i<len;++i) { if(str[i]>='0' && str[i]<='9'){ n*=10; n+=str[i]-'0'; } else { ans+=n; n=0; } } } printf("%d\n",ans); return 0; }
'0'や'9'との比較で文字列中で数字部分を探す。数字を発見時は1桁の数としてint型で保存する。連続して数字が並んでいる時は保存してある数字を10倍にして、並んでいた数字を新たに1桁目に割り当てる。それらの数の和が解になる。
0065: Trading
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<algorithm> #include<cmath> #include<complex> using namespace std; int main(){ bool a[1001]={false}; bool b[1001]={false}; int mm[1001]={0}; char tmp[100]; int x,y; for (;;) { fgets(tmp,100,stdin); if(tmp[0]<'0' || tmp[0]>'9') break; sscanf(tmp,"%d,%d",&x,&y); a[x]=true; mm[x]+=1; } for (;;) { if (fgets(tmp,100,stdin)==NULL) break; sscanf(tmp,"%d,%d",&x,&y); b[x]=true; mm[x]+=1; } for (int i=1;i<1001;++i) { if (a[i] && b[i]) { printf("%d %d\n",i,mm[i]); } } return 0; }
fgetsで何でも読み込む。tmpに入ったものの[0]が数字でない場合は、一旦は処理の切り替えタイミングになる。fgetsで読み込んだものをsscanf()で再度','区切りでint型で読み込む。受取が出来るようになれば1ヶ月目と2ヶ月目の出現をそれぞれ別のbool型配列で管理と、出現の総回数の保存をしておいて出題の支持に従って出力する。 1,2ヶ月目を1つのint型配列でやりくりも多分出来ると思う。
0066: Tic Tac Toe
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<algorithm> #include<cmath> #include<complex> using namespace std; int main(){ char tmp[10]; int x,y,f,cnt=0; while (scanf("%s",tmp)!=EOF) { f=0; if (tmp[0]==tmp[1] && tmp[1]==tmp[2] && tmp[2]!='s') { printf("%c\n",tmp[0]); f=1; } else if (tmp[3]==tmp[4] && tmp[4]==tmp[5] && tmp[5]!='s') { printf("%c\n",tmp[3]); f=1; } else if (tmp[6]==tmp[7] && tmp[7]==tmp[8] && tmp[8]!='s') { printf("%c\n",tmp[6]); f=1; } else if (tmp[0]==tmp[3] && tmp[3]==tmp[6] && tmp[6]!='s') { printf("%c\n",tmp[6]); f=1; } else if (tmp[1]==tmp[4] && tmp[4]==tmp[7] && tmp[7]!='s') { printf("%c\n",tmp[7]); f=1; } else if (tmp[2]==tmp[5] && tmp[5]==tmp[8] && tmp[8]!='s') { printf("%c\n",tmp[8]); f=1; } else if (tmp[0]==tmp[4] && tmp[4]==tmp[8] && tmp[8]!='s') { printf("%c\n",tmp[8]); f=1; } else if (tmp[2]==tmp[4] && tmp[4]==tmp[6] && tmp[6]!='s') { printf("%c\n",tmp[6]); f=1; } if (f==0) printf("d\n"); } return 0; }
3 * 3のマスで並んだ形の中を探索すると言うよりは長さ9の文字列のままで縦横斜めのそれぞれの3つ並びが全て同じになっていないかをチェックする。但し、3マスとも空マスsの場合があるのでそれもチェックする。
0067: The Number of Island
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<algorithm> #include<cmath> #include<complex> using namespace std; char m[12][12]; int w[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; void sol(int i,int j) { int ni,nj; m[i][j]='0'; for(int k=0;k<4;++k) { ni=i+w[k][0]; nj=j+w[k][1]; if (ni>=0 && ni<=11 && nj>=0 && nj<=11 ) { if(m[ni][nj]=='1') sol(ni,nj); } } return; } int main(){ int ans; while (scanf("%s",m[0])!=EOF){ ans=0; for (int i=1;i<12;++i) { scanf("%s",m[i]); } for (int i=0;i<12;++i) { for (int j=0;j<12;++j) { if (m[i][j]=='1') { sol(i,j); ans++; } } } printf("%d\n",ans); } return 0; }
0,0から11,11の端までチェックする。チェックしたマスが'1'で島なら四方に繋がっていないをチェックする。いまチェックしたマスと繋がってる島は全て'0'で海にしてします。端からの捜索で見つかった時に繋がっているものは全て海にしてしまえば、島の発見回数と島の数が等しくなり、それが解になる。あと再帰処理覚えるのが大事。
0068: Enclose Pins with a Rubber Band
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<algorithm> #include<cmath> #include<complex> using namespace std; #define EACH(v, c) for(auto&v:c) double EPS=1e-10; struct P { double x,y; P() : x(0),y(0) { return; } P(double x,double y) : x(x),y(y) { return; } P operator + (const P &a) const { return P(x+a.x,y+a.y); } P operator - (const P &a) const { return P(x-a.x,y-a.y); } P operator * (const double &a) const { return P(x*a,y*a); } P operator / (const double &a) const { return P(x/a,y/a); } bool operator < (const P &a) const { return x==a.x?y<a.y:x<a.x; } }; double cross(const P &a, const P &b) { return a.x*b.y-a.y*b.x; } vector<P> convex_hull(vector<P> ps) { const int n=ps.size(); sort(ps.begin(),ps.end()); int k=0; vector<P> convex(n*2); for (int i=0;i<n;++i) { while (k>1 && cross(convex[k-1]-convex[k-2], ps[i]-convex[k-1])<=0) k--; convex[k++]=ps[i]; } for (int i=n-2,t=k;i>=0;--i) { while (k>t && cross(convex[k-1]-convex[k-2],ps[i]-convex[k-1])<=0) k--; convex[k++]=ps[i]; } convex.resize(k-1); return convex; } int main() { cin.tie(0); ios::sync_with_stdio(false); for (;;) { int n; cin>>n; if (n==0) { break; } vector<P> ps(n); int tmp=10; EACH(p, ps) { char d; cin >> p.x >> d >> p.y; } vector<P> convex=convex_hull(ps); printf("%d\n",n-convex.size()); } return 0; }
凸法で解決するらしい。 写経元 http://torus711.hatenablog.com/entry/20121207/p1 蟻本読むなら233Pら辺かな。但し、蟻本のサンプルコード写経するならその前の部分から読む必要あり。
0069: Drawing Lots II
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<algorithm> #include<cmath> #include<complex> using namespace std; int main() { int n,m,a,d,tmp; int b[30][10]; char s[10]; bool f; for (;;) { scanf("%d",&n); if (n==0) break; scanf("%d",&m); scanf("%d",&a); scanf("%d",&d); for (int i=0;i<d;++i) { scanf("%s",&s); for (int j=0;j<n-1;++j) { b[i][j]=s[j]-'0'; } } tmp=m; for(int i=0;i<d;++i) { if(tmp<n && b[i][tmp-1]) tmp++; else if (tmp>1 && b[i][tmp-2]) tmp--; } if(tmp==a) { printf("0\n"); } else { f=0; for (int i=0;i<d;++i) { for (int j=0;j<n-1;++j) { if (!b[i][j] && (!j || !b[i][j-1]) && (j==n-2 || !b[i][j+1])) { b[i][j]=1; tmp=m; for (int k=0;k<d;++k) { if (tmp<n && b[k][tmp-1]) tmp++; else if (tmp>1 && b[k][tmp-2]) tmp--; } if (tmp==a) { f=1; printf("%d %d\n",i+1,j+1); } b[i][j]=0; } if (f) break; } if (f) break; } if (!f) printf("1\n"); } } return 0; }
写経。スタート地点をtmpに代入して素の状態での当たりをチェックして辿り着いていれば0で、そうでなければ両脇0で線を引けるトコには線を引いてみて、b[i][j]=1してから辿ってみて当たりなら解出力する。違ったらb[i][j]=0して線をなかったコトにして新たな線を試す。最終まで試してたどり着けなければ1出力をする。
0070: Combination of Number Sequences
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<queue> #include<algorithm> using namespace std; int dp[11][331][1025]; int solve(int n,int s,int used) { if (n==0 && s==0) return 1; if (n<=0 || s<0) return 0; if (dp[n][s][used] != -1) return dp[n][s][used]; int sum=0; for (int i=0;i<10;++i) { if ((used>>i)%2==0) { used+=1<<i; sum+=solve(n-1,s-i*n,used); used-=1<<i; } } return dp[n][s][used]=sum; } int main(){ int n,s; memset(dp,-1,sizeof(dp)); while (scanf("%d %d",&n,&s)!=EOF) { if (0<=s && s<=330) { int used=0; printf("%d\n",solve(n,s,used)); } else { printf("0\n"); } } return 0; }
写経。dp配列に0から9までの数のそれぞれの使い方で幾つになるかをつくってるのかな？？あとでもう少し掘り下げる。
0071: Bombs Chain
C++14
#include<bits/stdc++.h> #include<algorithm> using namespace std; char sute[1]; char m[8][8]; int w[12][2]={{-3,0},{-2,0},{-1,0},{3,0},{2,0},{1,0},{0,-3},{0,-2},{0,-1},{0,1},{0,2},{0,3}}; void bomb(int i,int j){ int ni,nj; for (int k=0;k<12;++k) { m[i][j]='0'; ni=i+w[k][0]; nj=j+w[k][1]; if (ni>=0 && ni<8 && nj>=0 && nj<8) { if (m[ni][nj]=='1') { bomb(ni,nj); } else { m[ni][nj]='0'; } } } return; } int main(){ int n,cnt=1,x,y; scanf("%d",&n); for (int i=0;i<n;++i){ fgets(sute,1,stdin); for (int j=0;j<8;++j) { scanf("%s",m[j]); } scanf("%d",&x); scanf("%d",&y); bomb(y-1,x-1); printf("Data %d:\n",cnt); cnt++; for (int j=0;j<8;++j) { for (int k=0;k<8;++k) { printf("%c",m[j][k]); } printf("\n"); } } return 0; }
再帰で縦8横8の範囲内を上下左右3マス処理すれば大丈夫だと思う。
0072: Carden Lantern
後で
0073: Surface Area of Quadrangular Pyramid
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<queue> #include<cmath> #include<algorithm> using namespace std; int main(){ int mod=1000000007; int x,h; for (;;) { scanf("%d",&x); scanf("%d",&h); if (x==h && x==0) break; printf("%lf\n",1.0*x*x+sqrt((1.0*x/2)*(1.0*x/2)+h*h)*x*2); } return 0; }
底面は正方形の面積で、錐の三角形部分は底辺は正方形の辺を使って高さは直角三角形のa2 + b2 = c2 で求めて、それが4つ分あって総和が解になる。
0074: Videotape
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<queue> #include<algorithm> using namespace std; int main(){ int mod=1000000007; int teep=120*60; int t,h,s; for (;;) { scanf("%d %d %d",&t,&h,&s); if (t==-1) break; int hyojun=teep-(t*3600+h*60+s); printf("%02d:%02d:%02d\n",hyojun/3600,(hyojun%3600)/60,hyojun%60); hyojun*=3; printf("%02d:%02d:%02d\n",hyojun/3600,(hyojun%3600)/60,hyojun%60); } return 0; }
一旦は全部を秒で考えて通常テープだけ計算して、3倍モード分は標準と3の積で解にする。後はまた時間表記に注意する。
0075: BMI
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<queue> #include<algorithm> using namespace std; int main(){ int mod=1000000007; int teep=120*60; int s; double w,h; while(scanf("%d,%lf,%lf",&s,&w,&h)!=EOF) { if (25.0-w/(h*h)<1e-10) printf("%d\n",s); } return 0; }
問題文に書かれている計算式の通りに。
0076: Treasure Hunt II
後で
0077: Run Length
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<queue> #include<algorithm> using namespace std; int main(){ int mod=1000000007; char s[51]; while(scanf("%s",&s)!=EOF) { int len=strlen(s); int f=0; for (int i=0;i<len;++i) { if (f==0 and s[i]!='@') { printf("%c",s[i]); } else if (s[i]=='@') { f=1; } else if (f==1) { f=2; } else if (f==2) { for (int j=0;j<s[i-1]-'0';++j) { printf("%c",s[i]); } f=0; } } printf("\n"); } return 0; }
先頭から見ていって@が出現したフラグを立てて、@の次の数字の個数だけ更に次の文字を出力させた。それ以外は入力で受け取った通りに。
0078: Magic Square
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<queue> #include<algorithm> using namespace std; int main(){ int mod=1000000007; char s[51]; int n; for (;;) { scanf("%d",&n); if (n==0) break; int ans[n][n]; for (int i=0;i<n;++i) { for (int j=0;j<n;++j) { ans[i][j]=-1; } } int x=n/2, y=n/2+1; for (int i=1;i<=n*n;++i) { ans[y][x]=i; y=(y+1)%n; x=(x+1)%n; if (ans[y][x]!=-1) { y=(y+1)%n; x=(x+n-1)%n; } } for (int i=0;i<n;++i){ for (int j=0;j<n;++j) { if (j<n-1) { printf("%4d",ans[i][j]); } else { printf("%4d\n",ans[i][j]); } } } } return 0; }
問題文に書かれている作成方法をバグらせずに実装する。端から反対側に抜けるのには%nで剰余を利用する。既に数が入っている時の左上への行き方が少し注意が必要。
0079: Area of Polygon
C++14
#include<bits/stdc++.h> #include<vector> #include<list> #include<stack> #include<queue> #include<algorithm> using namespace std; int main(){ double tmp[20][2]; int cnt=0; double ans=0.0; while (scanf("%lf,%lf",&tmp[cnt][0],&tmp[cnt][1])!=EOF) { cnt++; } for (int i=0;i<cnt;++i) { ans+=(tmp[i][0]-tmp[(i+1)%cnt][0])*(tmp[i][1]+tmp[(i+1)%cnt][1]); } ans=abs(ans); printf("%lf\n",ans/2.0); return 0; }
なぜそれでいいのかはわかりませんが ( \(x_k\) - \(x{k+1}\) ) * ( \(y_k\) + \(y{k+1}\) ) の式で最後のkは1番目のとの計算をして総和を2で割った商が面積になるらしい。
