SRM 493 div2 hard: CrouchingAmoebas

問題

TopCoder Statistics - Problem Statement

解法

正方形を作る際, 左下の点を決定すれば, どのような正方形になるかは一意に決まります。ということで, 左下の点がどこに来る可能性があるのかを考えると, これは各 (x[i], y[j]) (0 <= i < n, 0 <= j < n) に対して (x[i]+dx, y[j]+dy) (-T <= dx <= T, -T <= dy <= T) となる点のみです。

こころとしては, 位置 (x[i], y[i]) を入れるためにはマンハッタン距離で T より大きく離れていては意味がない, ということです。でも (x[i], y[i]) だけを調べるだけでは不十分で, i != j の場合も調べる必要があります。

このように正方形が決まった場合, どのようにアメーバを動かすのが最適かというと, 正方形内に入れるために動かす回数が少ない物順に貪欲に正方形内にいれていくのが最適です。
正方形をすべて調べて, 正方形内に入れられるアメーバの数が一番多かったものを採用しましょう。

本当は安心するために各 (x[i]+dx, y[j]+dy) について, この点が左下/右下/左上/右上 になる場合も試したかったのですが, そうすると TLE しました。これをやる必要が無い理由は, 例えばもし右上に点をやることで OK になったとすると, 別の頂点から左下の点があった場合を考えた時と同じになるからです。

class CrouchingAmoebas {
public:
    int count(vector <int> x, vector <int> y, int A, int T) {
        int n = x.size();
        vector<pair<ll, ll> > cand;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int dx = -T; dx <= T; dx++) for (int dy = -T; dy <= T; dy++) {
                    if (dx+dy > T) continue;
                    cand.emplace_back(x[i]+dx, y[j]+dy);
                }
            }
        }
        sort(cand.begin(), cand.end());
        cand.erase(unique(cand.begin(), cand.end()), cand.end());
        int ans = 1;
        for (pii p : cand) {
            ll L, R, U, D;
            L = p.first, R = p.first+A;
            D = p.second, U = p.second+A;
            vector<ll> need;
            for (int i = 0; i < n; i++) {
                ll tmp = 0;
                if (x[i] < L) tmp += L-x[i];
                else if (x[i] > R) tmp += x[i]-R;
                if (y[i] < D) tmp += D-y[i];
                else if (y[i] > U) tmp += y[i]-U;
                need.push_back(tmp);
            }
            sort(need.begin(), need.end());
            int rest = T, cnt = 0;
            for (int i = 0; i < n; i++) {
                if (rest < need[i]) break;
                cnt++;
                rest -= need[i];
            }
            ans = max(ans, cnt);
        }
        return ans;
    }
};