けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 304 D - A Piece of Cake (1Q, 緑色, 400 点)

AtCoder AtCoder400点 そのまま覚えたい典型問題 緑色diff ABC-D 座標圧縮 区間 二分探索:lower_bound 二分探索 【問題集】二分探索の入門 考察：独立に考える 二次元平面上のN点の問題 sparseな問題 最大値と最小値を求める 独立に考える：x軸とy軸 NoviSteps1Q

「点がどの区間に属するか」は極めて典型的な問題で、それを二次元にしたバージョン！

問題概要

二次元平面上で、左下の頂点が (0, 0)、右上の頂点が (W, H) であるような長方形状のケーキがあります。

このケーキ上には N 個のいちごが乗っていて、 i 番目のいちごは (p_{i}, q_{i}) にあります。

今、このケーキに対して

  • A 本の直線 x = a_{1}, a_{2}, \dots, a_{A} に沿って切る
  • B 本の直線 y = b_{1}, b_{2}, \dots, b_{B} に沿って切る

ただし、 0 \lt a_{1} \lt a_{2} \lt \dots \lt a_{A} \lt W、 0 \lt b_{1} \lt b_{2} \lt \dots \lt b_{B} \lt H であるとします。

このとき、ケーキは (A+1)(B+1) 個のピースに分かれます。これらのピースのうち、いちごが乗っている個数の最小値と最大値を答えてください。

制約

  • 3 \le W, H \le 10^{9}
  • 1 \le N, A, B \le 2 \times 10^{5}
  • どのいちごも、ケーキの縁や、切り取り線上にはない

考えたこと：まず整理する

問題内容が多少複雑なので、整理してみましょう。たとえば、

  • W = 11, H = 10
  • a = (3, 5, 9)　 (A = 3)
  • b = (2, 4, 8)　 (B = 3)
  • (p, q) = (2, 1), (4, 5), (4, 6), (4, 7), (6, 3), (7, 9), (8, 1), (9, 6)　 (N = 8)

の場合は、下図のようになります。この場合、答えは最小値が 0 個、最大値が 3 個となります。

x 軸と y 軸をそれぞれ独立に考える

二次元の問題であっても、実は x 軸と y 軸をそれぞれ独立に考えてよいことはすごくたくさんあります。今回も、各いちごについて

  • x 軸方向に分かれた A + 1 個の区間のどこに属するか
  • y 軸方向に分かれた B + 1 個の区間のどこに属するか

を、それぞれ独立に考えることができます。そして、この「与えられた点がどの区間に属するか」という問題は、ものすごく典型的なよくある問題です。C++ であれば lower_bound() を使って求められます。

ピンと来ない方は、ぜひ次の問題を先に解いてみてください。あの有名な競プロ典型 90 問の問 007 です！

drken1215.hatenablog.com

10^{5} \times 10^{5} の二次元配列は無理なので map を使う

ここまで来れば、次のような配列を作りたくなるでしょう。

num[i][j] ← x 軸方向に見て i 番目の区間 ( i = 0, 1, \dots, A)、 y 軸方向に見て j 番目の区間 ( j = 0, 1, \dots, B) を表すピースに含まれるイチゴの個数

この配列は、たとえば次のように求められる気がしてきます。なお、入力の a や b の先頭には、あらかじめ 0 を挿入しておくこととします。

vector<vector<int>> num(A+1, vector<int>(B+1, 0));

// 各いちごが属するピースを求める
for (int i = 0; i < N; ++i) {
    // x 軸方向の区間番号を求める
    int x = lower_bound(a.begin(), a.end(), p[i]) - a.begin();
    
    // y 軸方向の区間番号を求める
    int y = lower_bound(b.begin(), b.end(), q[i]) - b.begin();

    // カウントする
    ++num[x][y];
}

しかしこの方法は MLE します。なぜなら、配列 num のサイズが O(AB) であり、馬鹿でかいのです。

ここで、「いちごが乗っているようなピースの個数は高々 N 個以下」であることを思い出しましょう。よって、二次元配列の代わりに連想配列を使います。C++ なら、次のようにすれば良いでしょう。

map<pair<int,int>, int> num

num[{i, j}]は、 x 軸方向に見て i 番目の区間 ( i = 0, 1, \dots, A)、 y 軸方向に見て j 番目の区間 ( j = 0, 1, \dots, B) を表すピースに含まれるイチゴの個数を表す

こうすれば、変数 num の専有するメモリ容量は O(N) で済みます。

最後に：最大値と最小値

最後に、各ピースのいちごの個数の最大値と最小値を求める方法を整理します。

最大値は簡単です。変数 num の要素を順に見ていき、いちごの個数の最大値を見ればよいです。最小値は少々複雑です。そもそも変数 num には、いちごが 1 個以上乗っているようなピースしか格納されていません。そこで、

  • ピースの個数 (A+1)(B+1)
  • 変数 num のサイズ

を比較すればよいです。前者の方が大きければ最小値は 0 個、前者と後者が等しければ最小値は num の要素を見ていったときの、いちごの個数の最小値を求めれば良いです。

以上の解法の計算量は O(N(\log A + \log B + \log N) + A + B) となります。

コード

最後の注意点として、 (A+1)(B+1) を計算するときにオーバーフローしないようにしましょう！

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;  // 何番目のピースかを表す

int main() {
    // 入力
    long long W, H, N, A, B;
    cin >> W >> H >> N;
    vector<long long> p(N), q(N);
    for (int i = 0; i < N; ++i) cin >> p[i] >> q[i];
    cin >> A;
    vector<long long> a(A+1, 0);
    for (int i = 0; i < A; ++i) cin >> a[i+1];
    cin >> B;
    vector<long long> b(B+1, 0);
    for (int i = 0; i < B; ++i) cin >> b[i+1];
    
    // 各ピースのイチゴの個数を集計する
    map<pint, int> num;
    for (int i = 0; i < N; ++i) {
        int x = lower_bound(a.begin(), a.end(), p[i]) - a.begin();
        int y = lower_bound(b.begin(), b.end(), q[i]) - b.begin();
        ++num[pint(x, y)];
    }
    
    // 変数 num に格納されているピースのいちごの個数の最大値と最小値を求める
    int minv = N + 1, maxv = -1;
    for (auto it : num) {
        minv = min(minv, it.second);
        maxv = max(maxv, it.second);
    }
    
    // いちごの乗っていないピースがある場合
    if (num.size() < (A+1) * (B+1)) minv = 0;
    
    // 出力
    cout << minv << " " << maxv << endl;
}