るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

SRM 541 Div2

250: AkariDaisukiDiv2

わーいSRMあかりSRM大好きー

class AkariDaisukiDiv2 {
public:
  int countTuples(string S) {
    int result = 0;
    for(int x1 = 0; x1 < S.size(); x1++){
      for(int x2 = x1 + 1; x2 < S.size() - 1; x2++){
	for(int x3 = x2 + 1; x3 < S.size() - 1; x3++){
	  for(int x4 = x3 + 1; x4 < S.size() - 1; x4++){
	  string s1 = S.substr(0,x1 + 1);
	  string s2 = S.substr(x1 + 1,x2 - x1);
	  string s3 = S.substr(x2 + 1,x3 - x2);
	  string s4 = S.substr(x3 + 1,x4 - x3);
	  string s5 = S.substr(x4 + 1);
	  //	  cout<<s1<<","<<s2<<","<<s3<<","<<s4<<","<<s5<<endl;
	  if(s2 == s4) result++;
	  }
	}
      }
    }
    return result;
  }
};


500: AntsMeet

やるだけとか思ってたら、恐ろしいコーナーケースがあってパニック...
他人のコード読んで始めて気づきました..

コーナーケース:
{0,1}
{0,0}
"EW"

class AntsMeet {
public:
  int countAnts(vector <int> x, vector <int> y, string direction) {
    bool alive[100];
    memset(alive,1,sizeof(alive));
    string d = direction;
    rep(i,d.size()){
      x[i] = 2 * x[i];
      y[i] = 2 * y[i];
    }    
    rep(loop,10000){
      rep(i,d.size()){
	if(alive[i]){
	  switch(d[i]){
	  case 'N':
	    y[i]++;
	    break;	    
	  case 'W':
	    x[i]--;	  
	    break;
	  case 'E':
	    x[i]++;
	    break;
	  case 'S':
	    y[i]--;
	    break;
	  }
	}
      }
      rep(i,d.size()){
	if(!alive[i]) continue;
	rep(j,d.size()){
	  if(i == j) continue;
	  if(x[i] == x[j] && y[i] == y[j] && alive[j]) alive[i] = alive[j] = false;
	}
      }
      loop++;
    }
    int res = 0;
    rep(i,d.size()) res += alive[i];
    return res;
  }

};