問題

問題概要

英小文字のみで構成された長さ $n$ の文字列 $s$ がある。これに対して、 $i$ 回目の操作では長さ $2^{i-1}$ の $s$ の連続する部分列を切り取り、残った部分を連結して $s$ とする、ということを $s$ がなくなってしまう直前まで行う(つまり回数を $k$ とすると、 $k= \lfloor \log_{2} n \rfloor$ )。

$k$ 回操作した後にあり得る文字列の中で辞書順最小のものを答えよ。

$1 \le n \le 5000$

アイデア

まず、 $n \le 5000$ であることから、行われる操作の回数はたかだか12回であるという事実と、入れ子になっているような削除操作は入れ子にならないように分解できるので、削除する区間は元の文字列でも連続していると考えてしまって構わない。

以上のことからdp[i][mask] := i文字目まで決定済み、削除操作はmaskの状態で行った時の答え(=辞書順最小の文字列)ということを考えると、状態数が $O(n^2)$ なので間に合いそうに見えるが、陽に文字列を持とうとすると、1状態辺りで $O(n)$ の空間を使用することになり、MLE,TLEが発生すると考えられる。

今、上で考えたことに対して、dp配列の中に入っているのはこの問題の答えの候補に対するprefixが入っていることになる。そこで、違う状態だが、このprefixの長さが同じである2状態に注目してみる(dp[i1][mask1] と dp[i2][mask2] とする)(ちなみに、この状態(i,mask)に対してprefixの長さは一意に定まるし、簡単に計算できる)。

さて、このprefixの時点でdp[i1][mask1] と dp[i2][mask2]に大小関係がついていたら、大きい方についてはそれ以降の遷移を考えるのは無駄である。何文字目まで見ていようが、その時点でprefixが小さい方を選ばなければ、大きい方をそれ以降いくら頑張って選んでも小さい方の後ろに適当にくっつけたものでさえ敵わないからである。(辞書順最小はとこのようなgreedyなアプローチと相性が良い(要出典))。

そうすると、各状態について陽に文字列を保つ必要はなく、この状態は最小に到達できうるか否かを持てば良いということになる。遷移の順番をどうすればいいのかで悩んだが、状態に対してprefixの長さが決まるので、これが短い順に遷移していき、それと同時に1文字ずつ答えを決定していけば良い。 $n$ に対して、最終状態の文字の長さも一意に定まるので、その文字に到達すれば終了とすれば良い。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const int N = 5005;
const int M = 1<<12;
bool dp[N][M]={};

using pi = pair<int,int>;
vector<pi> Q[N];

int main(){
    string s;
    cin >>s;

    int n = s.size();

    // finally len(s) becomes F
    int F = n;

    int m = 0;
    while(1){
        int sub = 1<<m;
        if(F - sub <= 0) break;
        F -= sub;
        ++m;
    }

    // calcurate prefix lemgth for states
    rep(i,n)rep(mask,1<<m){
        int L = i;
        rep(j,m)if(mask>>j&1) L -= (1<<j);
        if(0<=L && L<F) Q[L].pb({i,mask});
    }

    dp[0][0] = true;

    string ans = "";
    // decide ans[i]
    rep(i,F){
        // propagete dp state
        for(const auto &p: Q[i]){
            int idx = p.fi, mask = p.se;
            if(!dp[idx][mask]) continue;

            // erase operateion
            rep(j,m)if(!(mask>>j&1)){
                int nidx = idx+(1<<j);
                int nmask = mask|(1<<j);
                dp[nidx][nmask] = true;
            }
        }

        // decide answer
        char c = 'z';
        for(const auto &p: Q[i])if(dp[p.fi][p.se]) c = min(c, s[p.fi]);
        ans += c;

        // propagete to next state
        for(const auto &p: Q[i])if(dp[p.fi][p.se]){
            if(c == s[p.fi]) dp[p.fi+1][p.se] = true;
        }
    }

    cout << ans << endl;
    return 0;
}

裏紙

ほぼ競プロ、たまに日記

CF 938 F - Erasing Substrings

問題

問題概要

アイデア

実装(C++)