ABC 278 E — Grid Filling

考察

各windowの外側に残るdistinct数は、値xごとに『grid全体の出現数−window内出現数が正か』を数えればよい。

H,W,N≤300なので、値ごとに2D prefix countを持つHWN規模の集計が制約内に収まる。

採用する候補: 各値xのindicator gridに2D累積和を作り、各h×w window内のx個数を全体個数から引いて外に残る値を数える。

棄却する候補: 各windowごとにblackout外の全HW cellを走査し、setでdistinctを数える。

window数もHW規模で、全体が(HW)²になり得る。

count[r][c][x]を(1,1)…(r,c)のx出現数として全値分構築する。各top-left(k,l)とxについてh×w内個数を4項で取り、total[x]との差が正ならanswerを1増やして表形式で出力する。

典型の発動条件

値別2D累積和

発動条件: 小さい値域の各カテゴリについて、多数のrectangle内出現数queryが必要なとき。

カテゴリindicatorのprefix countを第三次元に持ち、4 corner差を取る。

補集合でdistinct判定

発動条件: 領域外のdistinct種類数を求め、全体頻度と領域内頻度が得られるとき。

total-inside>0のカテゴリ数を数える。

問題固有の要素

blackout外を直接見る代わりに、各値がblackout内へ全出現を奪われたかだけを判定すればよい。

別の問題へ持ち帰る視点: 領域削除後のdistinct数は、カテゴリごとの全体頻度と削除領域頻度の一致判定へ分解する。

正当性

値xが答えに含まれる条件はtotal[x]>insideWindow[x]であり、window外の位置を個別に列挙する必要はない。 rectangle内個数は4 cornerの2D prefix差で求まり、同じprefix tableを全windowで再利用できる。 windowごとのcell再走査を避け、各値のrectangle countを定数時間で得られる。

実装上の注意

  • prefix配列の0行・0列を用意し、window端点のinclusive/exclusive規約を統一する。
  • 実際に出現しない値はtotal=0なので答えへ加えず、Nの全値を走査しても条件をstrictly positiveにする。

復習の核

  • ある値の全出現がwindow内に入る場合と1個だけ外へ残る場合を描き、判定がtotal==insideかどうかに集約されることを確認する。

計算量と制約

時間

O(HWN+(H−h+1)(W−w+1)N)、Nは色数、h×wを切り抜く。

空間

O(HWN)、色別2D prefix。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq H,W,N \leq 300; 1 \leq h \leq H; 1 \leq w \leq W; (h,w)\neq(H,W); 1 \leq A _ {i,j} \leq N\ (1\leq i\leq H,1\leq j\leq W); All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Grid Filling の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 一次元・二次元累積和と差分で区間情報を線形化する

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

      主タグ: 累積和・差分配列

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

      学習の位置

      体系上の位置: 一次元・二次元累積和と差分で区間情報を線形化する

      • prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。

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

      • オンライン更新を伴うFenwick Tree・Segment Treeの動的区間要約。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題