20位なday3
ABC三完の凡人だった
A
やるだけ
#include <iostream> #include <vector> #include <map> using namespace std; typedef pair<string, int> P; vector<P> log; int main() { string s; cin >> s; string bef=""; int i=0; if (s[0]=='e') { bef="egg"; i+=3; } else { bef="chicken"; i+=7; } if (i==s.length()) { cout<<bef<<endl; return 0; } int cnt=1; for (;i<s.length(); i++) { if (s[i]=='e'&&bef=="egg") { log.push_back(P(bef,cnt)); cnt=1; i+=2; } else if (s[i]=='c'&&bef=="chicken") { log.push_back(P(bef,cnt)); cnt=1; i+=6; } else { if (s[i]=='e') { bef="egg"; i+=2; } else if (s[i]=='c') { bef="chicken"; i+=6; } cnt++; } } log.push_back(P(bef,cnt)); string res; int rc=0; for (int i=0; i<log.size(); i++) { if (log[i].second>rc) { res=log[i].first; rc=log[i].second; } // cout<<log[i].first<<" "<<log[i].second<<endl; } cout<<res<<endl; }
B
空白マスの期待値をどうするか迷いましたが結局適当に近似するだけでした
#include <cstdio> #include <algorithm> using namespace std; #define EPS 0.0000001 int main() { int t; scanf("%d",&t); double max_v=0.0; for (int i=0; i<t; i++) { double v=0.0, r=1.0; int n, m; scanf("%d%d",&n,&m); for (int j=0; j<m; j++) { int vj; double rj; scanf("%d%lf",&vj,&rj); v+=vj*rj; r-=rj; } double x=1.0, y=0.0; for (int j=0; j<100; j++) { y+=v*x; x*=r; } max_v=max(max_v,y); } int p, q; scanf("%d%d",&p,&q); double boss=0.0, br=1.0; for (int i=0; i<q; i++) { int vi; double ri; scanf("%d%lf",&vi,&ri); boss+=vi*ri; br-=ri; } double bx=1.0, by=0.0; for (int i=0; i<100; i++) { by+=boss*bx; bx*=br; } if (by+EPS<=max_v) puts("YES"); else puts("NO"); }
C
Union-Findやるだけ
最初DFSとかBFSでできるかなとか変な考えもってTLEとかMLE量産して、
Union-Find気づいてからは添字ミスとかいろいろで大量にWA量産してた
#include <cstdio> #include <iostream> #include <map> #include <queue> #include <vector> using namespace std; typedef pair<int,int> P; string field[1000]; int w, h; int n; int dx[4]={0,0,-1,1}; int dy[4]={-1,1,0,0}; struct unionfind { int par[1000005], rank[1000005]; unionfind(int w, int h) { for (int i=0; i<h; i++) { for (int j=0; j<w; j++) { par[i*w+j]=i*w+j; rank[i*w+j]=i*w+j; } } } int find(int x) { if (x==par[x]) { return x; } else { return par[x]=find(par[x]); } } void unite(int x, int y) { x=find(x); y=find(y); if (x==y) return; if (rank[x]<rank[y]) { par[x]=y; } else { par[y]=x; if (rank[x]==rank[y]) rank[x]++; } } bool same(int x, int y) { return find(x)==find(y); } }; bool isin(int x, int y) { return x>=0&&x<h&&y>=0&&y<w; } int main() { scanf("%d%d",&w,&h); for (int i=0; i<h; i++) cin>>field[i]; int res=-1; unionfind uf(w,h); int rx=-1, ry=-1; for (int i=0; i<h; i++) { for (int j=0; j<w; j++) { if (field[i][j]=='t') { rx=i; ry=j; field[i][j]='.'; } if (field[i][j]=='.') { field[i][j]='-'; queue<P> que; que.push(P(i,j)); while (!que.empty()) { P p=que.front(); que.pop(); for (int k=0; k<4; k++) { int nx=p.first+dx[k], ny=p.second+dy[k]; if (isin(nx,ny)&&field[nx][ny]=='.') { que.push(P(nx,ny)); uf.unite(i*w+j,nx*w+ny); field[nx][ny]='-'; } else if (isin(nx,ny)&&field[nx][ny]=='t') { que.push(P(nx,ny)); uf.unite(i*w+j,nx*w+ny); rx=nx; ry=ny; field[nx][ny]='-'; } } } } } } // for (int i=0; i<h; i++) cout<<field[i]<<endl; int r=rx*w+ry; if (uf.same(0,r)) res=0; scanf("%d",&n); for (int i=1; i<=n; i++) { int x, y; scanf("%d%d",&y,&x); field[x][y]='-'; if (res==-1) { for (int j=0; j<4; j++) { int nx=x+dx[j], ny=y+dy[j]; if (isin(nx,ny)&&field[nx][ny]=='-') { uf.unite(x*w+y,nx*w+ny); } } if (uf.same(0,r)) res=i; } } printf("%d\n",res); }
まとめ
Dは問題文が読めず
Eは難しい部分和の発展的な奴な気がして
Fはヒュタインズゲートってなんぞってなって
Gは読んでなかった
20位で三完は凡人の成績だからすごい人めざして精進したい