ECR160-D Array Collapse - zawatinはてなブログ

ECR強化期間

AtCoderは前半解きすぎて残っているセットがほぼない(助けてくれ)。ECRでバチャを走り、セット形式で練習する。バチャ中に解けなかった問題をupsolve/解説ACし、自分の理解をブログに留める。

橙まで、やる気があったら赤diffもACする
ICPCなどでチームメイトに解法を伝える練習も兼ねる

強化期間と銘打っているが、やる気がなくなったらすぐ終わる。この記事でそれっきりかもしれない.....

問題

https://codeforces.com/contest/1913/problem/D (2100diff)

長さ $N$ の数列 $A$ が与えられる。 $A$ はdisjoint。以下の操作を $0$ 回以上行う。

連続する区間を選び、区間内の最小値以外を削除する

最終的にありうる数列の数 $\mod{998244353}$

制約: $N$ がでかい。

解法

dp[i] := $i$ 項までを考慮する。 $i$ 番目の要素を残すように操作を行った時のありうる数列の数。

dp[0] = 1

dp[i] = $\sum_{x\in S_{i}}$ dp[x] ( $S_{i}$ は $a_{j + 1}, a_{j + 2}, \dots, a_{i - 1}$ まで全て消すことができるような操作が存在する値 $j$ の集合

解: $a_{N + 1} = \infty$ として、dp[N + 1]

suffixを全部消して $N + 1$ 項目に飛んでくることができるもの、と考えるとわかりやすかった。

$S_{i}$ がどのような集合か考えると、 $a_{j}, a_{j + 1}, \dots, a_{i}$ の最小値が $a_{j}$ か $a_{i}$ であるような $j$ であると分かる。

そうで無い時、操作によって $a_{k} (j\lt k \lt i)$ が残ってしまうような $k$ が存在する。

$a_{i}$ が最小値となる区間はどうとでもできて、dpの遷移も累積和を持つことでできる。

区間 $a_{j}, a_{j + 1}, \dots, a_{i}$ で $a_{j}$ が最小値となるような $j$ の集合は「 $(a_{1}, a_{2}, \dots, a_{i})$ を後ろから累積minをとったとして、最小値を更新する $j$ の集合(から、 $i$ を取り除いたもの)」である。

そのような集合はstackで得ることができて、dpの総和も同様に管理できるだろう
おそらく、Cartesian Treeの構築と同じ操作をしている(Cartesian Treeを未履修なので本当か微妙だが、こちらの記事を見る感じおそらくそう)

提出コード

#include <bits/stdc++.h>

#include "Src/Template/IOSetting.hpp"
using namespace zawa;

#include "atcoder/modint"
using mint = atcoder::modint998244353;

mint solve() {
    int n; std::cin >> n;
    mint stack_sum{};
    std::stack<std::pair<int, int>> stack;
    std::vector<mint> dp(n), sum(n + 1);
    for (int i{} ; i < n ; i++) {
        int a; std::cin >> a;
        while (stack.size() and stack.top().first > a) {
            stack_sum -= dp[stack.top().second];
            stack.pop();
        }
        if (stack.size()) {
            dp[i] = sum[i] - sum[stack.top().second + 1] + stack_sum;
        }
        else {
            assert(stack_sum == mint{});
            dp[i] = sum[i] + 1;
        }
        sum[i + 1] = sum[i] + dp[i];
        stack_sum += dp[i];
        stack.emplace(a, i);
    }
    return stack_sum;
}

int main() {
    SetFastIO();

    int t; std::cin >> t;
    while (t--) {
        std::cout << solve().val() << '\n';
    }
}

反省

コンテスト中は90分近く残っていたが、dpの発想すらなかった。えぇ....

Cartesian Treeとかは考えていたんだけど、ハズレ方針だった。