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; } };