2021年9月11日に開催された AtCoder Beginner Contest 218（ABC218） に参加しました。

AtCoder Beginner Contest 218 – AtCoder

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

結果は以下の通りでした。

• 2完（A,B） 0WA
• 順位: 4494位
• パフォーマンス: 579
• レーティング: 720 → 707

ここではD問題について復習します。

D問題について

問題等は以下のリンクをご確認ください。

D – Rectangles

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

コンテスト中は手が出せなかったのですが、コンテスト後にやってみました。

考えた手順は以下の通りです。

1. 左上と右下が決まれば、右上と左下の座標が決まるので、\(N^2\)で全部試せばいい。
2. 右上と左下の座標と同じ点があればOKで、二分探索を使えば実行計算時間4秒だし間に合いそう。

競プロ典型90問であった「答えで二分探索」のような発想です。
コンテスト中じゃなければ発想もスムーズ。
落ち着いたものです。

上記の手順をもとに一旦、ACしたコードは以下になります。

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// const int mod = 1000000007;
// const ll INF = 1LL<<60;
// const int INF = 1001001001;

int main() {
  int N;
  cin >> N;

  vector<P> point(N);
  rep(i, N) {
    int x, y;
    cin >> x >> y;
    point[i] = make_pair(x, y);
  }

  set<vector<P>> ans;
  sort(point.begin(), point.end());
  rep(i, N) {
    rep(j, N) {
      if(i == j) {
        continue;
      }
      // top_left
      P tl = point[i];
      // bottom_right
      P br = point[j];

      // top_right
      P tr = *lower_bound(point.begin(), point.end(),
                          make_pair(br.first, tl.second));
      // bottom_left
      P bl = *lower_bound(point.begin(), point.end(),
                          make_pair(tl.first, br.second));

      // 同じ点があったらダメ
      if(tl == tr || br == tr || tl == bl || br == bl || tr == bl) {
        continue;
      }

      if(tl.first == bl.first && tl.second == tr.second &&
         bl.second == br.second && br.first == tr.first) {
        vector<P> v = {tl, br, tr, bl};
        sort(v.begin(), v.end());
        ans.insert(v);
      }
    }
  }

  cout << ans.size() << endl;
  return 0;
}

上記のコードを実装時は、二分探索＝lower_boundという発想しかありませんでした。。

二分探索＝lower_bound近いものを返す場合があるので、ACできましたが、その辺の調整が大変でした。

最終的には、setにvector>をいれるという、強引というかゴリ押しというかなんかスマートじゃないなというか何かまんぞくできない感じで実装しました。

binary_searchもあるのを忘れない

二分探索には、binary_searchもあることを忘れない。

このD問題で得た教訓です。

binary_searchを使ってACしたコードが以下になります。
以前感じたゴリ押し感なく満足できる感じで解けました。

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// const int mod = 1000000007;
// const ll INF = 1LL<<60;
// const int INF = 1001001001;

int main() {
  int N;
  cin >> N;

  vector<P> point(N);
  rep(i, N) {
    int x, y;
    cin >> x >> y;
    point[i] = make_pair(x, y);
  }

  int ans = 0;
  sort(point.begin(), point.end());
  rep(i, N) {
    rep(j, N) {
      if(i == j) {
        continue;
      }
      // top_left
      P tl = point[i];
      // bottom_right
      P br = point[j];

      if(br.first <= tl.first || br.second <= tl.second) {
        continue;
      }

      // top_right
      bool flg1 = binary_search(point.begin(), point.end(),
                                make_pair(br.first, tl.second));
      // bottom_left
      bool flg2 = binary_search(point.begin(), point.end(),
                                make_pair(tl.first, br.second));

      if(flg1 && flg2) {
        ans++;
      }
    }
  }

  cout << ans << endl;
  return 0;
}