D. String Deletion

Educational Codeforces Round 96 (Rated for Div. 2) https://codeforces.com/contest/1430/problem/D

問題

0と1で構成された文字列が与えられる。
に対して2stepからなる操作を何回か適用することを考える。

1. ]を選んで削除する。ただしである。
2. が0で無いならば、の先頭から同じ文字が連続しているカタマリを削除する。

上記の操作を最大で何回行えるか求めよ。

解法

先頭の連続したカタマリをのPrefixと呼ぶ事とする。
最大回数行うためには、1回の操作で出来るだけ文字を消さないようにすれば良いことがわかる。
まず、Prefixは、操作を行うと必ず消えてしまうので]を選んで消すときにPrefixに含まれる場所を選んで消せばPrefixだけを消すだけ済む。
上だけでは、Prefixが1の場合に困ってしまう。次に考えるのは、]を選んだときに別のカタマリから借りてくることである。ここで、安易にPrefixを削除しないのは、100001のような場合にPrefixを削除してしまうと無駄に文字を消してしまうからである。先ほど述べたように削除する要素]を別のカタマリから借りてくれば削除する文字はPrefix(length = 1)と]の2文字だけである。
しかし、よくよく考えると101010のような、別のカタマリから借りてくると損をする場合が存在する。このような場合では、末尾を削除するのが最適である(先頭でも良いが実装では末尾を選択した)。というのも、この場合で末尾および先頭以外を削除すると11010(i=1を削除)のようにPrefixが大きくなってしまって余計に文字を削除してしまうからである。
以上より、この問題は貪欲法で解けます。

実装では、連続するカタマリのサイズを前計算することで処理をやりやすくしている。
先頭より後ろのサイズが2以上のカタマリをqueueに追加している。
後は、順番に前から見ていって、prefixが1より大きかったらprefixのみを削除、prefixが1だったら他のカタマリから借用している。
また、queueの先頭がprefixとなっている場合もしくは1の時はpopしてひとつ後ろのカタマリをqueueの先頭としている。
残りは、上の考察と同じです。

コード

https://codeforces.com/contest/1430/submission/95345916

void solve(){
    int n;
    string s;
    cin >> n >> s;
 
    vector<int> v;
    char cur = s[0];
    int left = 0;
    rep(i, n) {
        if (cur != s[i]) {
            v.push_back(i - left);
            cur = s[i];
            left = i;
        }
    }
    v.push_back(n - left);
 
    queue<int> borrow;
    for (int i = 1; i < v.size(); i++) {
        if (v[i] >= 2) borrow.push(i);
    }
 
    int ans = 0;
    int last = v.size() - 1;
    rep(i, v.size()) {
        if (v[i] == 0) {//empty!
            break;
        }
 
 
        //借りてるidxがprefixになったら外す, 次のに付け替える
        int idx;
        if (borrow.size() != 0) idx = borrow.front();
        if (borrow.size() != 0 && idx == i) {
            borrow.pop();
            if (borrow.size() != 0) idx = borrow.front();
        }
 
        if (v[i] >= 2) {//prefixが2以上
        }
        else if (borrow.size() != 0) {//借りれる
            v[idx]--;
            if (v[idx] == 1) borrow.pop();//これ以上借りれない
        }
        else {//借りる相手がいないので末尾から取る
            if (v[last] < 1) last--;
            v[last]--;
        }
 
        ans++;
    }
    
 
    cout << ans << endl;
}
 
int main() {
    int t;
    cin >> t;
    rep(i, t) solve();
}