ICPC2022 国内予選 D問題 - TTRS

解説無しで牛歩考察牛歩実装でなんとかAC出来て楽しいのでメモに残す．

問題

以下のリンクのD問題．
icpc.iisf.or.jp

問題のふんわり考察

$s$ における単調増加列

・ $s$ がゲートに入った際に，分割された後のすべてのグループが単調増加列であった場合，入場時にはすべてソートされた順番で入場する．なぜなら，各グループの先頭は各グループの最小値であり続けるためである．
・逆にこのような状況で $t$ が単調増加列ではない場合，このような $t$ は実現できない．

$s$ における単調減少列

・ $s$ における単調減少列は，それをそのままグループにするとゲートの先でそのままの順番の列（ $s$ に現れる単調減少列そのまま）で入場する．なぜなら先頭の値は後続する値よりも大きいかつ任意の他のグループの先頭より小さいため，先頭の値が選択される時点で次に選ばれるのはそれの後続となるためである．
・言い換えれば， $s$ における単調減少列が $t$ において「そのままの順番で」現れる場合，その単調減少列は必ず同じグループに入れられる必要がある．
→ $s$ と $t$ の両方に現れる単調減少列は，結局その先頭の文字のみと等価である．
→ $s$ と $t$ の両方に現れる単調減少列をともにその先頭の文字で置き換えてもよさそう．
・逆に， $s$ に現れない単調減少列は $t$ において実現できない．なぜなら， $s$ に現れない時点で2つのグループが必要となるが，その際に先頭の文字でソートされてしまい，単調減少列とならないためである．

整理

・ $s$ と $t$ にある単調減少列は先頭の値で置き換えできる．この操作は単調減少列を減らしていく操作とも見える．
・ $s$ の単調減少列がこれ以上減らせない時に $t$ にまだ単調減少列がある場合，そのような $t$ は実現不可
・ $s$ の残っている単調減少列をすべてバラにしてみるとこれはまあ単調増加列だなあ．
・ $s$ のグループがすべて単調増加列である場合は $t$ がソートされた状態になる．

手続き

考察の内容より，以下の処理が浮かぶ．
(1): 以下の処理を繰り返す．
(1.1): $s$ における単調減少列の集合を取り出す．
(1.2): $t$ において $s$ から取り出した単調減少列の部分列となっている場所を取り出す．これを $s$ と $t$ の共通部分単調減少列と呼ぶ．
(1.3): 共通部分単調減少列の長さがすべて1であれば， $t$ がソートされているかを確認する．されていない場合は答えは0である．されている場合はここで処理(1)を終了
(1.4): sとtの共通部分単調減少列を，それぞれの共通部分単調減少の先頭で置き換える．(1.1) にもどる．

(2): $s$ に含まれる極大な単調増加列の集合について，各単調増加列の長さを|Gn|とすると，この問題は「Gnを複数個に分割することを繰り返した際に，結果的に分割数が $k$ 以下となる場合の数の計算」となります．これはdpにより計算できます．
dp[i][j]: i個めのグループを見たときのj個のグループが存在する分割方法
そうすると，
dp[i+1][j+l] += dp[i][j] * |Gi-1| \mathrm{C}_{l-1}
と遷移できる．

具体例での簡単な確認

Sample1

4 2 3 5 1 → 1 3 4 2 5
まず両者に含まれる共通単調減少列を先頭の値で置き換えて，([4, 2] -> [4])
4 3 5 1 → 1 3 4 5
ここで， $t$ はソートされているのでこの $t$ は実現可能．
$s$ における極大な単調増加列の集合は，{{4}, {3, 5}, {1}}である．あとはdpでよしなに

Sample5

2 1 4 3 → 1 4 3 2
共通単調減少列を見る．[4, 3] → [4]と置きかえて

2 1 4 → 1 4 2
もっかい共通単調減少列を見る。そんなものはない...だがソートもされていないからには...どうする？！
これは実現不可能であるので0を出力する．

追加

2 6 1 5 3 4 → 2 5 3 4 6 1
共通単調減少列を見る．[6, 1] → [6], [5, 3]→[5]へと置き換える．
2 6 5 4 → 2 5 4 6
もう一度見る．[5, 4] → [5]へと置き換える．
2 6 5 → 2 5 6
$t$ はソートされている． $s$ における極大な単調増加列の集合は{{2, 6}, {5}}である．

実装の一部

solveの部分だけ載せておきます（includeなどは載せていません）．変な実装ですね

enum class State{
    NG,
    TryAgain,
    End
};

State Find_DecArray_and_erase_if_exists_in_both(int64_t n, vector<int64_t> &s, vector<int64_t> &t) {
    // Sの[L, L+Num)が単調減少列
    // {L, Num}
    vector<pair<int, int>> S_DecreasingArray;
    bool isDecreasing = false;
    int start_decreasing_idx;

    for(int i = 1; i < n; i++) {
        if(s[i-1] > s[i]) {
            if(!isDecreasing) {
                isDecreasing = true;
                start_decreasing_idx = i-1;
            }
        }
        else {
            if(isDecreasing) {
                isDecreasing = false;
                S_DecreasingArray.emplace_back(start_decreasing_idx, i - start_decreasing_idx);
            }
        }
    }
    if(isDecreasing) {
        S_DecreasingArray.emplace_back(start_decreasing_idx, n - start_decreasing_idx);
    }

    // Tに同じ減少列があるかを確認する．
    // 長さ2以上の連続共通部分列があれば先頭の文字以外を溶解する．
    bool Exist_DissolveAble = false;
    // {{Ls, Lt}, Num}
    // Num : 以下を満たす最大
    // S[Ls, Ls+Num) == T[Lt, Lt+Num): 単調減少列
    vector<pair<pair<int, int>, int>> MatchLengthList(S_DecreasingArray.size());
    for(int i = 0; i < S_DecreasingArray.size(); i++) {
        // S[L, R)がTにおいてどれほど一致するかを調べる
        int S_DecArraySize = S_DecreasingArray[i].second;
        int S_DecArrayBeginIdx = S_DecreasingArray[i].first;
        int S_MaxMatch_DecStartMatchingIdx;
        int T_MaxMatch_DecStartMatchingIdx;
        int MaxMatchLength = 1;

        // S[Begin, Begin+Size)とT[k, k+Size)を比較する．．
        for(int k = -S_DecArraySize+1; k < n; k++) {
            int MatchCount = 0;
            int S_StartMatchingIdx;
            int T_StartMatchingIdx;
            for(int j = 0; j < S_DecArraySize; j++) {
                if(k + j < 0) {
                    continue;
                }
                if(k + j >= n) {
                    break;
                }
                if(s[S_DecArrayBeginIdx + j] == t[k + j]) {
                    if(MatchCount == 0) {
                        S_StartMatchingIdx = S_DecArrayBeginIdx + j;
                        T_StartMatchingIdx = k + j;
                    }
                    MatchCount++;
                }
                else {
                    if(MatchCount != 0) {
                        break;
                    }
                }
            }
            if(MaxMatchLength <= MatchCount) {
                S_MaxMatch_DecStartMatchingIdx = S_StartMatchingIdx;
                T_MaxMatch_DecStartMatchingIdx = T_StartMatchingIdx;
                MaxMatchLength = MatchCount;
            }
        }

        MatchLengthList[i] = {{S_MaxMatch_DecStartMatchingIdx, T_MaxMatch_DecStartMatchingIdx}, MaxMatchLength};
        if(MaxMatchLength > 1) {
            Exist_DissolveAble = true;
        }
    }



    // 2個以上の要素を持つ共通部分列が存在しない場合，tがソート済みかを確認
    if(!Exist_DissolveAble) {
        if(!is_sorted(t.begin(), t.end())) {
            return State::NG;
        }
        else {
            return State::End;
        }
    }

    // 溶解処理
    // sにおける共通部分列の開始インデックスをソート
    sort(MatchLengthList.begin(), MatchLengthList.end());
    vector<int64_t> new_s;
    int idx_MatchLength = 0;
    for(int i = 0; i < n; i++) {
        new_s.push_back(s[i]);
        if(idx_MatchLength < MatchLengthList.size() && i == MatchLengthList[idx_MatchLength].first.first) {
            i += MatchLengthList[idx_MatchLength].second - 1;
            idx_MatchLength++;
        }
    }
    // tにおける共通部分列の開始インデックスをソート
    for(auto& d : MatchLengthList) {
        swap(d.first.first, d.first.second);
    }
    sort(MatchLengthList.begin(), MatchLengthList.end());
    vector<int64_t> new_t;
    idx_MatchLength = 0;
    for(int i = 0; i < n; i++) {
        new_t.push_back(t[i]);
        if(idx_MatchLength < MatchLengthList.size() && i == MatchLengthList[idx_MatchLength].first.first) {
            i += MatchLengthList[idx_MatchLength].second - 1;
            idx_MatchLength++;
        }
    }
    s = new_s;
    t = new_t;

    return State::TryAgain;
}

const int MAX_C = 10100;
mint Com[MAX_C][MAX_C];

void calc_com() {
    memset(Com, 0, sizeof(Com));
    Com[0][0] = 1;
    for (int i = 1; i < MAX_C; ++i) {
        Com[i][0] = 1;
        for (int j = 1; j < MAX_C; ++j) {
            Com[i][j] = (Com[i-1][j-1] + Com[i-1][j]);
        }
    }
}

vector<int> Output;
void solve(int64_t n, int64_t k ,vector<int64_t> &s, vector<int64_t> &t) {
    State St;
    while(true) {
        St = Find_DecArray_and_erase_if_exists_in_both(s.size(), s, t);
        if(St != State::TryAgain) {
            break;
        }
    }

    if(St == State::NG) {
        Output.emplace_back(0);
        cout << 0 << endl;
        return;
    }

    vector<mint> Groups;
    mint g_size = 1;
    for(int i = 1; i < s.size(); i++) {
        if(s[i-1] > s[i]) {
            Groups.push_back(g_size);
            g_size = 1;
        }
        else {
            g_size++;
        }
    }
    Groups.push_back(g_size);
    vector<vector<mint>> dp(Groups.size() + 1, vector<mint> (k+1));
    vector<vector<bool>> isValid(Groups.size() + 1, vector<bool> (k+1, false));
    isValid[0][0] = true;
    dp[0][0] = 1;
    for(int i = 0; i < Groups.size(); i++) {
        for(int j = 0; j < k; j++) {
            for(int l = 1; l <= Groups[i].val(); l++) {
                if(j + l > k) {
                    break;
                }
                if(isValid[i][j]) {
                    dp[i+1][j+l] += dp[i][j] * Com[Groups[i].val()-1][l-1];
                    isValid[i+1][j+l] = true;
                }
            }
        }
    }

    mint Ans = 0;
    for(int i = 0; i <= k; i++) {
        Ans += dp[Groups.size()][i];
    }

    cout << Ans.val() << endl;
    Output.push_back(Ans.val());
}

なお，二項係数の実装は以下の記事から引用してます．

drken1215.hatenablog.com