夢追い人

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

書かないほうがいいと思ったけど

まぁ一区切り付いたし一応書いておきます。

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ががががが

広告を非表示にする