ABC058/ARC071 D問題解説

D - 井井井 / ###

問題のURLはこちらです。
D: 井井井 / ### - AtCoder Regular Contest 071 | AtCoder

問題概要

2 次元平面上に x 軸と平行な直線が m 本と y 軸と平行な直線が n 本引いてあります。
この中に存在しているすべての長方形についてその面積を求め、 合計を 10^9+7 で割ったあまりを出力してください。

考えたこと

途中でか日本語力が無くなりました。たぶん解説になってないです。

とします。
まず高さがy0の長方形の面積の合計を考えます。

x0*y0 + (x0+x1)*y0 + x1*y0 + ... = y0*(x0 + ((x0+ x1) + x1) + ((x0 + x1 + x2) + (x1 + x2) + x2))

省略がある上に分かりにくい！（ごめんなさい）
とりあえずy0で括れることが分かれば良いです。
長方形の幅にあたるなにやら良く分からないかっこの中身だけ考えましょう。
長方形の幅はそれぞれ

x0
x0 + x1
     x1
x0 + x1 + x2
     x1 + x2
          x2

になります。
x3まであるとすると、

x0
x0 + x1
     x1
x0 + x1 + x2
     x1 + x2
          x2
x0 + x1 + x2 + x3
     x1 + x2 + x3
          x2 + x3
               x3

になります。
かっこの中身はこれの合計です。

次にyを動かしてみましょう。
あるyの取り方を決めるとx方向の取り方は常に先ほど求めた長方形の幅の合計になります。
よって、長方形の幅の合計をWとしたときに、長方形の面積の合計は

y0*W + (y0+y1)*W + y1*W=W*(y0 + ((y0+y1)+y1))

になります。
つまりWで括れます。
yのかっこの中身は高さですが、これもxと同様に、

y0
y0 + y1
     y1

の合計になります。
これをHとすると、H*Wで答えが求まりそうです。

しかし、xnまであるとして、幅の総数はn(n+1)/2個あるので、愚直に計算していると間に合わないことが分かります。

x2まで使ったときの幅の合計と、x3まで使ったときの幅の合計の差分は

x0
x0 + x1
     x1
x0 + x1 + x2
     x1 + x2
          x2
x0 + x1 + x2 + x3
     x1 + x2 + x3
          x2 + x3
               x3

これを見ると分かりやすいですが、>||x1->x2の差分 + (3+1)*x3||<です。証明は出来ると思います。
というわけでこの方法で計算するとO(N)になります。

yにも同じことをやるだけなので、全体でO(N+M)です。

コード(C++)

http://arc071.contest.atcoder.jp/submissions/1208594

//mintは自動でmod10^9+7をとってくれる整数型です。
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
 
	in >> N>>M;
	int32_t TMP_BEF;//直前の加算分
	mint bef;
	mint xsum, ysum;
	in >> TMP_BEF;
	for (int32_t i = 1; i <= N-1; ++i)
	{
		int32_t tmp;
		in >> tmp;
		mint v = tmp-TMP_BEF;//区間の長さ
		TMP_BEF = tmp;
		auto add = bef + v*i;
		xsum += add;
		bef = add;
	}
	bef = 0;
	in >> TMP_BEF;
	for (int32_t i = 1; i <= M-1; ++i)
	{
		int32_t tmp;
		in >> tmp;
		mint v = tmp - TMP_BEF;
		TMP_BEF = tmp;
		auto add = bef + v*i;
		ysum += add;
		bef = add;
	}
	out << xsum*ysum << endl;
 
	return 0;
}