parukii https://blog.hatena.ne.jp/parukii/ parukiのブログ https://par.hateblo.jp/ 解を式で表してそれを簡単にする (右端)-(左端) の長さの重複を認めた集合を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座標)について解ければ上下については同様。以下、左右についてのみ考える。 長さの和を求める →ある縦の線分… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpar.hateblo.jp%2Fentry%2F2017%2F04%2F09%2F231324" title="AtCoder ARC071C: 井井井 / ### - parukiのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2017-04-09 23:13:24 rich https://par.hateblo.jp/entry/2017/04/09/231324 1.0 100%