Codeforces Round #480 div2-C Posterized

  • 問題概要

[0,255]を連続する数字ごとにいくつかのグループに分ける。各グループの大きさはk以下である。
各グループに対してそのグループに属する1つの数がkeyとして扱われる。
n個の数字v_i(0≦v_i≦255)が与えられ、返されるn個のkeyが辞書順最小になるようにグループを作るとする。
このときの各keyを求めよ。

  • 解法

まずkeyは各グループ内の最小値としていい。辞書順最小だから前から順に貪欲に考えていけばよく、あるv_iに対してkeyが最小になるのはグループのsizeをk以下に保ったままグループを左に拡大していくときである。
(例 v_i=5,k=3のときグループは{5}→{4,5}→{3,4,5})と拡大していく。)
この操作はグループ内の最小値iに対してuf.unite(i,i-1)を順次行っていけばいい。
sizeをk以下に保つことはuf.size(i)+uf.size(i-1)<=kが対応する。

struct uf_tree {
    std::vector<int> parent;
    int __size;
    uf_tree(int size_) : parent(size_, -1), __size(size_) {}
    void unite(int x, int y) {
        if ((x = find(x)) != (y = find(y))) {
            if (parent[y] < parent[x]) std::swap(x, y);
            parent[x] += parent[y];
            parent[y] = x;
            __size--;
        }
    }
    bool is_same(int x, int y) { return find(x) == find(y); }
    int find(int x) { return parent[x] < 0 ? x : parent[x] = find(parent[x]); }
    int size(int x) { return -parent[find(x)]; }
    int size() { return __size; }
};

int a[256];
int n;
int main() {
    cin>>n>>k;
    vector<int> v(n);
    for(auto &x : v)cin>>x;
    uf_tree uf(256);
    for(auto &x : v) {
        int i = x;
        while (1) {
            if (i == 0)break;
            else if (uf.find(i) == uf.find(i - 1))i--;
            else if (uf.size(i) + uf.size(i - 1) <= k)uf.unite(i, i - 1);
            else break;
        }
    }
    MEMINF(a);//aを大きい値で初期化
    rep(i, 256)chmin(a[uf.find(i)], i);//各グループ内における最小値を記録
    for(auto &x : v)cout << a[uf.find(x)] << " ";
}