書かないほうがいいと思ったけど
まぁ一区切り付いたし一応書いておきます。
ARC 3
A
誤差が怖いだっち←たまごっち?
#include <cstdio> #include <iostream> using namespace std; #define eps 1e-9 /* レートいつつくんですか???? */ int main() { int n; string r; scanf("%d",&n); cin>>r; double sum=0; for (int i=0; i<n; i++) { if (r[i]=='A') sum+=4.0; if (r[i]=='B') sum+=3.0; if (r[i]=='C') sum+=2.0; if (r[i]=='D') sum+=1.0; } double res=sum/n; printf("%.10f\n",res); }
B
一番簡単だった
#include <cstdio> #include <iostream> #include <string> #include <algorithm> using namespace std; int n; string s[100]; int main() { scanf("%d",&n); for (int i=0; i<n; i++) { string in; cin>>in; reverse(in.begin(), in.end()); s[i]=in; } sort(s, s+n); for (int i=0; i<n; i++) { reverse(s[i].begin(), s[i].end()); cout<<s[i]<<endl; } }
C
こういう問題はにぶたん+BFS、にぶたん+BFS、覚えましたし
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <map> #define eps 1e-9 #define T 0.99 using namespace std; typedef pair<int, int> P; int n, m, sx, sy, gx, gy; int dx[4]={0,0,-1,1}; int dy[4]={-1,1,0,0}; double dlg[9][500000]; bool used[500][500]; string mp[500]; bool isin(int x, int y) { return x>=0&&x<n&&y>=0&&y<m; } bool isgo() { queue<P> que; que.push(P(sx,sy)); memset(used, 0, sizeof(used)); used[sx][sy]=true; while (!que.empty()) { P p=que.front(); que.pop(); int x=p.first, y=p.second; if (x==gx&&y==gy) return true; for (int i=0; i<4; i++) { int nx=x+dx[i], ny=y+dy[i]; if (isin(nx,ny)&&!used[nx][ny]&&mp[nx][ny]!='#') { que.push(P(nx,ny)); used[nx][ny]=true; } } } return false; } bool C(double r) { queue<pair<int, P> > que; que.push(make_pair(1, P(sx,sy))); memset(used, 0, sizeof(used)); while (!que.empty()) { int t=que.front().first; P p=que.front().second; que.pop(); int x=p.first, y=p.second; if (used[x][y]) continue; used[x][y]=true; for (int i=0; i<4; i++) { int nx=x+dx[i], ny=y+dy[i]; if (isin(nx,ny)&&!used[nx][ny]&&mp[nx][ny]!='#') { if (mp[nx][ny]=='g') return true; int lg=mp[nx][ny]-'0'-1; if (dlg[lg][t]<r) continue; //printf("%d %d %d %d %.3f\n",nx,ny,t,lg,dlg[lg][t]); que.push(make_pair(t+1, P(nx, ny))); } } } return false; } int main() { for (int i=0; i<9; i++) { dlg[i][0]=i+1; for (int j=1; j<500000; j++) { dlg[i][j]=dlg[i][j-1]*T; } } scanf("%d%d",&n,&m); for (int i=0; i<n; i++) { cin>>mp[i]; for (int j=0; j<m; j++) { if (mp[i][j]=='s') { sx=i; sy=j; } if (mp[i][j]=='g') { gx=i; gy=j; } } } if (!isgo()) puts("-1"); else { double lb=0.0, ub=10.0; for (int i=0; i<100; i++) { double mid=(lb+ub)/2.0; if (C(mid)) lb=mid; else ub=mid; } printf("%.10f\n",lb); } }
WUPC
A
サンプル確認しないの良くないある
#include <cstdio> int day[12]={31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int main() { int ma,da,mb,db; scanf("%d%d%d%d",&ma,&da,&mb,&db); int res=0; if (ma==mb) res=db-da; else { res+=-da+db; for (int i=ma-1; i<mb-1; i++) res+=day[i]; } printf("%d\n",res); }
B
テクニカルにやろうとして失敗、結局愚直解
#include <iostream> #include <algorithm> #include <vector> using namespace std; string dict[50]; vector<string> res; int main() { int n; cin>>n; for (int i=0; i<n; i++) cin>>dict[i]; for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { if (i==j) continue; res.push_back(dict[i]+dict[j]); } } sort(res.begin(), res.end()); cout<<res[0]<<endl; }
C
最短経路はBFSだった、そうだった
#include <cstdio> #include <cstring> #include <climits> #include <iostream> #include <algorithm> #include <map> #include <queue> using namespace std; #define M INT_MAX/2 typedef pair<int, int> P; int n, m, sx, sy, cx, cy, gx, gy; int used[500][500]; int ret[500][500]; string mat[500]; int dx[4]={0,0,-1,1}; int dy[4]={-1,1,0,0}; int dfs(int x, int y, int tx, int ty) { memset(used, 0, sizeof(used)); for (int i=0; i<n; i++) for (int j=0; j<n; j++) ret[i][j]=M; ret[x][y]=0; used[x][y]=1; queue<P> que; que.push(P(x,y)); while (!que.empty()) { P p=que.front(); que.pop(); x=p.first; y=p.second; if (x==tx&&y==ty) continue; for (int i=0; i<4; i++) { int nx=x+dx[i], ny=y+dy[i]; if (!used[nx][ny]&&mat[nx][ny]!='#') { ret[nx][ny]=ret[x][y]+1; used[nx][ny]=1; que.push(P(nx,ny)); } } } if (ret[tx][ty]==M) return -1; else return ret[tx][ty]; } int main() { scanf("%d%d",&n,&m); for (int i=0; i<n; i++) { cin>>mat[i]; for (int j=0; j<m; j++) { if (mat[i][j]=='S') { sx=i; sy=j; } if (mat[i][j]=='C') { cx=i; cy=j; } if (mat[i][j]=='G') { gx=i; gy=j; } } } int r1=dfs(sx,sy,cx,cy); int r2=dfs(cx,cy,gx,gy); if (r1>0&&r2>0) printf("%d\n",r1+r2); else puts("-1"); }
D
らくちんでござる
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n, dp[100][100], a[100][100]; int main() { scanf("%d",&n); for (int i=0; i<n; i++) for (int j=0; j<=i; j++) scanf("%d",&a[i][j]); memset(dp, 0, sizeof(dp)); dp[0][0]=a[0][0]; for (int i=1; i<n; i++) { for (int j=0; j<=i; j++) { int x=0, y=dp[i-1][j]; if (j!=0) x=dp[i-1][j-1]; dp[i][j]=a[i][j]+max(x,y); } } printf("%d\n", *max_element(dp[n-1], dp[n-1]+n)); }
おわり
AtCoderの問題ってなんだかリハビリにいい問題が多いな…とか思ったり
明日の新幹線でも精進しますよw
てかPKU2110ががががが