[Codeforces] Educational Codeforces Round 96 (Div. 2) D. String Deletion

2020年10月12日2020年12月12日

問題

方針

あまり理解していませんが、操作 1. で選ぶ文字は、同じ文字が連続する部分文字列のなかで一番左のものを選ぶみたいです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string s;
int n;

void solve() {
    vector<int> v;
    v.push_back(1);
    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) {
            v.back() += 1;
        } else {
            v.push_back(1);
        }
    }
    int cnt = 0;
    int r = 0;
    int m = v.size();
    for (int l = 0; l < m; l++) {
        while (r < m && v[r] <= 1) r++;
        if (r == m) {
            cnt += (m - l + 1) / 2;
            break;
        }
        if (v[r] >= 2) {
            v[r]--;
        } else {
            while (r < m && v[r] <= 1) r++;
            if (r == m) {
                cnt += (m - l + 1) / 2;
                break;
            }
            v[r]--;
        }
        v[l] = 0;
        cnt++;
    }
    cout << cnt << "\n";
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n >> s;
        solve();
    }
    return 0;
}

感想

貪欲法は難しい。