mayoko’s diary

プロコンとかいろいろ。

SRM 684 div1 easy: CliqueParty

この問題, 感覚的にはそこそこ速く解いたつもりだったのにクッソ点数が低くなって, もうダメという感じでした。

解法

この問題で大切なのは結局配列 a の最小値 mini と最大値 maxi が, k*mini >= maxi を満たすように動けるかどうかでわかります。
maxi は「a から選んだ数のうち, 最大のものと最小のものの差」, mini は「a の連続した2つの数の差のうち最小のもの」と考えると, dp で出来そうです。

dp[minDiff][now][first] := (今のところの最小 diff が minDiff で, 今見ているのが 配列 a の now 番目の数で, 一番小さい数の index は first である時に, now から先で稼げる要素の数) とすれば, 次に a から選ぶ数を a[next] であるとして, min(minDiff, a[next]-a[now])*k >= a[next]-a[first] を満たせば dp[minDiff][now][first] = max(dp[min(minDiff, a[next]-a[now])][next][first]) を見る, みたいな感じで OK です。

minDiff をそのまま持つことは当然出来ないので, map を使って座標圧縮しました。
計算量は, 状態が O(n^2*n*n) で, それぞれの状態の計算に O(n log n) (log n は map) かかるので, O(n^5 log n) です。怪しい計算量な気がしますが, 計算時間を見ると 30ms すらかかっているものはなかったです。まぁ結構定数倍が早いですしおすし。

const ll INF = 1ll<<55;
int dp[1300][55];

map<ll, int> mp;
vector<ll> a;
vector<ll> trans;
ll k;

int dfs(int dIndex, int now, int first) {
    int& ret = dp[dIndex][now];
    if (ret >= 0) return ret;
    int n = a.size();
    ll diff = trans[dIndex];
    ret = 1;
    for (int next = now+1; next < n; next++) {
        ll ndiff = min(diff, a[next]-a[now]);
        if (ndiff*k < a[next]-a[first]) continue;
        ret = max(ret, 1+dfs(mp[ndiff], next, first));
    }
    return ret;
}

class CliqueParty {
public:
    int maxsize(vector <int> A, int K) {
        k = K;
        int ans = 2, n = A.size();
        a.resize(n);
        for (int i = 0; i < n; i++) a[i] = A[i];
        sort(a.begin(), a.end());
        mp.clear();
        for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++) {
            mp[a[j]-a[i]] = 0;
        }
        mp[INF] = 0;
        int size = 0;
        trans.clear();
        for (auto& p : mp) {
            p.second = size++;
            trans.push_back(p.first);
        }
        for (int first = 0; first < n; first++) {
            memset(dp, -1, sizeof(dp));
            ans = max(ans, dfs(mp[INF], first, first));
        }
        return ans;
    }
};