AtCoder ARC071C: 井井井 / ###

解を式で表してそれを簡単にする

(右端)-(左端)　の長さの重複を認めた集合をW,

(上端)-(下端)　の長さの重複を認めた集合をH,

とすると解は

Σw*h (w∈W, h∈H)

で表せる。

これにはよくある式変形により

Σw*h (w∈W, h∈W)

=Σw(w∈W) * Σh(h∈H)

たとえば

w0*h0+w0*h1+w1*h0+w1*h1

= (w0+w1)*(h0+h1)

のようになる。

辺の長さの和が求まれば解は求まりそう。問題は簡単になった。

辺の長さの和を求める

左右(x座標)について解ければ上下については同様。以下、左右についてのみ考える。

長さの和を求める

→ある縦の線分とその右隣の縦の線分の間の横の辺の使われる回数は？それと長さの積を出して和を取る。

要するに、縦棒で仕切られた横棒たちが何回使われるかを考えればいい。ある1個の横棒に注目する。この横棒の左にl個横棒があるとする。このとき、注目している横棒は0~l個分左に伸ばせる。同様に横棒が右にr個あるなら、0~r個分右に伸ばせる。よって、(l+1)*(r+1)個この横棒を使った辺がある。辺の長さを掛けて和を取ったものが辺の長さの和であった。これにより解は求まった。