問題概要

1 と 2 と 3 のみからなる長さ $N$ の数列が与えられる。同じ数値が 4 個以上連続することはない。

この数列のうちの 1 箇所の値を自由に書き換えることができる。そしてその後、以下の操作を好きな順序で好きな回数だけ繰り返す:

連続して 4 個以上同じ値がある箇所について、それらの数値をまるごと削除する

操作後に残る数列の長さとして、考えられる最小値を求めよ。

制約

$1 \le N \le 10^{4}$

考えたこと

書き換え方法は $O(N)$ 通りある。この手の問題では、それらすべてを愚直に試すと間に合わないことが多いけど、今回はそれぞれ $O(N)$ で解けるなら問題ない。

というわけで、与えられた文字列に対して操作を適切に行って得られる文字列の長さを $O(N)$ で求める方法を考える。

もし「同じ文字が 2 連続している箇所を削除できる」という設定の問題だったならば、有名な「カッコ列整合性判定問題」と一緒

drken1215.hatenablog.com

「4 個以上連続していたら消せる」という設定でも同じようにできる。気になるのが、

1122221133331

というようなケースでは、普通にスタックを使ってやると

11222211
↓
1111
↓
(消去)

というふうになったときに、その後の 33331 の "1" が残ってしまう。このような端の 1 の処理が気になる。

しかし今回はもともとの数列において、「4 箇所以上同じ数値が連続している箇所はない」ということがわかっているので、こういうケースは発生しない。以上から

書き換え方を全パターン試す
書き換えた文字列を、ランレングス圧縮する
同じかたまりの長さが 4 以上なら消失させる
スタックの末尾と合わせて長さ 4 以上になったら消す

という感じで判定できる。

コード

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

int score(const vector<int> &S) {
    vector<pair<int,int>> comp, st;
    for (int i = 0; i < S.size();) {
        int j = i;
        while (j < S.size() && S[j] == S[i]) ++j;
        if (j-i < 4) comp.emplace_back(S[i], j-i);
        i = j;
    }
    for (auto p : comp) {
        if (st.empty()) st.push_back(p);
        else if (st.back().first == p.first) {
            st.back().second += p.second;
            if (st.back().second >= 4) st.pop_back();
        }
        else st.push_back(p);
    }
    int res = 0;
    for (auto p : st) res += p.second;
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<int> S(N);
    for (int i = 0; i < N; ++i) cin >> S[i];
    int res = N;
    for (int i = 0; i < N; ++i) {
        int ori = S[i];
        for (int j = 1; j <= 3; ++j) {
            S[i] = j;
            res = min(res, score(S));
        }
        S[i] = ori;
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 予選 2009 C - 連鎖 (AOJ 0534) (2Q, 難易度 6)

問題概要

制約

考えたこと

コード