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

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

AtCoder AGC 026 E - Synchronized Subsequence (赤色, 1600 点)

こういうのちゃんと解き切れるようになりたい...

なんだろ、「'a' と 'b' の個数が等しくなるような区間ごとに分割する」という発想がちゃんと出て来るようにするためには、どういう流れの考察をすればよいのだろう...

問題へのリンク

問題概要

N 個の 'a' と N 個の 'b' からなる長さ 2N の文字列 S が与えられる。 {0, 1, ..., N-1} の部分集合 V であって、

  • V に含まれる各 i について、S の中で i 番目の a と i 番目の b を抜き取ってくる
  • それらを S 中で登場する順に concat する

という操作で得られる文字列が辞書順最大となるものを求めよ。

制約

  • 1 <= N <= 3000

考えたこと

i = 0, 1, 2, ..., N-1 に対して、i 番目の 'a', 'b' の index を p_i, q_i とすると

  • p_i > q_i
  • p_i < q_i

のどちらかになる。まずはこのどちらかしか登場しないパターンを解いてみる。

すべてが p_i > q_i ('a' が先んじる) のとき

最初の 1 文字目はどんなに頑張っても 'a' になる。その次に 'a' が来るのは損なので最初に選んだ 'a' のペア 'b' が登場するまで 'a' を全部飛ばして、'b' を回収する。

そして、その 'b' の後ろにある 'a' をまたどれか選んで、そのペア 'b' を回収して... を繰り返す感じになる。

最終結果は "abababababab" という感じになる。この長さが長ければ長いほどよい。よって、毎回の 'a' の選び方は Greedy に一番前からとっていけばよい。

すべてが p_i < q_i ('b' が先んじる) のとき

最初はとにかく 'b' をたくさん並べたい気持ちになる。だから、'b' から見て相方の 'a' がなるべく遠くにあるやつを選んで...でも tie があったら...とか考えて迷宮入りしてしまった。

まず、i 番目の 'b' ( q_i) を選んだとして  q_{i+1} の登場の仕方が 2 パターンあることに注目する:

  •  q_{i+1} <  p_{i} のとき: 問答無用で i+1 番目の 'b' も回収するのがいい
  •  q_{i+1} >  p_{i} のとき: i+1 番目の 'b' も回収するべきかどうか定かでない

この状況から以下のような発想ができるかどうか... (ここがまだ自分には厳しい)


 q_{i+1} >  p_{i} になるときというのは、i 番目の 'a' の地点で一旦

  • 'b' と 'a' の個数が一緒になる

という状況になる。そこで文字列全体を「'b' と 'a' の個数が等しい」ような区間ごとに分割して考える。


各区間については、

  • ある地点での 'b' を回収したならば、そこから先の 'b' はすべて回収した方がよい (どの 'b' についてもそのペアとなる 'a' を回収する前にその先の 'b' を回収できるため)

ということが言える。このことを利用すれば、各区間についての辞書順最大の文字列は、'b' 回収の開始時点を全探索すれば求められる。これにはナイーブには  O(N^{2}) でできる。Suffix Array を用いれば  O(N) でもできそう。

そうして各区間についての辞書順最大の文字列を求めておいて、区間全体の辞書順最大を求めるためには DP をすればよい。

DP

文字列を値にもつ辞書順最大 or 最小を求める DP では、後ろからやるのが定石ではある。なぜなら S, T, add を文字列として

  • max(S + add, T + add) = max(S, T) + add

は文字列の concat については必ずしも成り立つとは限らないが、

  • max(add + S, add + T) = add + max(S, T)

は成立する。各区間について辞書順最大の文字列が

S1, S2, ..., Sk

と求められているとき、各文字列を採用するかどうかを後ろから DP しながら求めていけばよい。なお、各区間からとってくる文字列として「その区間の辞書順最大」と「空文字列」のみを考えればよいことは、以下の性質を用いて示せる (beet さんの記事参照):


文字列 X と Y が互いに prefix の関係にないとする。このとき任意の文字列を T として

X < Y ならば X+T < Y+T

が成立する


なお、この DP は文字列比較を含むために  O(N^{2}) であるが、以下のような Greedy でもよくて、Suffix Array を組み合わせれば  O(N) でもできる。

  • pair(Si, -i) が最大のものをまず選ぶ
  • i より大きい範囲の j について pair(Sj, -j) が最大のものを選ぶ。以後これを繰り返す

全体

ここまで来れば大体もう解けている。

index を後ろから見ていったときに、「p_i < q_i ('b' が先んじる)」型の i が一度でも登場したら、それより前の index の「p_i > q_i ('a' が先んじる)」型はすべて無視してよい (使うと辞書順が下がってしまうため)。

よって、無視作業を含めると

  • 前半は「p_i < q_i」型のみ
  • 後半は「p_i > q_i」型のみ

という風にになる。前半と後半それぞれ辞書順最大を持って来て concat すればよい (それでよいことは比較的容易に示せる)

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

int N;
string S;

string subSolve(const string &s) {
    if (s[0] == 'a') {
        string res = "";
        int prev_a = -1;
        int a_num = 0, b_num = 0;
        bool search_a = true;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == 'a') {
                if (search_a) {
                    res += "a";
                    prev_a = a_num;
                    search_a = false;
                }
                ++a_num;
            }
            else {
                if (!search_a) {
                    if (b_num == prev_a) {
                        res += "b";
                        search_a = true;
                    }
                }
                ++b_num;
            }
        }
        return res;
    }
    else {
        string res = "";
        for (int i = 0; i*2 < s.size(); ++i) {
            string tmp = "";
            int a_num = 0, b_num = 0;
            for (int j = 0; j < s.size(); ++j) {
                if (s[j] == 'a') {
                    if (a_num >= i) tmp += s[j];
                    ++a_num;
                }
                else {
                    if (b_num >= i) tmp += s[j];
                    ++b_num;
                }
            }
            res = max(res, tmp);
        }
        return res;
    }
}

int main() {
    cin >> N >> S;
    int iter = 0;
    vector<string> vec;
    string tmp = "";
    bool exist = false;
    for (int i = (int)S.size()-1; i >= 0; --i) {
        tmp += S[i];
        if (S[i] == 'a') ++iter;
        else --iter;
        if (iter == 0) {
            reverse(tmp.begin(), tmp.end());
            if (tmp[0] == 'a' && exist) { tmp = ""; continue; }
            if (tmp[0] == 'b') exist = true;
            string ma = subSolve(tmp);
            vec.push_back(ma);
            tmp = "";
        }
    }
    
    vector<string> dp; dp.assign(N+1, "");
    for (int i = 0; i < vec.size(); ++i) {
        dp[i+1] = max(dp[i+1], dp[i]);
        dp[i+1] = max(dp[i+1], vec[i] +dp[i]);
    }
    cout << dp[vec.size()] << endl;
}