スタンプを押す操作を以下のように言い換えましょう．

• 最初すべてのマスは未使用の状態である． スタンプ \((h,w)\) を押すときは，未使用のマスのみからなる \(h \times w\) 長方形を一つ選ぶ．その後長方形内のマスを一つ選んで使用済みに変える．

スタンプ \((h,w)\) の色が最終的に残るマスが，使用済みに変えるマスに対応します． この操作をすべてのスタンプについて行うことが目標です．

valid な操作列の性質を考えます．

結論から言えば，以下の性質が成り立ちます．

• 性質 \(1\) : 操作のすべての段階において，領域は以下の \(2\) つの条件を満たす．

  • 各 \(i\) について，\(i\) 行目にある未使用なマスの列番号は区間 \([l_i,r_i]\) をなす（区間は空かもしれない）．そしてこれらの区間を適切に並び替えると \([l_{i_1},r_{i_1}] \subseteq [l_{i_2},r_{i_2}]\subseteq \cdots \subseteq [l_{i_N},r_{i_N}]\) となる．
  • 各 \(j\) について，\(j\) 列目にある未使用なマスの行番号は区間 \([u_j,d_j]\) をなす（区間は空かもしれない）．そしてこれらの区間を適切に並び替えると \([u_{j_1},d_{j_1}] \subseteq [u_{j_2},d_{j_2}]\subseteq \cdots \subseteq [u_{j_N},d_{j_N}]\) となる．

• 性質 \(2\) : 未使用領域の中でサイズ \((h,w)\) の長方形が取れることと，サイズ \((h,w)\) のスタンプが未使用であることは同値．

以上の性質を帰納法で示します． 明らかに初期状態では成立しています．

適当な状態からスタンプを押すことを考えます． まず，押すスタンプのサイズは極大でなくてはなりません． 極大でないサイズのスタンプを押し，それで使用したマスが \((x,y)\) だとします． ここでマス \((x,y)\) を含む極大長方形を考えると，この長方形と同じサイズのスタンプを今後使用できないことになります． これでは valid な操作列にならないので，押すスタンプのサイズは必ず極大です．

また同様の理由から，\(2\) つ以上の極大長方形に含まれるようなマスを使用することもできません．

これに加えて，長方形の \(4\) 隅以外のマスを使用することもできません． 例として以下の状態 (. が使用済みマス) を考えます． 今から左上の \(4 \times 5\) 長方形にスタンプを押すとします．

OOOOO.
OOOOOO
OOOOO.
OOOAO.
.OO...

ここでもしマス \(A\) (\(=(4,4)\)) を使用したらどうなるでしょうか？ サイズ \(4 \times 4\) のスタンプを今後使えなくなるのでこれは valid な操作にはなりません． これを一般化すれば，\(4\) 隅以外のマスを使用できないとわかります．

では逆に，「ちょうど \(1\) つの極大長方形に含まれ，かつ \(4\) 隅に対応するマス」を使えば必ず valid でしょうか． 実は valid であることがわかります． 上の条件を満たすマスを使用した場合，残った未使用マスの領域が最初に提示した条件をすべて満たすからです．

元の問題に戻りましょう． すでに押した \(K\) 個のスタンプについて，どの \(4\) 隅を使用したかを適切に決めることで，上で示した条件を満たすようにすればよいです．

スタンプ \((h,w)\) を位置 \((a,b)\) に押し，マス \((x,y)\) (\(x=a\) or \(a+h-1\), \(y=b\) or \(b+w-1\)) を使用するとします． valid な操作を得るために \((x,y)\) が満たすべき条件は以下のとおりです．

• \(K\) 個のスタンプを押した段階で，マス \((x,y)\) は別のスタンプで塗られていない．
• スタンプ \((h,w)\) を押す直前の段階で，マス \((x,b-1),(x,b+w),(a-1,y),(a+h,y)\) は使用済みである． ただし盤面からはみ出したマスはすべて使用済みとみなす．

\(x=a\) と \(x=a+h-1\) のどちらを選ぶかを boolean 変数で表すことにします． また同様に \(y=b\) と \(y=b+w-1\) の選択も boolean 変数で表してみます．

するとすべての条件を 2-SAT の形で書くことができます． なのでこれを解けば良いです．

計算量について解析します． 2-SAT の変数や制約は \(O(K)\) 個なので，このパートの計算量は \(O(N^2)\) になります． ただし，最初に \(K\) 個のスタンプを押したあとの盤面を求める必要があり，これに \(O(N^3)\) (or 間に合いそうな好きな計算量) かかります． よって最終的な計算量は \(O(N^3)\) になります．

回答例

おまけ：tester解が面白いです．