るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

SRM 558 Div2

一応本番も出ていましたが、Easyしか通せませんでした....orz

解きなおし



250: SurroundingGameEasy

誤読すると氏ぬ

bool d[100][100];
class SurroundingGameEasy {
public:
  int score(vector <string> cost, vector <string> benefit, vector <string> stone) {
    memset(d,0,sizeof(d));
    int width = stone[0].size();
    int height = stone.size();
    rep(y,stone.size()){
      rep(x,stone[y].size()){
	if(stone[y][x] == 'o'){
	  d[x][y] = true;
	}else{
	  bool isd = true;
	  rep(i,4){
	    int nx = x + dx[i];
	    int ny = y + dy[i];
	    if(0 <= nx && nx < width && 0 <= ny && ny < height){
	      if(stone[ny][nx] != 'o'){
		isd = false;
		break;
	      }
	    }
	  }
	  if(isd) d[x][y] = true;
	}
      }
    }
    int be_sum = 0,c_sum = 0;

    rep(y,stone.size())
      rep(x,stone[y].size())
	if(d[x][y]) be_sum += benefit[y][x] - '0';
    rep(y,stone.size())
      rep(x,stone[y].size())
      if(stone[y][x] == 'o') c_sum += cost[y][x] - '0';
    
    return be_sum - c_sum;
  }

};


600: Stamp

やるだけとか思ってたけど、書いてみるとかなり時間がかかった... (どのみち本番では絶対に解けなかった)

区間dpっぽいことをする。 まったく同じ区間に同じ色を塗るというパターンは明らかに必要ないので、一つづつ区間をづらしていって部分最適解を求めていく。上限と下限でミスが起こりやすいと思う。


int dp[100][4];
int N;
string S;
char col[3] = {'R','G','B'};
class Stamp {
public:
  bool CanPaint(int l,int r,int c){
    for(int i = l; i < r; i++)     
      if(S[i] != '*' && S[i] != col[c]) return false;
    return true;
  }
  int Calc(int L){
    rep(i,100) rep(j,4) dp[i][j] = INF;    
    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    
    for(int i = L; i <= N; i++){
      for(int c = 0; c < 3; c++){
	int l = i - L;
	int r = i;
	if(CanPaint(l,r,c)){
	  int mn = INF;
	  rep(k,3) mn = min(mn,dp[l][k]); //何でも塗れる
	  for(int x = i - L; x < i; x++)//重なっている
	    mn = min(mn,dp[x][c]);
	  if(mn != INF)
	    dp[i][c] = mn + 1;
	}
      }
    }
    return min(dp[N][0],min(dp[N][1],dp[N][2]));
  }
  int getMinimumCost(string desiredColor, int stampCost, int pushCost) {
    N = desiredColor.size();
    S = desiredColor;
    int result = INF;
    for(int L = 1; L <= N; L++){
      int c = Calc(L);
      if(c < INF)
	result = min(result,stampCost * L + pushCost * c);
    }
    return result;
  }
};

Hardが簡単だったらしいのでそのうち解きます