ABC 309 F — Box in Box

考察

箱は自由に回転できるので、各箱の三辺を昇順 h≤w≤d に正規化してよい。すると必要なのは三座標すべてが真に小さい点対の存在判定である。

h の昇順に走査すれば第一座標は処理順へ移せるが、h が等しい箱同士を参照させない工夫が strict な不等号に必要になる。

採用する候補: h ごとに同値群をまとめ、過去の箱について w 未満の最小 d をセグメント木で問い合わせてから同値群を一括追加する。

棄却する候補: 正規化した全箱の二組を比較して、三辺がすべて小さい組を探す。

N=2×10^5 では N² 比較が不可能であり、第一座標の順序を活用できていない。

各箱の辺を昇順化し、h 昇順で同じ h を一群にする。群内の各 (w,d) についてセグメント木の w 未満の最小値が d 未満なら Yes。全照会後に各 w へ d の min 更新を行い、最後まで無ければ No とする。

典型の発動条件

多次元 strict dominance の平面走査

発動条件: 複数座標がすべて真に小さい点対を多数の点から探すとき。

一座標を走査順へ移し、残る座標を区間集約データ構造で判定する。

同値キーの遅延追加

発動条件: 走査キーに strict 不等号があり、同値要素同士を過去として扱うと誤答するとき。

同じ h の問い合わせをすべて済ませてから更新し、h<h_current を不変条件にする。

問題固有の要素

三辺を箱ごとにソートする正規化が、6 通りの回転を消すだけでなく比較軸を共通化する。

別の問題へ持ち帰る視点: 対称な向きを持つ物体では、向き全探索の前に sorted components による支配関係へ落ちないか調べる。

正当性

回転の選択を探索する代わりに三辺をソートすれば、「ある向きで入る」と正規化後の成分ごとの strict dominance が同値になる。 w を座標圧縮し、prefix [0,w) に登録済みの d の最小値を持てば、存在判定に必要な過去全体を一値へ集約できる。 過去集合を h が真に小さい箱だけに限定し、区間最小値が d 未満かで残る二座標の strict dominance を判定できる。

実装上の注意

  • w 未満を問い合わせて w 自身を含めないこと、同じ h の更新を照会後に行うことの二箇所で strict 条件を守る。初期値は全 d より大きくする。

復習の核

  • 多次元比較ではまず等号が許される軸を明記する。この問題では三軸とも strict なので、ソート順だけでなく同値群の更新時刻まで点検する。

計算量と制約

時間

O(N log N)、三辺sortは固定三値。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2.5 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 1 \leq h_i,w_i,d_i \leq 10^9; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Box in Box の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: event順にactive集合を更新する

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

    主タグ: event・値順のオフライン走査

    補助タグ: 座標・値の順序保存圧縮 区間monoid要約

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

    学習の位置

    体系上の位置: event順にactive集合を更新する

    • 値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。

    先に読む単元:

    • 疎なkeyの順序を保ってdense indexへ圧縮する — 保持すべき疎な座標をsort-uniqueして順序・等値性を添字へ写す。距離・時間差・区間長も使う場合は元座標と間隔を併せて保存する。
    • 区間monoid要約 — queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

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

    • 更新を単に逆順へ読む処理、答えの局所寄与だけを集計する順序交換、sort-uniqueしたkeyの添字化、および固定方向の単純scan。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題