読者です 読者をやめる 読者になる 読者になる

アルゴリズム忘備録

競技プログラミングとかデータ分析とか

AtCoder Regular Contest 071 D 井井井 / ###

arc071.contest.atcoder.jp

 

x軸に平行な直線がm本、y軸に平行な直線n本、あり、それぞれのy座標、x座標はy[i], x[j] である。これらの交点を使って任意の長方形を作る。そういう長方形の面積の総和を求めよ。

 

x軸とy軸で独立して考える。x[i]からx[i - 1]の間の領域が長方形の面積として使われる回数は、その領域が含まれる長さすべてで、左右の頂点の数を書ければよく、 i * (n - i) 通り。なので、(x[i] - x[i - 1]) * i * (n - i) の総和を求める。

y軸も同様にして総和を求め、x軸の和とかけると答え。