ColorfulTilesEasy srm 472 div2 easy

program topcoder
  • 結構考えて、時間ぎりぎりで解答が分かった。
  • 列の中で同じ色が続いている部分を「連」と呼ぶことにする。色が4色あるので、連の両サイドがどんな色だったかを気にせずに必ず「(連の長さ) / 2」ステップで連の内部及び連の両端で同じ色が連続しないように出来る(但し、端数切り捨て)。
  • 連の内部の同色連続は必ず解消しないといけないので、この手順で得られる手数は最小。
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


class ColorfulTilesEasy{
public:
  int theMin(string room){
    int ret = 0;
    int n = room.size();
    room += "A";
    int start, end;
    start = 0;
    while(start < n){
      end = start + 1;
      while(room[start] == room[end]){
	end++;
      }
      ret += (end - start) / 2;
      start = end;
    }
    return ret;
  }



};