Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 223 E 問題 Placing Rectangles

AtCoder ABC ABC223 E問題 500 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

次を満たすように長方形 \mathcal{R}, \mathcal{S}, \mathcal{T} を座標平面 \mathbb{R}^2 に配置できるか?

  • \mathcal{R}, \mathcal{S}, \mathcal{T} の各辺は x 軸または y 軸に平行である.
  • \mathcal{R}, \mathcal{S}, \mathcal{T} の頂点は格子点で, 領域 [0,X] \times [0,Y] 内 (境界含む) の点である.
  • \mathcal{R} の面積は A 以上, \mathcal{S} の面積は B 以上, \mathcal{T} の面積は C 以上
  • どの2つの長方形を選んでも, その共通部分の面積は 0 である.

制約

  • 1 \leq X,Y \leq 10^9
  • 1 \leq A,B,C \leq 10^{18}

解法

簡略化した問題を考える.

まず, 問題を簡略化して, 2つの長方形 \mathcal{R}, \mathcal{S} の場合を考える. この場合, 配置可能ならば, 1つの長方形のある辺を延長することによって, 領域をある直線で分割して, 各領域を長方形 \mathcal{R}, \mathcal{S} と見なすことにより, 配置可能な例を示せた.

このことから, X+Y+2 本の直線 x=a~(0 \leq a \leq X), y=b~(0 \leq b \leq Y) で分断したときの長方形 \mathcal{R}, \mathcal{S} の面積を比較し, 条件を満たすような直線が存在するか判定すれば良い.

ただし, 実際には全探索ではなく, \mathcal{R} については各軸に平行な直線のうち, 条件を満たすギリギリの直線のみを見れば十分である. つまり, 2直線 \displaystyle y=\left \lceil \dfrac{A}{X} \right \rceil, x=\left \lceil \dfrac{A}{Y} \right \rceil のみをみれば十分である.

本問題を考える.

では, 今回の問題である, 3個の場合を考える. 2個の場合と同様に考えると, 条件を満たすならば, 以下のうちのどれかで領域を分割した後, 各領域を長方形と見なすことにより, 条件を満たすような例を作れる.

  • 領域内の格子点 (p,q) を中心とし, x 軸, y 軸 に平行な2つの直線と半直線でT字型で分割する.
  • x 軸に平行な2つの直線
  • y 軸に平行な2つの直線

よって, 領域の分割の方法および, 長方形 \mathcal{R}, \mathcal{S}, \mathcal{T} の割当を全て調べることによって, O(1) で判定できる.