SRM636-639 Div1E

40問目まで来たね

 ・SRM636 Div1E ChocolateDividingEasy

大きさh×wのグリッドがある.各マスには0から9までの数字が書かれている.このグリッドを水平方向に2回,垂直方向に2回きって9個の小グリッドに分割する.各小グリッド内の数の和の最小値としてあり得るもののうち最大のものを求めよ.という問題.

これは簡単で分割方法を全て試すだけ.ただし一々ループして和を求めているとTLEするので二次元累積和を取っておいてO(1)で和が求まるようにしておく.

ソースコード

 

int sum[50][50];
class ChocolateDividingEasy {
    public:
    int findBest(vector<string> chocolate) {
        int h=chocolate.size();
        int w=chocolate[0].size();
        for(int i=0;i<h;i++) {
            for(int j=0;j<w;j++) sum[i][j]=chocolate[i][j]-'0';
            for(int j=1;j<w;j++) sum[i][j]+=sum[i][j-1];
        }
        for(int i=1;i<h;i++) {
            for(int j=0;j<w;j++) sum[i][j]+=sum[i-1][j];
        }
        int ans=0;
        for(int x1=0;x1<w;x1++) {
            for(int x2=x1+1;x2+1<w;x2++) {
                for(int y1=0;y1<h;y1++) {
                    for(int y2=y1+1;y2+1<h;y2++) {
                        vector<int> v;
                        v.push_back(sum[y1][x1]);
                        v.push_back(sum[y1][x2]-sum[y1][x1]);
                        v.push_back(sum[y1][w-1]-sum[y1][x2]);
                        v.push_back(sum[y2][x1]-sum[y1][x1]);
                        v.push_back(sum[y2][x2]-sum[y2][x1]-sum[y1][x2]+sum[y1][x1]);
                        v.push_back(sum[y2][w-1]-sum[y2][x2]-sum[y1][w-1]+sum[y1][x2]);
                        v.push_back(sum[h-1][x1]-sum[y2][x1]);
                        v.push_back(sum[h-1][x2]-sum[h-1][x1]-sum[y2][x2]+sum[y2][x1]);
                        v.push_back(sum[h-1][w-1]-sum[h-1][x2]-sum[y2][w-1]+sum[y2][x2]);
                        sort(v.begin(),v.end());
                        ans=max(ans,v[0]);
                    }
                }
            }
        }
        return ans;
    }
};

・SRM637 Div1E GreaterGame

1から2Nまでの数が書かれた2N枚のカードがある.A,BはそれぞれこのうちのN枚を手札とし,ゲームを行う.ゲームはNターンからなる.各ターンにおいて,二人は手札のうち1枚を選んで出し,大きい数を出した方が1点を得る.今,Aは自分の手札N枚とBがiターン目に出すカードを知っている(ただし一部は不明).Aが最適な順番でカードを出したときの,Aの得点の期待値を求めよ.という問題.

まずBがiターン目に出すカードが完全にわかっている場合の戦略をかんがえると,Bの出すカードよりも大きいカードのうち最も小さいものを出せばいいことがわかる(どれも相手より大きくないときは最小のカードを出す).そこでBの出すカードが判明しているターンについてはこの戦略を用いて出すことにする.そうすると確定で何点取れるかがわかる.のこりは不定の所だがよくかんがえると相手がランダムに並べてくる時点でこちらの並べ方は関係ないことがわかるので,のこりのカードを昇順に出すとする.そうすると,"dp[i][j]=i枚目まで出している時点で得点がjである確率"というDPが出来る.

ソースコード

double dp[51][51];
class GreaterGame {
    public:
    double calc(vector<int> hand, vector<int> sothe) {
        set<int> S,T;
        int N=hand.size();
        for(int i=1;i<=2*N;i++) T.insert(i);
        for(int i=0;i<N;i++) {
            T.erase(hand[i]);
            S.insert(hand[i]);
        }
        double ans=0;
        for(int i=0;i<N;i++) {
            if(sothe[i]==-1) continue;
            T.erase(sothe[i]);
            auto itr=S.upper_bound(sothe[i]);
            if(itr==S.end()) continue;
            S.erase(itr);
            ans++;
        }
        vector<int> s,t;
        auto S_itr=S.rbegin();
        auto T_itr=T.begin();
        int unk=T.size();
        for(int i=0;i<unk;i++) s.push_back(*(S_itr++)),t.push_back(*(T_itr++));
        sort(s.begin(),s.end());
        dp[0][0]=1;
        for(int i=0;i<unk;i++) {
            for(int j=0;j<=i;j++) {
                double win=lower_bound(t.begin(),t.end(),s[i])-t.begin();
                dp[i+1][j]+=(1-win/t.size())*dp[i][j];
                dp[i+1][j+1]+=(win/t.size())*dp[i][j];
            }
        }
        for(int i=0;i<=unk;i++) {
            ans+=i*dp[unk][i];
        }
        return ans;
    }
};

・SRM638 Div1E ShadowSculpture

大きさn×n×nの立方体(一つの面はXY平面上にある)から,いくつかの大きさ1×1×1の小立方体をのぞいた図形がある.ただしのこった小立方体は連結でないといけない.これをXY平面,YZ平面,ZX平面に射影したときの影が与えられる.これらの条件を図形が存在するかどうか判定せよ.という問題.

影ができていない所には小立方体があってはダメなので,小立方体があっても良い場所が求まる.それらが連結とはかぎらないので,各連結したパーツについてそれを射影したときの影が条件通りかどうかを調べてやる.罠が多いのでこれを時間内に出来る人はすごいと思う...

ソースコード

bool cube[10][10][10];
int  com[10][10][10];
int dx[6]={1,0,-1,0,0,0};
int dy[6]={0,1,0,-1,0,0};
int dz[6]={0,0,0,0,1,-1};
int n;
class ShadowSculpture {
    public:
    void dfs(int x,int y,int z,int k) {
        com[z][y][x]=k;
        for(int i=0;i<6;i++) {
            int nx=x+dx[i];
            int ny=y+dy[i];
            int nz=z+dz[i];
            if(0>nx||nx>=n||0>ny||ny>=n||0>nz||nz>=n||com[nz][ny][nx]!=-1||!cube[nz][ny][nx]) continue;
            dfs(nx,ny,nz,k);
        }
    }
    bool check(int k,vector<string> &XY,vector<string> &YZ,vector<string> &ZX) {
        for(int x=0;x<n;x++) {
            for(int y=0;y<n;y++) {
                bool Y=0;
                for(int z=0;z<n;z++) Y|=(com[z][y][x]==k);
                if(Y!=(XY[x][y]=='Y')) return false;
            }
        }
        for(int y=0;y<n;y++) {
            for(int z=0;z<n;z++) {
                bool Y=0;
                for(int x=0;x<n;x++) Y|=(com[z][y][x]==k);
                if(Y!=(YZ[y][z]=='Y')) return false;
            }
        }
        for(int z=0;z<n;z++) {
            for(int x=0;x<n;x++) {
                bool Y=0;
                for(int y=0;y<n;y++) Y|=(com[z][y][x]==k);
                if(Y!=(ZX[z][x]=='Y')) return false;
            }
        }
        return true;
    }
    string possible(vector<string> XY, vector<string> YZ, vector<string> ZX) {
        n=XY.size();
        for(int z=0;z<n;z++) {
            for(int y=0;y<n;y++) for(int x=0;x<n;x++) cube[z][y][x]=1;
            for(int x=0;x<n;x++) {
                if(ZX[z][x]=='Y') continue;
                for(int y=0;y<n;y++) cube[z][y][x]=0;
            }
            for(int y=0;y<n;y++) {
                if(YZ[y][z]=='Y') continue;
                for(int x=0;x<n;x++) cube[z][y][x]=0;
            }
            for(int y=0;y<n;y++) {
                for(int x=0;x<n;x++) {
                    if(XY[x][y]=='N') cube[z][y][x]=0;
                }
            }
        }
        memset(com,-1,sizeof(com));
        int k=0;
        for(int z=0;z<n;z++) {
            for(int y=0;y<n;y++) {
                for(int x=0;x<n;x++) {
                    if(com[z][y][x]!=-1||!cube[z][y][x]) continue;
                    dfs(x,y,z,k++);
                }
            }
        }
        if(k==0) {
            for(int z=0;z<n;z++) {
                for(int y=0;y<n;y++) {
                    for(int x=0;x<n;x++) {
                        if(XY[x][y]=='Y'||YZ[y][z]=='Y'||ZX[z][x]=='Y') return "Impossible";
                    }
                }
            }
            return "Possible";
        }
        for(int i=0;i<k;i++) {
            if(check(i,XY,YZ,ZX)) return "Possible";
        }
        return "Impossible";
    }
};

・SRM639 Div1E AliceGame

AとBがいくつかのターンからなるゲームを行う.iターン目にはAとBのいずれかが勝ち,2*i-1点を得る.今,Aがx点,Bがy点であることがわかっている.Aの勝った回数としてあり得る最小の回数を求めよ.という問題.

kターン目が終了した時点で,どんな場合でもAとBの得点の和は1+3+...+2k-1=k^2点である.よってx+yが平方数でない場合はあり得ない.x+y=k^2とすると,今kターン目まで終了したことがわかる.さて,問題は1,3,...,2k-1までのうち和がxとなるよういくつかの数を選ぶとき,最小で何個選べばいいか,ということ.m(0≦m≦k)個の数を選んだとし,i個目に選んだ数を2*a[i]-1(aは単調増加)とすると,(2*a[0]-1)+(2*a[1]-1)+...+(2*a[m-1]-1)=2*(a[0]+a[1]+...+a[m-1])-m=x つまりa[0]+a[1]+...+a[m-1]=(x+m)/2である.よって1以上k以下の数からm個選んで和を(x+m)/2に出来るかの判定問題になった.小さい方からm個選んだ時の和は1+2+...+m=m(m+1)/2で,大きい方からm個選んだときの和はk+(k-1)+...+(k-m+1)=m(2k-m+1)/2.上手く増減させると,和をこの間に入っているどんな数にも出来そうな気がするので書くと通る.

 ソースコード

class AliceGame {
    public:
    long long findMinimumValue(long long x, long long y) {
        long long k;
        if(x+y==0) return 0;
        for(k=1;k*k<x+y;k++);
        if(k*k!=x+y) return -1;
        if(x==0) return 0;
        for(long long i=1;i<=k;i++) {
            if((x+i)%2!=0) continue;
            long long z=(x+i)/2;
            if(i*(i+1)/2<=z && z<=(2*k-i+1)*i/2) {
                return i;
            }
        }
        return -1;
    }
};