SRM542 Div1 Easy - PatrolRoute
問題
x*yのグリッド上の3点a,b,cの選び方で、(ab間の距離)+(bc間の距離)+(ca間の距離)がmn以上mx以下になるようなものは何通りあるか
ただしa,b,cは全てx座標もy座標も異なる必要がある
3 <= x, y <= 4000
1 <= mn <= mx <= 20000
解法
(ab間の距離)+(bc間の距離)+(ca間の距離) ってのは、abcを内側(or境界)に含む最も小さい長方形の周の長さと言い換えられる
この長方形のサイズを全列挙することを考える
その長方形が3点を含む最小の長方形であるように3点を配置する方法は、distinctの制約を考えると、「4つの角のうちどれか1つの角に1点置いてもう2点で残り2辺をカバーする」か「対角に2点を置いてもう1点を好きな場所に置く」の2通りしかないことがわかる
あとはx*y内でその長方形を置くことができる場所の個数をかけて答えに足していけばいい
class PatrolRoute { public: int countRoutes(int x, int y, int mn, int mx) { ll res = 0; reps(h,3,x+1) reps(w,3,y+1) { int s = (h+w-2)*2; if (s<mn || mx<s) continue; ll p = (h-2)*(w-2)*4 + (h-2)*(w-2)*2; (res += p * (x-h+1) * (y-w+1)) %= mod; } return (int)res; } };