[アルゴリズム]Algospot QUANTiZE

ソース:https://www.algospot.com/judge/problem/read/QUANTIZE

質問する

量子化(Quantization)プロセスとは、より広い範囲の値をより小さな範囲の値として近似することによって、資料を圧縮するプロセスである.例えば、16ビットJPGファイルを4色GIFファイルに変換することは、RGB色空間の色を4色の1つに量子化することであり、身長161、164、170、178の4人の生徒を「160対2、170対2」と略し、量子化ともいえる.
1000以下の自然数からなる数列を最大Sクラスのみを使用する値に量子化したい.このとき量子化された数字は、もともと数列に含まれていない数字かもしれません.量子化の方法はいろいろあります.数列1 2 3 4 5 6 7 8 9 10を2つの数字だけで表すと、3 3 3 3 3 3 7 7で表すこともできるし、1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 10 10で表すこともできる.ここで,各数値の誤差二乗和を最小化した量子化結果を知りたい.
例えば、数列1 2 3 4 5は1 1 3 3に量子化され、誤差二乗の和は0+1+0+1+4=6、2 2 2 4は誤差二乗の和は1+0+1+0+1=3となる.
数列とSが与えられた場合、誤差二乗和の最小値を求めるプログラムを作成します.

入力

入力された最初の行は、試験例の数C(1<=C<=50)を与える.各テストケースの最初の行には、数列の長さN(1<=N<=100)、使用する数字S(1<=S<=10)が与えられる.次の行はN個の整数で数列の数字を与えます.数列のすべての数は1000以下の自然数です.

しゅつりょく

各試験例において、与えられた数列を最大S個数に量子化すると、誤差二乗和の最小値が出力される.

正しいコード

#include <bits/stdc++.h>
#define FASTio ios_base ::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'

using namespace std;

int n, s;

int sum[101];
int psum[101];

void miri(vector<int> &v)
{
    sum[0] = v[0];
    psum[0] = v[0] * v[0];

    for (int i = 1; i < v.size(); i++)
    {
        sum[i] = sum[i - 1] + v[i];
        psum[i] = psum[i - 1] + v[i] * v[i];
    }
}

int abs(int lo, int hi)
{
    int tsum = sum[hi] - (lo == 0 ? 0 : sum[lo - 1]);
    int tpsum = psum[hi] - (lo == 0 ? 0 : psum[lo - 1]);

    int m = int(0.5 + (double)tsum / (hi - lo + 1));

    int ret = tpsum - 2 * m * tsum + m * m * (hi - lo + 1);
    return ret;
}

int cache[101][11];

int quantize(int from, int parts)
{
    if (from == n)
        return 0;

    if (parts == 0)
        return 987654321;

    int &ret = cache[from][parts];

    if (ret != -1)
        return ret;

    ret = 987654321;

    for (int partSize = 1; from + partSize <= n; ++partSize)
        ret = min(ret, abs(from, from + partSize - 1) + quantize(from + partSize, parts - 1));

    return ret;
}

int main()
{
    FASTio;

    int t;

    cin >> t;

    while (t--)
    {
        cin >> n >> s;

        vector<int> seq(n, 0);

        memset(cache, -1, sizeof(cache));

        for (int i = 0; i < n; i++)
            cin >> seq[i];

        sort(seq.begin(), seq.end());

        miri(seq);

        cout << quantize(0, s) << endl;
    }

    return 0;
}

解答と思考過程

考えが浮かんだが、実施中に問題にぶつかった...
この問題は3日前にやったので,はっきり覚えていない.
今度すぐブログに行きます.