SRM684 Div.1 Easy(250) CliqueParty

問題

TopCoder Statistics - Problem Statement

集合aは異なる正の整数からなる。aの部分集合に含まれる任意の要素の組(A, B)に対し、|A-B|を要素とする集合をDとする。Dがk-smoothとなるようなaの部分集合の最大の要素数を答えよ。ただしk-smoothとは、集合に含まれる任意の要素の組(A, B)に対し、A <= k * Bが成立することである。

制約

aの要素数: 2以上50以下

解法

集合Dがk-smoothであることは、Dの最大要素maxdiff, 最小要素mindiffに対してmaxdiff <= k * mindiffが成り立つことと同値である。aの部分集合が決まると、maxdiff = (aの最大要素 - aの最小要素), mindiff = (aの隣り合う要素の差の最小値) とわかる。そこで、aの部分集合の最小要素と最大要素を全探索する。これはaをソートしておくと左端iと右端jを全探索すればよい。i, jが固定された時点でmaxdiffは定まっているので、あと考えなければならないのはmindiffだけ。iとjの間にある要素のうち、mindiffの条件を満たすものだけ取っていくとi, jに対するaの部分集合の要素数の最大値が求まる。

i, jを決めたとき、必ずしもその間をすべて取る必要はないことに注意。

class CliqueParty {
    public:
    int maxsize(vector<int> a, int k) {
        sort(all(a));
        int n = a.size();
        int ans = 1;
        rep(j, n) {
            rep(i, j) {
                int ma = a[j] - a[i];
                int cnt = 2;
                int pre = a[i];
                rep2(t, i + 1, j) {
                    if (ma <= 1LL * k * (a[t] - pre) && ma <= 1LL * (a[j] - a[t]) * k) {
                        cnt++;
                        pre = a[t];
                    }
                }
                ans = max(ans, cnt);
             }
        }
        return ans;
    }
};

Overall Accuracy: 47.93%

ソートしてmaxdiff <= ki * mindiffまではわかったけど、i, jの間をすべて取れなければ最適でないと思い込んでいたのでHackされた。

じっくり考察、って感じだなあ……。