Div.1Easy埋め再開

部活でコーディング(^O^)

SRM425 CrazyBot

方向ごとにその方向に進む確率だけ決まっていてあとはランダムに動くロボットがn回動いた時、同じマスにとまらずにn回進む確率を求める問題。
n<=14なのでHannyCombみたいにメモ化再帰でやる。
120.11点ではあったけど確率問題できたのは嬉しい

class CrazyBot {
public:
    double ep,wp,sp,np;
    double field[29][29];
    bool cnt[29][29];
    bool isin(int x, int y) {
        return x>=0&&x<29&&y>=0&&y<29;
    }
    void dfs(int n, int x, int y, double befp, int deg) {
        if (cnt[x][y]) return;
        cnt[x][y]=true;
        double p=0.0;
        int dx[4]={0,0,-1,1};
        int dy[4]={-1,1,0,0};
        if (deg==0) p=befp*ep;
        else if (deg==1) p=befp*wp;
        else if (deg==2) p=befp*sp;
        else if (deg==3) p=befp*np;
        if (--n==0) field[x][y]+=p;
        else {
            for (int i=0; i<4; i++) {
                int nx=x+dx[i], ny=y+dy[i];
                if (isin(nx,ny)) dfs(n,nx,ny,p,i);
            }
        }
        cnt[x][y]=false;
        return;
    }
    double getProbability( int n, int east, int west, int south, int north ) {
        ep=east/100.0; wp=west/100.0; sp=south/100.0; np=north/100.0;
        // printf("%.2f %.2f %.2f %.2f\n",ep,wp,sp,np);
        int dx[4]={0,0,-1,1};
        int dy[4]={-1,1,0,0};
        if (n==1) return 1.0;
        for (int i=0; i<29; i++) for (int j=0; j<29; j++) {
            cnt[i][j]=false;
            field[i][j]=0.0;
        }
        cnt[14][14]=true;
        for (int i=0; i<4; i++) {
            int nx=14+dx[i],ny=14+dy[i];
            if (isin(nx,ny)) dfs(n,nx,ny,1.0,i);
        }
        double res=0.0;
        for (int i=0; i<29; i++) for (int j=0; j<29; j++) {
            res+=field[i][j];
        }
        return res;
    }
};

SRM255 WordCompositionGame

かぶったら負け的な言葉のゲーム。
mapであらかじめ出現回数をカウントしておいて得点を求めるだけ。

class WordCompositionGame {
public:
    string score( vector <string> listA, vector <string> listB, vector <string> listC ) {
        map<string, int> gcnt;
        for (int i=0; i<listA.size(); i++) {
            if (gcnt.find(listA[i])!=gcnt.end()) gcnt[listA[i]]++;
            else gcnt[listA[i]]=1;
        }
        for (int i=0; i<listB.size(); i++) {
            if (gcnt.find(listB[i])!=gcnt.end()) gcnt[listB[i]]++;
            else gcnt[listB[i]]=1;
        }
        for (int i=0; i<listC.size(); i++) {
            if (gcnt.find(listC[i])!=gcnt.end()) gcnt[listC[i]]++;
            else gcnt[listC[i]]=1;
        }
        int A=0, B=0, C=0;
        for (int i=0; i<listA.size(); i++) {
            A+=4-gcnt[listA[i]];
        }
        for (int i=0; i<listB.size(); i++) {
            B+=4-gcnt[listB[i]];
        }
        for (int i=0; i<listC.size(); i++) {
            C+=4-gcnt[listC[i]];
        }
        stringstream sA, sB, sC;
        string scA, scB, scC;
        sA<<A; sA>>scA;
        sB<<B; sB>>scB;
        sC<<C; sC>>scC;
        return scA+"/"+scB+"/"+scC;
    }
};

stringstream難しい。

SRM231 Stitch

文字列をある規則によって合成する問題。
割った時小数点一位で四捨五入しなければならないのが人外に難しかった。

class Stitch {
public:
    vector <string> stitch( vector <string> A, vector <string> B, int overlap ) {
        int spos=A[0].length()-overlap;
        vector<string> res(A.size(), "");
        for (int i=0; i<A.size(); i++) {
            for (int j=0; j<spos; j++) res[i]+=A[i][j];
            for (int j=spos; j<A[i].length(); j++) {
                int x=j-spos;
                char rc=(char)((((overlap-x)*(int)A[i][j]+((x+1)*(int)B[i][x]))+overlap) / (overlap+1));
                if ((((overlap-x)*(int)A[i][j]+((x+1)*(int)B[i][x]))+overlap)%(overlap+1)<(overlap+2)/2-1) rc--;
                res[i]+=rc;
            }
            for (int j=overlap; j<B[i].length(); j++) {
                res[i]+=B[i][j];
            }
        }
        return res;
    }
};

AOJ 0560

なんか無駄にWAしてたorz
アルゴリズムはいいんだけど、実装力がない。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct joi {
int j, o, i;
joi(){j=0;o=0;i=0;}
};
joi sum[1005][1005];
int m,n,k;
int main() {
    scanf("%d%d%d",&m,&n,&k);
    for (int i=1; i<=m; i++) {
        string row; cin>>row;
        for (int j=1; j<=n; j++) {
            sum[i][j].j=sum[i-1][j].j+sum[i][j-1].j-sum[i-1][j-1].j;
            sum[i][j].o=sum[i-1][j].o+sum[i][j-1].o-sum[i-1][j-1].o;
            sum[i][j].i=sum[i-1][j].i+sum[i][j-1].i-sum[i-1][j-1].i;
            if (row[j-1]=='J') sum[i][j].j++;
            if (row[j-1]=='O') sum[i][j].o++;
            if (row[j-1]=='I') sum[i][j].i++;
        }
    }
    int a,b,c,d;
    for (int i=0; i<k; i++) {
        scanf("%d%d%d%d",&a,&b,&c,&d);a--;b--;
        int rj=sum[c][d].j+sum[a][b].j-sum[a][d].j-sum[c][b].j;
        int ro=sum[c][d].o+sum[a][b].o-sum[a][d].o-sum[c][b].o;
        int ri=sum[c][d].i+sum[a][b].i-sum[a][d].i-sum[c][b].i;
        printf("%d %d %d\n",rj,ro,ri);
    }
    /*for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            printf("(%d,%d,%d)%c",sum[i][j].j,sum[i][j].o,sum[i][j].i,j==n-1?'\n':' ');
        }
    }*/
}