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

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

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

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

問題概要

二次元平面上で、左下の頂点が  (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;
}