StablePairsDiv1 [2018 TCO Algorithm Round 1B Med]

以下のルールを満たす、長さKの配列x,yを構築せよ。

• 1≦x[i]＜y[i]≦N
• y[i]＜x[i + 1]
• (x[i+1]+y[i+1])-(x[i]+y[i])=C
• 上記を満たす配列x,yの中で総和が最大のもの

構築できない場合は空の配列を答える。

解法

貪欲法。
解法に自信が無いが、これしか思いつかなかったので、これで解いたら通った。
　
まず、大きい数から使っていった方が良さそうなので、配列の後ろから順番に数を決めていく。
x[i]とy[i]を決める時にx[i+1],y[i+1]を利用して決める。
y[i]は基本はx[i+1]-1にして、x[i]はsm-y[i]-Cとする。
もし、これが無理ならば、y[i]を小さくしていって、x[i]がおけるようになったら、おくようにする。
これを繰り返して、置けなくなったら構築できない。

struct StablePairsDiv1 {
    vector<int> findMaxStablePairs(int n, int c, int k) {
        vector<int> ans;
        
        int x = n, sm = 0;
        ans.push_back(x);
        sm += x;
        x--;
        if (x == 0) return {};

        ans.push_back(x);
        sm += x;
        x--;

        rep(i, 0, k - 1) {
            while (1) {
                if (x < 2) return {};
                int d = sm - x - c;
                if (d <= 0 or x - 1 < d) {
                    x--;
                    continue;
                }
                break;
            }

            int tot = x;
            ans.push_back(x);
            x--;
            if (x == 0) return {};

            int d = sm - tot - c;
            if (d <= 0) return {};

            if (x < d) return {};

            ans.push_back(d);
            sm = tot + d;
            x = d - 1;
        }

        reverse(all(ans));

        return ans;
    }
};