問題:
\(10^5\) 行 \(10^5\) 列のグリッドがある。左から \(x\) マス目、下から \(y\) マス目を \((x,y)\) とする。
このうち \(N\) 個のマス \((X_i,Y_i)\) は黒く塗られている。
以下の条件を満たすマスの集合 \(S\) を、「適切」であるとする。
- 黒く塗られているマスは、全て \(S\) に含まれる。
- \(S\) に含まれる任意の2マス \(a(x_a,y_a)\ ,\ b(x_b,y_b)\) について、片方からもう片方に、\(S\)内の(辺を共有する)マスのみを伝って \(|x_a-x_b|+|y_a-y_b|\) 回の移動で移動可能である。
「適切」なマスの集合のうち、考えうる最小のサイズを \(t\) とする。
\(t\) を求め、さらにサイズが \(t\) であるような「適切」なマスの集合の数を \(\mod 10^9+7\) で数え上げよ。
小課題
1. (10点) \( X_i \le 5 , Y_i \le 4 \)
2. (30点) \(t\) だけ求めればよく、場合の数の数え上げはしなくてよい。
3. (60点) 追加の制約はない。
サンプル画像
このサンプルの場合、最小のサイズ \(t = 10\) となり、そのようなケースは \(2\) 通りあります。
まず、「適切」な集合とはどのようなものか、考えてみましょう。
画像の上側が元の点集合たち、下側がいくつかマスを補完して「適切」にする一例と思ってください。
これを見て、「凸包っぽい」というざっくりとした感想を抱きます。
正確には、各行最も左側の点、最も右側の点がそれぞれ山形になることがわかります。
それもそのはず、もし谷があっても、その谷の両端側を最短で移動可能にするためにその谷は潰れてしまうのです。
これを基に、「可能な最も右側の左端」「可能な最も左側の右端」を描きます。
「可能な最も右側の左端」は、点を左から順に見ていくことで凸包っぽく構成可能です。「可能な最も左側の右端」も同様。
言葉で伝えにくいので、図に書くとこんな感じ。
例えば、左から3番目の図だと、上から \( (1+3+3+1)=8 \) マス含むと \(S\) は最小で、一番右の図だと \( ... \)
\(...\)
困ります。困ってもらわないと困る。
「右端が左にあって左端が右にある」様相を見て困惑します。
でも、心配ご無用。このような場合は、この交差した部分の左下から右上を結ぶ最短経路を、ひとつ結んでやればよいです。この時に二項係数ぶんの場合の数が発生します。(勿論、右下から左上となる場合もありますが…)
もう少し大きな例も見ておきましょう。
左側の場合は \(3\) 通り、右側の場合は \(36\) 通りの条件を満たすマスの集合が考えられます。
あとは、この直感的な理解を実装に移すだけです。僕はかなりバグり散らかしたので頑張ってください。(例えば上下/左右反転しただけのケースでWAを出すなど…)
https://www.codechef.com/viewsolution/42632720
