ABC 223 E — Placing Rectangles

考察

面積の総和が XY 以下でも、整数辺長と各長方形の形のため配置できるとは限らない。一方、長方形が三つだけなら、実現可能な配置には一つを残り二つから分ける水平または垂直な直線が存在する。

採用する候補: 分離する一個の長方形、分離方向、A,B,C の順列を列挙し、天井除算で必要な帯幅を確保して残領域へ二個を並べられるか判定する。

三長方形に対する分離直線の存在により、連続的に見える配置を有限個の必要十分な切り分けへ落とせる。

棄却する候補: A+B+C≤XY だけを確認して配置可能と判定する。

面積には余裕があっても、各長方形が整数幅・整数高さを必要とするため、容器の縦横へ収まらない例を除けない。

面積 S の長方形を幅 w の帯へ置くには高さ ceil(S/w) が必要十分であり、帯を切り取った後は二長方形の同じ判定へ帰着する。

三長方形の任意の実現可能配置では、いずれかの長方形の辺を延長することで、一個と二個を隔てる軸平行線を選べる。

A,B,C の6順列と X,Y の二方向を試し、最初の面積に必要な帯を切り取り、残った長方形で残り二面積を縦または横に分割できるか天井除算で調べる。

典型の発動条件

分離補題による幾何配置の有限化

発動条件: 少数の軸平行図形を重ならずに置く存在判定で、図形の辺を延長した分離線を議論できるとき。

三個の配置を『一個を帯へ置き、残り二個を残領域へ置く』有限ケースとして全列挙する。

天井除算による最小必要長

発動条件: 整数辺長の長方形で、一辺と必要面積からもう一辺の最小値を求めるとき。

面積 S を幅 w に収める高さを ceil(S/w) とし、残る寸法を過不足なく更新する。

問題固有の要素

三個までなら、どの実現可能配置にも一個対二個の軸平行な分離線が存在するため、複雑な噛み合わせを考えなくてよい。

別の問題へ持ち帰る視点: 少数の軸平行図形では、辺の延長で配置を再帰的な帯分割に標準化できるかを先に証明する。

正当性

面積Sを幅wの帯に置くための最小整数高さはceil(S/w)であり、それより狭い帯では面積が不足する。三つの互いに重ならない軸平行長方形には、一つと残り二つを分離する水平または垂直な切り線が存在する。横方向に二枚が分離している場合、その間を三枚目が遮れば三枚目は両方から縦に分離しており、縦の切り線を選べる。この一枚を最小の帯へ縮めても残りの領域は減らない。残り二枚は縦か横に分離でき、必要幅・高さの天井除算で正確に判定できる。全一枚目と全方向を試すので配置を漏らさない。

実装上の注意

  • ceil(S/w) は (S+w-1)/w で求め、S が10^18なので加算と面積比較の整数幅を確保し、必要長が容器を超えた場合を直ちに失敗させる。

復習の核

  • 面積総和だけで判断せず、『一個を切り離せる線があるか』を証明してから有限ケースへ落とす。

計算量と制約

時間

3!個の順列と容器の二方向、および残り二枚の二方向を試すだけなので O(1)。

空間

O(1)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq X, Y \leq 10^9; 1 \leq A, B, C \leq 10^{18}; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Placing Rectangles の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 幾何の基本判定と座標変換

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 幾何の基本判定・配置・座標変換

    補助タグ: 有界全列挙・有限case分解

    執筆: abc-explanation-author1.1.1 / revision 1

    学習の位置

    体系上の位置: 幾何の基本判定と座標変換

    • 幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。

    先に読む単元:

    この解説で扱わないこと:

    • 凸包の境界候補列挙・半平面交差。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題