SRM377 Div2 500

とぷこだ 過去問

問題

0からwidth、0からheightの長方形の内部にある整数のすべての点(x,y)の集合をrectangular latticeと定義する。このlatticeの4点のみを使って正方形の角の4点を決める時、できる正方形の個数を返す。

考え方

x,y軸に並行な正方形の数は、widthとheightで大きい方をn、小さい方をmとすると、

for(int i=1; i<=m; i++) ret += (m-i+1)*(n-i+1); //(1)

並行でない正方形の数は、2点を決定して、その正方形の個数を計算すると、

for(int i=1; i<m; i++){
  for(int j=1; j<m; j++){
    if(i+j<=m){
      ret += (m-(i+j)+1)*(n-(i+j)+1);
    }
  }
}

となるが、このままではTLEなので、さらに書き換えて、

for(int i=2; i<=m; i++) ret += (i-1)*(m-i+1)*(n-i+1); //(2)

とする。
上記の(1)と(2)を足したものが答えになる。
ちなみに、この2つをさらにまとめると、

for(int i=1; i<=m; i++) ret += (ll)(i)*(width-i+1)*(height-i+1);

だけでよい。