問題で問われていること

この問題は、ドラゴンにいることによって選手が入ることができなかったマスを、M 理事長をうまく置くことによって選手をできるだけ多く入れるようにする問題です。

最初の考察

サンプルを見てみると、M理事長が置かれたマスの行・列どちらにも選手が入れるマスが増えていることが分かります。

そして、ドラゴンの位置関係を考えると、M理事長の上下左右 4 方向のうち 2 方向以下のマスの選手は増やせるチャンスがあります。

1 方向しか選手を増やさないとき

\(x\) 座標 \(p\) にドラゴンが存在すると仮定します。 \((p, y)\) にドラゴンが存在する \(y\) の最小値を \(q\) とします。 \((p, q)\) は \(p\) 行目の最も左にあるドラゴンです。

そして、選手を増やす方向にあるマス目を \((p,1), (p,2), \cdots, (p,q-1)\) とします。このとき、実は M 理事長は \((p,q-1)\) に置くことが最適です。

\(1, 2, \cdots, q-2\) のうち、ドラゴンが存在する \(y\) 座標であるようなものの個数を \(k\) とします。そうすると、選手が置けるマスは \(q-2-k\) だけ増えます。

これをドラゴンが存在するそれぞれの \(x\) 座標について見ればこのパターンはすべて網羅できます。対称性から、他の方向も同じです。

2 方向選手を増やすとき

\(x\) 座標 \(p\) にドラゴンが存在すると仮定します。 \((p, y)\) にドラゴンが存在する \(y\) のうちその最小値を \(q\) とします。 \((p, q)\) は \(p\) 行目の最も左にあるドラゴンです。

\(i=1, 2, \cdots, q-1\) のうち、次の条件をすべて満たす最大のものを選び、 \(q'\) とします。

• \(y\) 座標が \(i\) であるようなドラゴンが存在する。
• \((p+1,i),(p+2,i),\cdots, (h,i)\) にドラゴンは存在しない。（すなわち、 \(y\) 座標が \(i\) であるようなドラゴンの \(x\) 座標はすべて \(p\) 未満である）

実は、 \(2\) 方向選手を増やすときはM理事長を \((p,q')\) に置くことが最適です。

\(1, 2, \cdots, q'-1\) のうち、ドラゴンが存在する \(y\) 座標であるようなものの個数を \(k\) とします。そうすると、 \((p,1), (p,2), \cdots, (p,q'-1)\) において選手が置けるマスは \(q'-1-k\) だけ増えます。

\(p+1,p+2,\cdots, h\) のうち、ドラゴンが存在する \(x\) 座標であるようなものの個数を \(s\) とします。そうすると、 \((p+1,q'), (p+2,q'), \cdots, (h,q')\) において選手が置けるマスは \(h-p-s\) だけ増えます。

これら以外のマスであって選手の入れるようになるマスはありません。

難しいのは \(q'\) を求めるパートですが、次のようにして解決することが出来ます。

• まず、空の集合 \(S\) と配列 \(A\) を用意する。また、事前に各 \(y\) 座標におけるドラゴンの個数を求める。
• \(x\) 座標 \(p\) の昇順に処理していく。
• \((p,i)\) にドラゴンがあれば、 \(A_i\) に \(1\) を足す。もし \(A_i\) が事前に求めた \(y=i\) におけるドラゴンの個数と一致したら、 \(S\) に \(i\) を追加する。
• \(q'\) は \(S\) における \(q\) 以下の最も大きい要素の値である。

\(S\) を保持するデータ構造として std::set（平行二分探索木） やセグメント木を用いることで \(q'\) はそれぞれ \(O(\log(N))\) 時間で求められます。

対称性から、他の方向も同じです。

実装

この問題は実行時間制限こそ比較的ゆるいものの、添字が非常に難しくバグりやすいです。また、オーバーフローにも注意しましょう。

上で議論した \((p,q)\) のパターン（各 \(x\) 座標について \(y\) 座標の最左だけ見る）についてだけ書けば、行列の \(x\) と \(y\) を入れ替えてマス目を \(w\times h\) にしたり、 \(x\) 座標をそれぞれ \(x \leftarrow h+1-x\)、 \(y\) 座標をそれぞれ \(y \leftarrow w+1-y\) に置き換えたりすることで結果的にすべての方向について試すことができます。これにより、繊細に気をつけるべき添字の箇所を減らすことができます。

実行時間は \(O(N \log N)\) です。