ABC 297 F — Minimum Bounding Box 2

考察

bounding box面積の総和は、各マス(a,b)がboxに含まれる選び方数を全マスで足す主客転倒で得られる。

採用する候補: 各マスごとに四方向除外の包除

boxが(a,b)を含まない条件は全選択点が上・下・左・右の半平面に入る事象の和で、16部分集合を面積から二項係数化できる。

棄却する候補: 各K点集合のboxを計算

C(HW,K)通りで不可能。

複数の方向条件の共通部分も一つの長方形領域になり、そこからK点を選ぶ数はC(area,K)である。

二項係数を前計算し、全(a,b)と上下左右条件の16maskについて許可長方形面積を求め、包除符号付きC(area,K)から包含選択数を出し、総和をC(HW,K)で割る。

典型の発動条件

期待値の総和割り

発動条件: 一様な組合せ事象のscore期待値。

全score総和を事象数で割る。

主客転倒と包除

発動条件: box面積を含有マス数として数える。

各マスがbox内に入る選択数を四方向事象の包除で得る。

問題固有の要素

box面積そのものを端点分布で追わず、box内の単位マス指示関数へ分解する。

別の問題へ持ち帰る視点: 幾何量の期待値は構成単位の包含確率へ線形化する。

正当性

box面積は含まれるcellの指示値の和。cellがboxから外れる事象は全選択点が上下左右いずれかの片側領域にあることで、その交差も長方形である。16項の包除がcellを含むK点選択を数えるので、全cellの和は全box面積総和になる。全C(HW,K)選択で割ると期待値を得る。

実装上の注意

  • 方向条件の交差が空なら面積0とし、K>areaのCを0、最後の分母逆元を正しく掛ける。

復習の核

  • 小盤面の全K集合と比較し、K=1,HW、端・中央マスの包除を確認する。

計算量と制約

時間

O(HW)。各cellの16方向maskを定数時間で計算する。

空間

O(HW)。階乗表。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq H,W \leq 1000; 1\leq K \leq HW; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 包除・Möbius反転で重複を補正する

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

    主タグ: 集合上の包除原理

    補助タグ: 組合せ係数・数え上げ 寄与の数え上げと順序交換 法上の四則演算・高速累乗・逆元

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

    学習の位置

    体系上の位置: 包除・Möbius反転で重複を補正する

    • 条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。

    先に読む単元:

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

    • 選択順を二項係数だけで式化する数え上げ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題