概要

入力の \(K\) 操作を終えた盤面を見ることで，行同士・列同士の比較関数を定めることができ，それを使って残り \((N^2-K)\) 回の操作の長方形の和集合として作るべき図形を \(1\) つ得ることができます．

構成方法

議論を簡単にするために，\((N+1)\) 行 \((N+1)\) 列の盤面に対して，スタンプ \((N+1, N+1), (N, N+1), \ldots, (1, N+1), (N+1, N), \ldots, (N+1, 1)\) をこの順に位置 \((1, 1)\) に押す，という操作を入力の先頭に追加したと思うことにして，\((N, K) \gets (N+1, 2N+1+K)\) とします．このようにしても解の有無は変わりません．

入力の \(K\) 操作を終えた盤面でのマス \((x, y)\) の色を \(f[x][y]\) とします．ただし色は \(1, \ldots, K\) の操作番号で表します．

行 \(x, x'\) に対し，関係 \(f[x] \prec f[x']\) を次で定めます：\(f[x][y] \ne f[x'][y]\) となる \(y\) のうち \(\max\{ f[x][y], f[x'][y] \}\) が最大となるものを \(1\) 個選んで，\(f[x][y] < f[x'][y]\) とできる．

[事実] \(x \ne x'\) のとき，\(f[x] \prec f[x']\) と \(f[x'] \prec f[x]\) のうちちょうど一方が成り立つことがわかります．

\((1, \ldots, N)\) の並べ替え \((x_1, \ldots, x_N)\) であって，各 \(h = 1, \ldots, N\) に対し \(\{x_1, \ldots, x_h\}\) が連続する \(h\) 個の整数をなすものを，ここでは良い順列と呼ぶことにします．

[手順 1] 初め \(p\) を空列，\(l = 1,\, r = N\) として，以下を繰り返します：

• \(l = r\) なら，\(p\) の先頭に \(l\) を追加して終了する．
• \(f[l] \prec f[r]\) なら，\(p\) の先頭に \(l\) を追加して，\(l \gets l+1\) とする．
• \(f[r] \prec f[l]\) なら，\(p\) の先頭に \(r\) を追加して，\(r \gets r-1\) とする．

すると良い順列 \(p = (x_1, \ldots, x_N)\) が得られます．

行と列の役割を入れ替えて，同様に良い順列 \((y_1, \ldots, y_N)\) を得ます．

[手順 2] このとき，以下の手順で正答が得られます：未使用のスタンプを \((h, w)\) の辞書順で降順に選び，長方形 \(\{x_1, \ldots, x_h\} \times \{y_1, \ldots, y_w\}\) を塗る．

\(f\) を求める部分は想定解の解説と同様です (愚直にやって，定数倍の軽い \(O(N^4)\) 時間でもよいです)．他は \(O(N^2)\) 時間でできます．

正当性の証明

[事実] の証明

冒頭で盤面を \((N+1)\) 行 \((N+1)\) 列に拡張したことにより，\(x \ne x'\) ならば \(f[x] \ne f[x']\) が成り立ちます．

\(\prec\) の定義で \(y\) の取り方が複数あり \(f[x][y] > f[x'][y],\, f[x][y'] < f[x'][y']\) となってしまう場合が問題ですが，これは操作 \(f[x][y] (= f[x'][y'])\) で塗った部分が長方形であることに反します．

操作の性質

操作を逆から見ると，長方形の和集合の面積が \(1\) ずつ増えていくことが目標になります．

操作列を \(1\) つ決めたとき，操作番号 \(>k\) の長方形の和集合を \(U(k)\) とし，\(U(k)\) の行 \(x\) にある列集合を \(I(k, x)\) と，\(U(k)\) の列 \(y\) にある行集合を \(J(k, y)\) と書くことにします．

[性質 1] 操作列が目標を達成することと，任意の \(k\) に対し以下の条件が成り立つことは同値です：

• 操作番号 \(>k\) で使ったスタンプ \((h, w)\) の集合は Young 図形となる
• 良い順列 \((x_1, \ldots, x_N)\) が存在し，\(I(k, x_1) \supseteq \cdots \supseteq I(k, x_N)\)
• 良い順列 \((y_1, \ldots, y_N)\) が存在し，\(J(k, y_1) \supseteq \cdots \supseteq J(k, y_N)\)
• 上の \(2\) 条件より，\(U(k)\) は行や列を並べ替えると Young 図形となるが，これが先述の \((h, w)\) たちの Young 図形と一致する

これは帰納法で証明できます．想定解の解説も参考にしてください．

[性質 2] さらに，任意の \(k\) に対し以下の条件が成り立つこととも同値です：

• 操作番号 \(>k\) で使ったスタンプ \((h, w)\) の集合は Young 図形となる
• 操作 \(k\) の長方形が使う行 \(x\) と使わない行 \(x'\) に対し，\(I(k, x) \supseteq I(k, x')\)
• 操作 \(k\) の長方形が使う列 \(y\) と使わない列 \(y'\) に対し，\(J(k, y) \supseteq J(k, y')\)

これも帰納法で証明できます．構成の正当性をこの条件を使って示すことにします．

解とは何か

[形の条件] 目標を達成する操作列に対する \(U(K)\) (および \(I(K, x), J(K, y)\)) は，以下の条件を満たすものすべてをとりえます：

• 良い順列 \((x_1, \ldots, x_N)\) が存在し，\(I(K, x_1) \supseteq \cdots \supseteq I(K, x_N)\)
• 良い順列 \((y_1, \ldots, y_N)\) が存在し，\(J(K, y_1) \supseteq \cdots \supseteq J(K, y_N)\)
• 入力の \(K\) 操作で未使用のスタンプ \((h, w)\) の集合のなす Young 図形と，\(U(K)\) の行や列を並べ替えて得られる Young 図形が一致する

これは [手順 2] を行えばよいことからわかります．

以下，この条件を満たす \(U(K)\) を求める問題として考えます．そのようなもののうち，入力の \(K\) 操作と合わせて目標を達成するものを単に解と呼ぶことにします．解の存在が保証されているので，\(1\) つとります．

解の変形

\(f\) を基に [手順 1] で得られる良い順列 \((x_1, \ldots, x_N)\) に対して \(I(K, x_1) \supseteq \cdots \supseteq I(K, x_N)\) を満たすように解を変形できることを示します．[手順 1] に沿って以下のように行の swap をしていきます．

\(f[l] \prec f[r]\) の場合を考えます．\(\prec\) の定義によって，ある操作 \(k\) が存在して以下を満たします：

• 操作 \(k+1, \ldots, K\) のそれぞれで，長方形が行 \(l, r\) を共に使うか共に使わない
• 操作 \(k\) では，長方形が行 \(l\) を使わず行 \(r\) を使う

ここで \(I(K, l) \supseteq I(K, r)\) であったとすると，\(1\) つ目の条件から \(I(k, l) \supseteq I(k, r)\) です．一方 \(2\) つ目の条件から [性質 2] を用いると \(I(k, l) \subseteq I(k, r)\) なので，\(I(k, l) = I(k, r)\) です．このとき，\(U(K)\) の行 \(l\) と行 \(r\) を入れ替えても解であることが保たれるとわかります．確認すべきことは以下です：

• [形の条件] を保つこと．これは \(x < l\) または \(r < x\) に対する \(I(K, x)\) が \(I(K, l), I(K, r)\) いずれもの部分集合であることが手順中に不変であることから従います．
• [性質 2] を保つこと．操作 \(k+1, \ldots, K\) においては先程の \(1\) つ目の条件より成り立ち，操作 \(1, \ldots, k\) においては入れ替えても \(I(*, l), I(*, r)\) が変わらないことから成り立ちます．

このようにして，必要ならば解を取り換えて \(I(K, l) \subseteq I(K, r)\) を満たすようにできます．

\(f[r] \prec f[l]\) の場合も同様に \(I(K, l) \supseteq I(K, r)\) を満たすようにできます．

これで，\(l = r\) となったときに所望の変形が完了します．全く同様にして，\(f\) を基に [手順 1] で得られる良い順列 \((y_1, \ldots, y_N)\) に対して \(J(K, y_1) \supseteq \cdots \supseteq J(K, y_N)\) を満たすように列の swap をして解を変形できます．なお，列の swap は \(I\) の条件に影響を与えません．

\((x_1, \ldots, x_N), (y_1, \ldots, y_N)\) が与えられたとき [形の条件] の条件を満たすマスの集合は一意なので，以上の変形によって得られた解がまさしく \(f\) に基づいて構成したものに一致することが示されました．