夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

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位で三完は凡人の成績だからすごい人めざして精進したい

広告を非表示にする