WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM684 Div1 Easy "CliqueParty"

解法

配列を昇順にソートしておいて、サブセットに含める最小値a[L]と最大値a[R]の2つを決め打ちする。
すると、Dの最大値は「a[R] - a[L]」に固定される。Dの最小値も「Dの最大値 / k」に固定される。
あとはa[L + 1]からa[R - 1]まで順に走査し、最近使用した左のものとの差、およびa[R]との差がDの最小値以上のものを貪欲に選んでいけばよい。

ソースコード

class CliqueParty {
    public:
    int maxsize(vector<int> a, int k) {
        int n = a.size();
        sort(a.begin(), a.end());
        int ans = 2;
        for (int L = 0; L < n; L++) {
            for (int R = L + 1; R < n; R++) {
                // (i, j)の範囲内とする。
                int ma = a[R] - a[L];
                int mi = ma / k + (ma % k == 0 ? 0 : 1);

                // 貪欲に行こう
                int cnt = 0;
                int pre_val = a[L];
                for (int i = L + 1; i < R; i++) {
                    if (mi <= a[i] - pre_val && mi <= a[R] - a[i]) {
                        cnt++;
                        pre_val = a[i];
                    }
                }

                if (ans < 2 + cnt) {
                    ans = 2 + cnt;
                }
            }
        }
        return ans;
    }
};