AtCoder006
A - 宝くじ
■問題
購入した宝くじと当選結果の一致している数字の数を数えてそれに対応した順位を出力する。
５つだった場合はボーナス数字があるかどうかで決める。
■解法
一致しているものを数えるだけ
やるだけ
■ソース
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<string> #include<vector> using namespace std; int e[10],l[10],b,ee,ll; int main(void){ int a=0,c=0; int ans[]={0,0,0,5,4,3,1,2}; for(int i=0;i<6;i++){ cin >> ee; e[ee]++; } cin >> b; for(int i=0;i<6;i++){ cin >> ll; l[ll]++; } for(int i=0;i<10;i++){ if(e[i] && l[i]){ a++; } } if(a == 5 && l[b]){ a+=2; } cout << ans[a] << endl; }
B - あみだくじ
■問題
あみだくじの線とあたりが与えられたときあたりにたどり着ける線がどれか求める。
■解法
下からルール通りたどるだけ
やるだけ
■ソース
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<string> #include<vector> using namespace std; int main(void){ int n,l,m; char s[21][101]; cin >> n >> l; int sl=n*2-1; cin.get(); for(int i=0;i<l+1;i++){ fgets(s[i],sizeof(s[i]),stdin); } for(int i=0;i<sl;i++){ if(s[l][i]=='o'){ m=i; break; } } for(int i=l-1;i>=0;i--){ if(m < sl-1 && s[i][m+1]=='-'){ m+=2; }else if(0 < m && s[i][m-1]=='-'){ m-=2; } } cout << m/2+1 << endl; }
C - 積み重ね
■問題
箱が下のものより上のものが軽いか同じ重さになるように積んだとき、山の数が最小の値を求めなさい。
■解法
積む時は、積める山の中で一番軽いところに積むのが最適である。
積めるところがない場合は新しい山を作る。
全探索でやるとＴＬＥするのでこのように貪欲法でやる。
■ソース
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<string> #include<vector> using namespace std; int n,w[51]; int t[51]; int ans =100; void solve(int i,int ti){ if(i==n){ ans = min(ans,ti); return; } int best=ti; for(int j=0;j<ti;j++){ if(t[j] >= w[i]){ if(best == ti || t[best]>t[j]){ best=j; } } } int temp=t[best]; t[best] = w[i]; solve(i+1,ti+((best==ti)?1:0) ); t[best]= temp; } int main(void){ cin >> n; for(int i=0;i<n;i++){ cin >> w[i] ; } solve(0,0); cout << ans << endl; }
D - アルファベット探し
■問題
入力データの中に'A、'B'、'C'と同じ形の図形が何個あるか求めろ。
整数倍に拡大したものや回転させたものも同じ図形である。
■解法
Aのつながっている数は12、Bのつながっている数は16、Cのつながっている数は11である。
回転してもその数は変わらず、整数倍してもその数は倍率^2の値になる。
後は数えるのを深さ優先ではなく幅優先でやって良い感じにする。
■ソース
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<string> #include<vector> #include<queue> using namespace std; string s[1001]; int h,w; int a,b,c; int dx[]={0,0,1,1,1,-1,-1,-1}; int dy[]={1,-1,0,1,-1,0,1,-1}; struct P{ int x,y; P(){} P(int x,int y):x(x),y(y){} }; int solve(int x,int y){ queue<P> que; que.push(P(x,y)); s[x][y]='.'; int ret=1; while(!que.empty()){ P p = que.front(); que.pop(); for(int i=0;i<8;i++){ int nx=p.x+dx[i]; int ny=p.y+dy[i]; if(0 <= nx && nx < h && 0<=ny && ny < w && s[nx][ny]=='o'){ s[nx][ny]='.'; ret++; que.push(P(nx,ny)); } } } return ret; } int main(void){ cin >> h >> w; for(int i=0;i<h;i++){ cin >> s[i]; } for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ if(s[i][j]=='o'){ int temp = solve(i,j); for(int l=1;;l++){ int ll=l*l; if(temp==12*ll){ a++; break; } else if(temp==16*ll){ b++; break; } else if(temp==11*ll){ c++; break; } } } } } cout << a << ' ' << b << ' ' << c << endl; }
