読者です 読者をやめる 読者になる 読者になる

Facebook Hacker Cup 2017 Round 1 - Fighting the Zombies

競プロ

問題

Fighting the Zombies | Facebook Hacker Cup 2017 Round 1

考察

円で移動させ、四角で攻撃するので、少し厄介な感じがします。
が、円の大きさは自由、四角の大きさは正方形で決まっています。
移動させる範囲が所定の正方形より大きくても結局攻撃できないため、同じ大きさの四角を移動させると考えても問題ありません。

うまく円の大きさや位置をいじることで、正方形x2の片方に含まれるゾンビをもう片方の正方形に移動できます。
きちんと証明するのは厄介そうですが、なんとなくイメージではできそうです。

結局この問題は、一辺がRの正方形を2つ取り出して、それらに含まれるゾンビが最大になるようにすればよいです。

まず、正方形を列挙することから始めます。
存在するゾンビのx座標、y座標全ての組み合わせを左下座標とすると、抜け漏れ無く正方形が作れます。
このとき併せて内部に幾つゾンビがいるか調べておきます。
 O(N^{3})

次に、そこから2つ正方形を取り出し、含まれるゾンビを調べます。
基本的には足し合わせれば良いですが、両方の領域にまたがっているゾンビがいると、それらを引く必要があります。
四角形の交差判定などを利用して、かぶっている範囲を求めて減算しました。
 O(N^{4} * N)

トータルで O(N^{5})となり、 N \leq 50なので間に合います。

注意点として、ゾンビが1体しかいない場合に1と出るようにしないといけません。
私はこれで落としました。

コード

int solve() {
    int N, R;
    cin >> N >> R;

    vector<pii> points(N);
    set<int> sx, sy;
    rep(i, N) {
        int x, y;
        cin >> x >> y;
        points[i] = mp(x, y);
        sx.insert(x);
        sy.insert(y);
    }

    sort(all(points));

    vector<pair<pii, int> > boxes;
    tr(it, sx) {
        tr(it2, sy) {
            int x = *it;
            int y = *it2;

            int c = 0;
            rep(i, N) {
                if(x <= points[i].first && points[i].first <= x + R &&
                    y <= points[i].second && points[i].second <= y + R) {
                    c++;
                }
            }

            if(c > 0)
                boxes.push_back(mp(mp(x,y), c));
        }
    }

    const int sz = boxes.size();
    int ans = 0;

    rep(i, sz) {
        // only one
        chmax(ans, boxes[i].second);

        REP(j, i+1, sz) {
            // collision
            pii p1 = boxes[i].first;
            pii p2 = boxes[j].first;
            double cx1 = (double)p1.first + (double)R / 2;
            double cx2 = (double)p2.first + (double)R / 2;
            double cy1 = (double)p1.second + (double)R / 2;
            double cy2 = (double)p2.second + (double)R / 2;

            int cnt = boxes[i].second + boxes[j].second;

            if( abs(cx1 - cx2) <= R && abs(cy1 - cy2) <= R) {
                if(p1 > p2)
                    swap(p1, p2);

                pii s = mp(-1,-1);
                pii e = mp(-1, -1);
                if(p1.second <= p2.second && p2.second <= p1.second + R) {
                    s = p2;
                    e = mp(p1.first+R, p1.second+R);
                }
                else {
                    s = mp(p2.first, p1.second);
                    e = mp(p1.first+R, p2.second+R);
                }

                rep(i, N) {
                    int x = points[i].first;
                    int y = points[i].second;
                    if(s.first <= x && x <= e.first &&
                            s.second <= y && y <= e.second)
                        cnt--;
                }
            }

            chmax(ans, cnt);
        }
    }

    return ans;
}


int main() {
    int T;
    cin >> T;
    rep(__t, T) {
        cout << "Case #" << __t + 1 << ": ";
        cout << solve() << endl;
    }

    return 0;
}

感想

幾何か!?と思って身構えましたが、そこまで幾何ではなかったです。
もっとすっきり書けそうな気もします……。