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

SRM 596 Div2 Medium ColorfulRoad

問題

SRM 596 - TopCoder Wiki

道路がN区画に区切られ,0からN-1に到達したい. 各区画はRGBの各3色で塗られ,Rの次はG,Gの次はB,Bの次はRという風な順番で移動しなくてはいけない. また移動コストは各ポジションの差の2乗となる. 0からN-1に移動する時の最小コストを求める問題. もし移動できなければ-1を返す.

解答

入力長が15と短かったので力づくで解いた. 使った区画をすべて考え,コストを計算し,最小のコストを返す.

class ColorfulRoad
{
public:
  int getMin(string road)
    {
      int i, j;
      int n = road.size();
      int res = INT_MAX;
      string rotation = "RGB";
      for(i = (1 << (n-1)); i < (1 << n); i++){
        int prev = 0;
        int prev_pos = 0;
        int cost = 0;
        for (j = 1; j < n; j++)if ((i >> j) & 1){
            if (rotation[(prev + 1)%3] == road[j]){
              cost += (j - prev_pos) * (j - prev_pos);
              prev = (prev + 1) % 3;
              prev_pos = j;
            }else{
              cost = INT_MAX;
              break;
            }
        }
        if (prev_pos == (n-1)){
          // if (cost == 0){
          //   std::cout << static_cast<std::bitset<8> >(i) << std::endl;
          // }
          res = min(res, cost);
        }
      }
      if (res == INT_MAX) return -1;
      return res;
    }
};