LineOff [2018 TCO Algorithm Round 1B Easy]

文字列Sがある。
この文字列に以下の操作を最大何回行えるか。
「2つの隣接する文字が等しいなら、2つの文字を消す」

考察

1. TCOのRound1のEasyなので、簡単めな解法だろうという線から考える
2. DPとかで解くのも難しそう
3. 貪欲しか無いのでは？
4. 適当に操作してもあんまし結果変わらない？

解法

貪欲法で解く。
貪欲に操作を行っていくだけ。

struct LineOff {
    int movesToDo(string points) {
        int ans = 0;
        string s = points;

        while (1) {
            int ng = 1;
            int n = s.length();
            rep(i, 0, n - 1) if (s[i] == s[i + 1]) {
                string ss = "";
                if(i) ss += s.substr(0, i);
                if(i + 2 < n) ss += s.substr(i + 2);

                s = ss;
                ans++;
                ng = 0;
                
                break;
            }

            if (ng) return ans;
        }
    }
};