るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

SRM 551 Div2

思いつかないと解けないセットだったと思う。頭の悪い僕にとっては結構難しかった


250: ColorfulBricks

使われている文字の種類が2種類以上だと成り立たない。

class ColorfulBricks {
public:
  int countLayouts(string bricks) {
    int res = 0;
    int r[26];
    memset(r,0,sizeof(r));
    rep(i,bricks.size()) r[bricks[i] - 'A']++;
    int kind = 0;
    rep(i,26)
      if(r[i] > 0)kind++;
    if(kind == 1) return 1;
    if(kind == 2) return 2;
    return 0;
  }
};


500: ColorfulChocolates

文字を固定して、何回swapが必要かを全探索する。

class ColorfulChocolates {
public:
  int maximumSpread(string chocolates, int maxSwaps) {
    int N = chocolates.size();
    int res = 0;
    rep(i,N){
      rep(j,N){
	char c = chocolates[i];
	int r = i,l = j;
	int cost = 0;
	int ans = 0;
	while(r < N){
	  if(abs(r - l) + cost > maxSwaps) break;
	  cost += abs(r - l);
	  r++;
	  ans++;
	  while(r < N && chocolates[r] != c) r++;
	  l++;
	}
	res = max(res,ans);
      }
    }
    return res;
  }