SRM542 Div.1 - Isa@Diary

結果

不参加でした。

250

xy平面上(0<=x<=w、0<=y<=h)の格子点から3点a,b,cを取って、
a->b->c->aの道のり(移動は軸に並行のみ)がminT以上maxT以下になる
a,b,cの置き方の総数を求めよ。という問題。

a,b,cの道のりはa,b,cを内包(辺上を含む)する最小の長方形の周の長さに等しい。

┌--A--┐
│     |
B      |
└-----C

イメージ的にはこんな感じ。
3点でタテH,ヨコWの長方形を作ろうとすると、少なくとも1点はいずれかの頂点に
くる必要がある。(2辺を決める点になる)
1点のみ頂点に来る場合は残り1点ずつで1本ずつの辺を決めるので
その点の決め方は(W-1)*(H-1)となる
どの頂点に置くかで更に*4通り

↓左と上の点を決める点A
・─────┐
│　　　　　・←点Cはこの2点のうちから1つ
│　　　　　│
│　　　　　・
└・─・─・┘
　↑点Bはこの3点のうちから1つ

対角線上の2頂点にA,Bを配置する場合は、
Cは長方形の内部ならばどこでもいいので(W-1)*(H-1)通り、対角線上の2頂点の選び方で
更に*2
合計(W-1)*(H-1)*6通りの並べ方がある。
更に、このW*Hの長方形をxy平面上のどこに置くかで(w-W+1)*(h-H+1)通りあるので、
全てのW,H(minT<=(W+H)*2 && (W+H)*2 <= maxT)に対する(W-1)*(H-1)*6*(w-W+1)*(h-H+1)の和を返せばいい。

用心していっぱいMOD取る+Javaだと4000^2で落ちるケースを見かけた。