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

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

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

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

問題概要

'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" は配置できない)。そうすると各区間

  1. "oxox...ox"
  2. "xoxo...xo"
  3. "oxox...o"
  4. "xoxo...x"

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

  1.  (n, 0) (a, b) ( a + b = n-1) が可能
  2.  (0, n) (a, b) ( a + b = n-1) が可能
  3.  (a, b) ( a + b = n-1) が可能
  4.  (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;
    }
}