問題5 解説

 この問題に対する単純なアルゴリズムは,平面が頂点の座標が整数であるような 1 辺の長さが 1 の正方形のタイルからなっていると考えるやり方である.長方形を1つ入力するごとに,その長方形に含まれる各タイルの位置に印を付け,すべての長方形に対してそのような処理を終えてから,印の付いている正方形の個数を数えれば求める面積が得られる.さらに,こうして印が付けられたタイルそれぞれについて,その上下左右に隣接している 4 つのタイルに印が付いているか否かを調べることにより,出来上がった図形の周囲の長さも求めることができる. なぜなら,印が付いていないタイルに隣接する辺は,出来あがった図形の周上にあるので,そのような辺の本数を数えれば周の長さを知ることができるからである.しかし,この方法では多くの入力データでタイムオーバーになってしまう(そのように入力データを作成した).

 そこで,出来上がる図形 A を与えられたタイルを何枚か縦に張り合わせた x 軸方向の長さが 1 の縦長の長方形の集まりと考えてこの問題を解く方法を考えてみよう. 言い換えると,図形を間隔が 1 の y 軸に平行な直線で切り分けて考える. 以下, 左下の座標が (ax, ay) で右上の座標が (bx, by) である長方形を (ax, ay)×(bx, by) と表し,図形 A に対して, 直線 x = x0 と x = x0 + 1 に挟まれた部分を A[x0] と書くことにする. 一般には,A[x0] は y 軸方向の長さが 1 の長方形ではなく,それらいくつかの和になっていることに注意しよう.
 i 番目に入力された長方形を Si = (xi1, yi1)×(xi2, yi2) とする(i = 1, ・・・, ,N). A = S1∪S2∪・・・∪SN について(∪ は和を表す)

  A[x0] = S1[x0] ∪ S2[x0] ∪ ・・・ ∪ SN[x0]

が成り立つ.xi1 ≦ x0 < xi2 のとき Si [x0] = (x0, yi1)×(x0 + 1, yi2) であり,それ以外のとき空である.Ai = S1∪S2∪・・・∪Si に対して Ai [x0] が

  Ai[x0] = (x0, a1)×(x0 + 1, b1) ∪ (x0, a2)×(x0 + 1, b2) ∪ ・・・ ∪ (x0, am)×(x0 + 1, bm),
  a1<b1<a2<b2<・・・<am<bm

と表されていれば,Ai+1[x0] を求めるのは多少ややこしいが,それほど難しくはない.例えば, as<x(i+1) 1<bs かつ bt<x(i+1) 2<at+1 ならば

  Ai+1[x0] = { (x0, a1)×(x0 + 1, b1) ∪ (x0, a2)×(x0 + 1, b2) ∪ ・・・ ∪ (x0, as-1)×(x0 + 1, bs-1) }
        ∪ (x0, as)×(x0 + 1, x(i+2) 2)
        ∪ { (x0, at+1)×(x0 + 1, bt+1) ∪ (x0, at+2)×(x0 + 1, bt+2) ∪ ・・・ ∪ (x0, am)×(x0 + 1, bm) }

になる.したがって, 必要な全ての座標について A[x0] を計算することは可能である.さらに, 入力 S1, ・・・, SN をあらかじめ都合の良い順序に並べなおしておけば,さらに効率良く A[x0] を計算することが出来る.

  Ai[x0] = (x0, a1)×(x0 + 1, b1) ∪ (x0, a2)×(x0 + 1, b2) ∪ ・・・ ∪ (x0, am)×(x0 + 1, bm)

の面積は

  (b1 - a1) ∪ (b2 - a2) ∪ ・・・ ∪ (bm - am)

である.こうして,A[x0] = AN[x0] から A の面積を求めることができる:

  A の面積 = (A[0] の面積) ∪ (A[1] の面積) ∪ ・・・ ∪ (A[maxX -1] の面積)   (maxX は長方形の x 座標の最大値)

さらに A[x0] に含まれる A の周囲で x 軸に平行な辺の長さは 2k であり,y 軸に平行な辺は両隣り A[x0 - 1], A[x0 + 1] と共通の部分以外の辺であり,これも k に比例した時間で計算することができる.

 さて,A[x0] をプログラム上で実装するためには 線形リスト (linear list) を用いるとメモリ使用量に関しても実行時間に関しても効率が良い(A[0], A[1], ..., A[maxX - 1] それぞれを線形リストで表す必要があるので,それらへのポインタを要素とする配列を使う).線形リストとは,同じタイプの要素を並べた列

  <x1, x2, ..., xn>    (各 xi は同じ型のデータで,この線形リストの要素という)

のことであり,これらがポインタで

  root → x1 → x2 → ・・・ → xn  (root はリストの先頭を指すポインタ)

のようにリンクされているものである.したがって,xi にアクセスするには x1, x2, ..., xi の順にポインタに沿ってたどるしかない.ただし,線形リストを使うと,必要なデータしか保持しないので,メモリが効率よく使えるだけでなく,データへの総アクセス時間が結果的に短くなることが多い.この問題でも,最初に述べた方法では時間内に答が計算できない(計算に何時間もかかる)ような入力データに対しても,後で述べた方法を線形リストを使って実装すると十分短い時間内で計算が終わるように入力データを作った.ただし,この方法でも,特殊なデータに対してはかなり実行時間がかかってしまう場合があることを付記しておく.