読者です 読者をやめる 読者になる 読者になる

るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

SRM 550 Div2

TopCoder

250: EasyConversionMachine

無駄な操作を除いた必要最低限の回数に2回ずつの無駄な操作を追加してkにできればPOSSIBLE

class EasyConversionMachine {
public:
  string isItPossible(string originalWord, string finalWord, int k) {
    int need = 0;
    rep(i,originalWord.size())
      if(originalWord[i] != finalWord[i]) need++;
    if(need > k) return "IMPOSSIBLE";
    if(need == k) return "POSSIBLE";
    if((k - need) % 2 == 0) return "POSSIBLE";
    return "IMPOSSIBLE";    
  }
};


550: RotatingBot

高さと幅は座標の最大、最小から求まる。(ここで止めていて間違えてしまった)
不正なデータ(曲がれないところで曲がる、一度通ったところを通るなど)が無いかを確認する。

const int dx[] = {1,0,-1,0},dy[] = {0,-1,0,1};
class RotatingBot {
public:
  int minArea(vector <int> moves) {
    int x = 64,y = 64;
    int minX = x, maxX = x,minY = y,maxY = y;
    rep(i,moves.size()){
      x += dx[i % 4] * moves[i];
      y += dy[i % 4] * moves[i];
      minX = min(minX,x);
      maxX = max(maxX,x);
      minY = min(minY,y);
      maxY = max(maxY,y);
    }
    int W = maxX - minX;
    int H = maxY - minY;
    if(W > 50 || H > 50) return -1;
    int flag[200][200]; memset(flag,0,sizeof(flag));
    rep(i,200)
      flag[minY - 1][i] = flag[maxY + 1][i] = flag[i][minX - 1] = flag[i][maxX + 1] = true;
    x = 64,y = 64;
    flag[y][x] = true;
    for(int i = 0; i < moves.size(); i++){
      for(int j = 0; j < moves[i]; j++){
	x += dx[i % 4];
	y += dy[i % 4];
	if(flag[y][x]) return -1;
	flag[y][x] = true;
      }
      if(i == (moves.size() - 1)) break;
      if(!flag[y + dy[i % 4]][x + dx[i % 4]]) return -1;
    }
    return (W + 1) * (H + 1);
  }

};