いろいろがんばりたいブログ

情報科学科の人がいろいろ書きます。

SRM 551 Div2

練習。

250 ColorfulBricks
種類が3つ以上あれば、必ず交わる場所が2箇所はある。
種類が2つであれば、exampleにあるように2パターン。
種類が1つであれば、exampleにあるように1パターン。
setを使うと楽。

class ColorfulBricks {
    public:
        int countLayouts( string bricks ) {
            set<char> alr;
            for(int i=0;i<bricks.size();i++){
                alr.insert(bricks[i]);
            }
            if(alr.size() == 1){
                return 1;
            }else if(alr.size() == 2){
                return 2;
            }else{
                return 0;
            }
        }
};

500 ColorfulChocolates
ものすごく長くなってしまった。
方針は、ある場所を選んで、そこを中心として左、右に近い方へのばしていく。
問題は、どうやってその距離を選ぶのかという点で、

ABBBAA

というのがあった時、仮に0番目のAを真ん中にすることにした場合、
左から4番目のAはswapが3回。左から5番目のはswapが3回と計算する。
なぜそうするかというと、5番目のAをつける前には必ず4番目のAをつけるからで、そうした場合、右の範囲が1ひろがるためである。
Editorialsを見たらもっと簡単でしょんぼり。

class ColorfulChocolates{
public:
    int maximumSpread(string chocolates, int maxSwaps){
        int ret = 0;
        for(char cc='A';cc<='Z';cc++){
            for(int i=0;i<chocolates.size();i++){
                if(cc != chocolates[i]) continue;
                int left,right;
                for(int j=i;j>=0;j--){
                    if(chocolates[j] == cc){
                        left=j;
                    }else{
                        break;
                    }
                }
                for(int j=i;j<chocolates.size();j++){
                    if(chocolates[j] == cc){
                        right=j;
                    }else{
                        break;
                    }
                }
                vector<int> dist;
                int lc=0,rc=0;
                for(int j=0;j<chocolates.size();j++){
                    if(chocolates[j] == cc){
                        if(left <= j and j <= right){
                            dist.push_back(0);
                        }else if(right < j){
                            dist.push_back(j-right-1-rc);
                            rc++;
                        }
                    }
                }
                for(int j=left-1;j>=0;j--){
                    if(chocolates[j] == cc){
                        dist.push_back(left-j-1-lc);
                        lc++;
                    }
                }
                sort(all(dist));
                cerr << left << " " << right << endl;
                for(int d=0;d<dist.size();d++){
                    cerr << dist[d] << (d==dist.size()-1?"\n":" ");
                }
                int now = 0;
                int mret = 0;
                for(int i=0;i<dist.size();i++){
                    if(now + dist[i] > maxSwaps){
                        break;
                    }else{
                        mret++;
                        now += dist[i];
                    }
                }
                ret = max(ret,mret);
            }
        }
        return ret;
    }
};

950 ColorfulCupcakesDivTwo
がんばってDPした。
ways[Aの残り][Bの残り][Cの残り][前に選んだの][最初に選んだの]でDPできた。

const ll MOD = 1000000007;
class ColorfulCupcakesDivTwo{
public:
    int countArrangements(string cupcakes){
        int N = cupcakes.size();
        ll ret = 0;
        ll cnt[3] = {0};
        for(int i=0;i<cupcakes.size();i++){
            cnt[cupcakes[i]-'A']++;
        }
        ll ways[cnt[0]+1][cnt[1]+1][cnt[2]+1][3][3];
        memset(ways,0,sizeof(ways));
        ways[cnt[0]-1][cnt[1]][cnt[2]][0][0] = cnt[0] != 0;
        ways[cnt[0]][cnt[1]-1][cnt[2]][1][1] = cnt[1] != 0;
        ways[cnt[0]][cnt[1]][cnt[2]-1][2][2] = cnt[2] != 0;

        for(int al=N-1;al>=1;al--){
            for(int i=0;i<=cnt[0];i++){
                for(int j=0;j<=cnt[1];j++){
                    for(int k=0;k<=cnt[2];k++){
                        if(i + j + k == al){
                            //before
                            for(int l=0;l<3;l++){
                                // first
                                for(int m=0;m<3;m++){
                                    // next
                                    for(int n=0;n<3;n++){
                                        if(n == l) continue;
                                        if(al == 1 and n == m) continue;
                                        if(n == 0 and i!=0){
                                            ways[i-1][j][k][n][m] += ways[i][j][k][l][m];
                                            ways[i-1][j][k][n][m] %= MOD;
                                        }
                                        if(n == 1 and j!=0){
                                            ways[i][j-1][k][n][m] += ways[i][j][k][l][m];
                                            ways[i][j-1][k][n][m] %= MOD;
                                        }
                                        if(n == 2 and k!=0){
                                            ways[i][j][k-1][n][m] += ways[i][j][k][l][m];
                                            ways[i][j][k-1][n][m] %= MOD;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                ret = (ret + ways[0][0][0][i][j]) % MOD;
            }
        }
        return ret;
    }
};