Zenn
🚀

ABC 218 D - Rectangles C++解答例

2021/09/12に公開
C++
#
競技プログラミング
AtCoder
#
競プロ
tech

AtCoder Beginner Contest 218 D-RectanglesをC++で解きます。

更新履歴

  • 2021/9/30：計算量の見積もりにおいて、std::mapへの各要素へのアクセスの計算量を考慮していなかったので修正しました。

問題

問題文をAtCoderのページより引用します。

問題文

2次元平面上にN個の相異なる点があり、1, 2, \ldots, Nの番号がついています。点 i (1 \leq i \leq N) の座標は(x_i, y_i)です。

これらの点のうち4つを頂点とし、全ての辺がx軸またはy軸に平行であるような長方形はいくつありますか？

制約

  • 4 \leq N \leq 2000
  • 0 \leq x_i, y_i \leq 10^9
  • (x_i, y_i) \neq (x_j, y_j) (i \neq j)
  • 入力はすべて整数である。

解答例

愚直に考えるとTLE

長方形を作るためには頂点が4つ必要になりますが、N個の中から相異なる点を4つ選んで長方形を作り、その長方形の各辺がx軸またはy軸と平行になるかどうかを見ていくと計算量が\mathcal{O}(N^4)となり、TLEとなってしまいます。
選ぶ点を3つに減らしても2000^3 = 8 \times 10^9なので間に合いません。

選ぶ点を2つにまで減らせたら何とか間に合いそうです。

対角にある点を考える

視点を変えて考えてみます。「全ての辺がx軸またはy軸と平行になるような長方形」は、対角にある2つの頂点が定まれば残りの2点も定まります。
例えば、長方形の左上の頂点にあたる点と、右下の頂点にあたる点を決めれば、自ずと左上と右下の頂点も決まります。

従って、「N個の頂点から2つ点を取り出し、それを対角の点とする長方形が作れるかどうか判定する」ことを繰り返せばこの問題が解けることになります。

「長方形が作れるか？」を素早く判定する

対角になる2点(x_i, y_i), (x_j, y_j) (1 \leq i < j \leq N)を選んだとき、残りの2点とすることができる点、すなわち(x_i, y_j), (x_j, y_i)が与えられたN個の点の中に存在するかどうかを判定しなければなりません。

ここで全探索を使ってしまうと、せっかく探索候補を\mathcal{O}(N^2)まで減らしたのが台無しになってしまいます。
高速な判定方法を探してみましょう。

ここで、「N個の点は全て相異なる」という制約を利用します。N個の点は重なっていないということは、「ある点iのx座標x_iに着目したとき、直線x = x_i上に存在する点のy座標は全て異なる」ということです。

つまり、ある点とx座標を同じくする点のy座標は、集合(std::set)で管理できるということがわかります。
集合で管理できるならば、存在するかどうかの判定は\mathcal{O}(\log{N})で行うことができます。十分に高速であるので、これを使えば何とか解けそうです。

実装の仕方

2次元平面上の各x座標について、そのx座標を通りy軸に平行な直線上に存在する点のy座標を集合で管理します。
std::setを要素とする配列をとってもいいですが、制約からx座標の範囲は0 \leq x \leq 10^9あり、Nはせいぜい2000までなので無駄が多いです。ここはstd::mapを使いましょう。

std::map<int64_t, std::set<int64_t>>型の変数を用意し、そこに点を記録していきます。std::mapの1つ目のキーが点のx座標で、2つ目のキーがそのx座標上に存在する点のy座標を格納した集合です。

そして、長方形の対角となる2点(x_i, y_i), (x_j, y_j)をとったとき、

  • 直線x = x_i上にy座標がy_jである点は存在するか？」
  • 直線x = x_j上にy座標がy_iである点は存在するか？」

という2つの判定を行います。どちらも真であるならば、2点(x_i, y_i), (x_j, y_j)を対角とする長方形が作れます。

この判定を全ての2点の組み合わせについて判定していけばよいです。

同じ長方形が2回計上されることに注意！

ここで1つ注意点があります。問題の条件を満たすある長方形について着目したとき、その長方形は対角となる点として「左下と右上の点の組」と「左上と右下の点の組」を持ちます。

そのため、N個の中から2点選んだとき、ある1つの長方形について2回計上を行ってしまうことになります。

対策は簡単で、答えを出力するときに2で割ってやることで正しく計上することができます。

C++で実装した例

C++で実装した例が以下のコードです[1]。
N個の中から2点を選び、そのそれぞれに対してmapへのアクセスを行い、更にそのそれぞれに対して集合の二分探索を行うので、総計算量は\mathcal{O}(N^2 \log{N}\log{N})になります。

d.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>

int main() {
  int64_t N;
  std::cin >> N;

  std::vector<int64_t> x(N);
  std::vector<int64_t> y(N);
  std::map<int64_t, std::set<int64_t>> vertical_point;
  for (int64_t i = 0; i < N; i++) {
    int64_t px, py;
    std::cin >> px >> py;
    x.at(i) = px;
    y.at(i) = py;
    vertical_point[px].insert(py);
  }

  int64_t count = 0;
  for (int64_t i = 0; i < N; i++) {
    for (int64_t j = i; j < N; j++) {
      if (x.at(i) != x.at(j) && y.at(i) != y.at(j)) {
        if (vertical_point[x.at(i)].find(y.at(j)) != vertical_point[x.at(i)].end()
            && vertical_point[x.at(j)].find(y.at(i)) != vertical_point[x.at(j)].end())
        {
          count++;
        }
      }
    }
  }

  std::cout << count / 2 << std::endl;

  return 0;
}

実際に提出したコードはこちら。

脚注

  1. 2重ループの中に余計な判定(選んだ2点が相異なるかどうかチェックするif文)が入っちゃってます。多分無くても動きます ↩︎

Discussion