ECR150-E Fill the Matrix

問題

https://codeforces.com/contest/1841/problem/E (diff: 2200)

行列の行列がある。始め列目の行目から行目のマスは黒く、行目から行目のマスは白く塗られている。各マスには値が決められていない。

あなたは、この行列から個の白マスを選んでからの値を割り当てる。

にが、にが割り当てられるようなの数は最大で何個になり得るか求めよ

制約

• 
• は白マスの数を超えない

解法

個横に連続した白ますに値をこの順で割り当てたとする。このとき値だけ解に寄与しない。

このような無駄になってしまう分を減らすには、白ますがより長く連続しているものから貪欲に割り当てれば良い。

白マスの連結成分の長さを列挙 -> ソート とするとTLEしてしまう。

そこで白マスの長方形は一気に使うこととしてシミュレーションを高速化しよう。

実装

#include <bits/stdc++.h>

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

struct M {
    using Element = int;
    static int identity() {
        return 0;
    }
    static int operation(int l, int r) {
        return std::max(l, r);
    }
};

long long solve() {
    int n; std::cin >> n;
    std::vector<int> a(n);
    for (auto& x : a) std::cin >> x;
    long long m; std::cin >> m;
    std::vector<std::set<int>> b(n + 1);
    for (int i{} ; i < n ; i++) b[a[i]].insert(i);
    SparseTable<M> spt(a);
    using qt = std::tuple<int, int, int>;
    std::priority_queue<qt> que;
    for (int i{} ; i < n ; i++) {
        if (a[i] < n) {
            int l{i};
            while (i < n and a[i] < n) i++;
            int r{i};
            que.emplace(r - l, l, n);
        }
    }
    long long ans{};
    while (m) {
        auto [len, l, dn]{que.top()};
        int r{l + len};
        que.pop();
        if (len <= 0) continue;
        auto up{spt.product(l, r)};
        // std::cout << "cur " << m << std::endl;
        // std::cout << "use " << l << ' ' << r << ' ' << dn << ' ' << up << std::endl;
        { // 計算
            long long tate{std::min<long long>(dn - up, m / len)};
            // std::cout << len - 1 << ' ' << tate << std::endl;
            ans += (long long)(len - 1) * tate; 
            m -= (long long)len * tate;
            assert(m >= 0);
            if (tate < dn - up and m > 0) {
                assert(m < len);
                ans += m - 1;
                m = 0;
            }
        }
        if (up > 0) {
            int L{l};
            for (auto it{b[up].lower_bound(l)} ; it != b[up].end() and *it < r ; it++) {
                int R{*it};
                if (R - L > 0) {
                    que.emplace(R - L, L, up);
                }
                L = R + 1;
                if (std::next(it) == b[up].end() or *std::next(it) >= r) {
                    if (r - L > 0) {
                        que.emplace(r - L, L, up);
                    }
                    break; 
                }
            }
        }
    }
    return ans;
}
int main() {
    SetFastIO();

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

感想

• バチャ中は挑む時間すら存在せず。その後ぼんやり考えて自力AC。
• 考察はあまり難しくない。実装が本質の問題だった。