第12回日本情報オリンピック 予選5

2012年12月21日
情報オリンピック日本委員会

問題
   魚の生息範囲 (Fish)

解説

海全体を 1 × 1 × 1 の小立方体 (整数 x, y, z に対し,2 点 (x, y, d), (x + 1, y + 1, d + 1) を向かい合う頂点とする立方体) に区切って考える.すると,各小立方体内では生息範囲が重なる魚の種類数は一定であるため,求める体積は K 種類以上の魚の生息範囲が重なる小立方体の個数である.よって,x, y, d についてループを回して,各々の小立方体に対して N 種類の魚のうち何種類の生息範囲が重なっているかを数え,K 種類以上ならば答えに足す,という方法で体積が求まる.しかし,各座標の値が 0 以上 1000000 以下であるため,この方法では調べるべき小立方体の個数が最大で 1000000^3 = 10^18 個にも及ぶため,満点を獲得することはできない.

上の解法の効率が悪さは,「区切りすぎ」という点にある.すべての整数値において区切るのではなく,入力に現れる座標値のみで区切ることを考える.具体的には,2N 個の値 X1,1, X1,2, X2,1, X2,2, …, XN,1, XN,2 を小さい順に並べ重複を取り除いたものを x0, x1, …, xA とする.y0, y1, …, yB および d0, d1, …, dC も同様に定める.海のうち x0 ≦ x ≦ xA,y0 ≦ y ≦ yB,d0 ≦ d ≦ dC である範囲を,2 点 (xj, yk, zl), (xj+1, yk+1, zl+1) (j = 0, 1, … A - 1,k = 0, 1, …, B - 1,l = 0, 1, …, C - 1) を向かい合う頂点とするような A × B × C 個の直方体に区切る.すると,これらの各直方体内では生息範囲が重なる魚の種類数は一定であるため,K 種類以上の魚の生息範囲が重なるものについて体積 (xj+1 - xj) × (yk+1 - yk) × (zl+1 - zl) を足していけばよい.この方法により,N4 に比例する時間でこの問題を解くことができる.N ≦ 50 であるから,十分高速であることがわかる.

この解法のように,入力に現れた座標値のみに着目して考えるような手法は「座標圧縮」と呼ばれ,しばしば用いられる.