これすごく好き！！！普通に難しい。

問題へのリンク

問題概要

'o' と 'x' のみからなる長さ $N$ の文字列 $S$ を作りたい。部品として使えるのは以下のものたち ( $2A + 2B + C + D = N$ となっている)。

"ox" が $A$ 個
"xo" が $B$ 個
"o" が $C$ 個
"x" が $D$ 個

これらを適切な順序で concat することで、文字列 $S$ にすることが可能かどうかを判定せよ。

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

とりあえず、 $S$ に含まれる 'o' が $A+B+C$ 個、'x' が $A+ B+D$ 個になる必要がある。

それを満たしているとき、部品 "o" と "x" の配置はあとからいくらでも調整が効くので、なるべく "ox" と "xo" を積極的に消費していきたい。逆に $A$ 個の "ox" と $B$ 個の "xo" をすべて、 $S$ 上で、互いに重なり合わないように配置できたならば、残りは "o" と "x" で埋めることができる。

さて、 $S$ において、「"o" が連続している箇所」や「"x" が連続している箇所」に仕切りを入れて分割して考えることにしよう。(仕切りを入れる場所には "ox" や "xo" は配置できない)。そうすると各区間は

"oxox...ox"
"xoxo...xo"
"oxox...o"
"xoxo...x"

のいずれかのパターンとなる。それぞれについて、長さを $2n$ (パターン 1, 2) または $2n-1$ (パターン 3, 4) とする。このとき、"ox" と "xo" の消費可能数を $(a, b)$ で表すことにすると、

$(n, 0)$ と $(a, b)$ ( $a + b = n-1$ ) が可能
$(0, n)$ と $(a, b)$ ( $a + b = n-1$ ) が可能
$(a, b)$ ( $a + b = n-1$ ) が可能
$(a, b)$ ( $a + b = n-1$ ) が可能

というふうになる。基本的には、どのパターンからも合計 $n-1$ 個ずつ作れることがわかる (そして合計が $n-1$ になるような 2 数のパターンは任意)。よって、各区間ごとの「(長さ - 1) / 2」の合計値を $L$ としたとき、 $A+B \le L$ であれば可能と言える。

$A+B \gt L$ となる場合が問題となる。このときは、パターン 1 で $(n, 0)$ を選んだり、パターン 2 で $(0, n)$ を選んだりすることによって、"ox" と "xo" の消費量の合計値を上手に上げていく必要がある。ただし、

パターン 1 で $(n, 0)$ を選ぶならば、それを選んだ $n$ の合計値が $A$ を超えてはならない
パターン 2 で $(0, n)$ を選ぶならば、それを選んだ $n$ の合計値が $B$ を超えてはならない

ということに留意する必要がある。以上から、次のように判定できることがわかる。

まず、すべてのパターンの「(長さ - 1) / 2」の合計値を $L$ とする。

パターン 1 な区間をすべて抽出して、それらの長さを $2l_{1}, 2l_{2}, \dots$ とする。それらから合計値 / 2 が $A$ 以下となるように選べる個数の最大値を $p$ とする

パターン 2 な区間をすべて抽出して、それらの長さを $2r_{1}, 2r_{2}, \dots$ とする。それらから合計値 / 2 が $B$ 以下となるように選べる個数の最大値を $q$ とする

このとき、 $L + p + q \ge A + B$ ならば可能で、そうでなければ不可能である。

計算量は $O(N \log N)$ となる。

コード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

long long N, A, B, C, D;
string S;

bool solve() {
    int maru = 0;
    for (int i = 0; i < N; ++i) if (S[i] == 'o') ++maru;
    if (maru != A + B + C) return false;
    if (N - maru != A + B + D) return false;

    vector<long long> ox, xo, other;
    for (int i = 0; i < N;) {
        int j = i+1;
        while (j < N && S[j-1] != S[j]) ++j;
        if ((j-i) % 2 == 0) {
            if (S[i] == 'o') ox.push_back((j-i)/2);
            else xo.push_back((j-i)/2);
        }
        else other.push_back((j-i)/2);
        i = j;
    }
    sort(ox.begin(), ox.end());
    sort(xo.begin(), xo.end());
    int num = 0;
    long long oxsum = 0, xosum = 0, otsum = 0;
    for (int i = 0; i < ox.size(); ++i) {
        if (oxsum + ox[i] <= A) ++num;
        oxsum += ox[i];
    }
    for (int i = 0; i < xo.size(); ++i) {
        if (xosum + xo[i] <= B) ++num;
        xosum += xo[i];
    }
    for (int i = 0; i < other.size(); ++i) otsum += other[i];
    if ((oxsum - (int)ox.size()) + (xosum - (int)xo.size()) + otsum + num >= A + B)
        return true;
    return false;
}

int main() {
    while (cin >> N >> S >> A >> B >> C >> D) {
        if (solve()) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

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

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

CPSCO2019 Session4 E - ox Concatenation (600 点設定)

問題概要

制約

考えたこと

コード