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

るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

SRM 538 Div2

TopCoder

300: LeftOrRight

300にする必要あるかなあ...

左にいってまた右にもどるみたいな操作は必要なさそうだったので、左と右のみに絞ったら通った。(証明はしていない)

class LeftOrRight {
public:
  int F(string s){
    int res = 0;
    int now = 0;
    rep(i,s.size()){
      if(s[i] == 'L') now--;
      else if(s[i] == 'R') now++;
      res = max(res,abs(now));
    }
    return res;
  }
  int maxDistance(string program) {
    string L = program;
    rep(i,L.size()) if(L[i] == '?') L[i] = 'L';
    string R = program;
    rep(i,R.size()) if(R[i] == '?') R[i] = 'R';
    return max(F(L),F(R));
  }
};


500: EvenRoute

どこを通っても良いなら無駄な動きをすれば、常にCANになるだろ みたいな安易な考察が敗因。

簡単な証明とかはここで読んだ
SRM 538 - TopCoder Wiki

class EvenRoute {
public:
  string isItPossible(vector <int> x, vector <int> y, int wantedParity) {
    rep(i,x.size())
      if(abs(x[i] + y[i]) % 2 == wantedParity) return "CAN";
    return "CANNOT";
  }
};