座標圧縮領域の個数蟻本読書会

ひとりで勝手にはじめた蟻本読書会半分全列挙全探索を高速化するテクニック蟻本読書会の続きです。

座標圧縮とは数列 A[0], A[0], …, A[N-1] が与えられたときに、それぞれの要素が全体の中で何番目に小さいかを求める処理のことです。値の大小関係を保ったまま小さな自然数に変換できます。

たとえば以下のような問題だと H, W の値が小さい場合は2次元配列をつかって幅優先探索で解く方法があります。マスキングテープで覆われていないセルで連続したものを選択しつづけることで領域の数を取得することができるわけです。ところが H, W の上限が 1,000,000 と大きいと2次元配列を宣言しようとしてもメモリーが足りません。このようなときに座標圧縮の処理をすることで問題を解くことができるようになります。

Contents

1 E – ペンキの色
2 C – Reorder Cards
3 E – 魚の生息範囲 (Fish)

E – ペンキの色

長方形のベニヤ板にペンキを塗り看板を制作したい。ベニヤ板には色を塗りたくないところにあらかじめ何枚かの長方形のマスキングテープ（図の灰色の部分）が貼られている。マスキングテープで区切られた領域ごとに別々の色を使いペンキを塗る。図なら 4 色のペンキを使う。

入力としてマスキングテープを貼る位置が与えられた時、使うペンキの色の数を求めるプログラムを作成せよ。ただしベニヤ板全体がマスキングテープで覆われることはなく、全てのマスキングテープの辺はベニヤ板のいずれかの辺に平行である。

入力されるデータ
W H
N
a_1 b_1 c_1 d_1
a_2 b_2 c_2 d_2
…
a_N b_N c_N d_N

（ただし、
W はベニヤ板の幅
H はベニヤ板の高さ
N はマスキングテープの数
a_i, b_i c_i d_i
i 番目に貼るマスキングテープの左下の座標 (a_i, b_i) と右上の座標 (c_i, d_i)

1 ≦ W, H ≦ 1,000,000
1 ≦ N ≦ 1000
0 ≦ a_i ＜ c_i ≦ W
0 ≦ b_i ＜ d_i ≦ H ）

数列 A を座標圧縮をするときは A のなかの重複する値を削除したあと、昇順ソート（小さい順に並べ替える）します。そのあと先頭から取り出せばインデックスが座標圧縮後の値になっています。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int W, H;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            W = vs[0];
            H = vs[1];
        }

        int N = int.Parse(Console.ReadLine());

        int[] A = new int[N];
        int[] B = new int[N];
        int[] C = new int[N];
        int[] D = new int[N];

        for (int i = 0; i < N; i++)
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            A[i] = vs[0];
            B[i] = vs[1];
            C[i] = vs[2];
            D[i] = vs[3];
        }

        // 配列 A と C を座標圧縮する
        List<int> X = new List<int>();
        X.Add(0); // 最小値
        X.AddRange(A);
        X.AddRange(C);
        X.Add(W - 1); // 最大値

        X = X.Distinct().OrderBy(_ => _).ToList();

        // ソート後の配列のインデックスと要素の値をセットに
        Dictionary<int, int> dicX = new Dictionary<int, int>();
        for (int i = 0; i < X.Count; i++)
            dicX.Add(X[i], i);

        // 配列 A, C の値を変更
        for (int i = 0; i < A.Length; i++)
            A[i] = dicX[A[i]];
        for (int i = 0; i < C.Length; i++)
            C[i] = dicX[C[i]];

        // 同様に配列 B と D も座標圧縮する
        List<int> Y = new List<int>();
        Y.Add(0);
        Y.AddRange(B);
        Y.AddRange(D);
        Y.Add(H - 1);

        Y = Y.Distinct().OrderBy(_ => _).ToList();

        Dictionary<int, int> dicY = new Dictionary<int, int>();
        for (int i = 0; i < Y.Count; i++)
            dicY.Add(Y[i], i);

        for (int i = 0; i < B.Length; i++)
            B[i] = dicY[B[i]];
        for (int i = 0; i < D.Length; i++)
            D[i] = dicY[D[i]];

        // H と W も忘れずに座標圧縮する
        H = dicY[H - 1] + 1;
        W = dicX[W - 1] + 1;

        // 未訪問のセルがなくなるまで幅優先探索を繰り返す
        bool[,] isCheck = new bool[H, W];

        // マスキングテープが貼られている部分は訪問済みとする
        for (int i = 0; i < N; i++)
        {
            for (int row = B[i]; row < D[i]; row++)
            {
                for (int col = A[i]; col < C[i]; col++)
                    isCheck[row, col] = true;
            }
        }

        // 未訪問のセルを見つけたら上下左右でつながっているセルに幅優先探索で訪問する
        // 繰り返すことができた回数が解である。
        Queue<int> qX = new Queue<int>();
        Queue<int> qY = new Queue<int>();

        int count = 0;
        for (int row = 0; row < H; row++)
        {
            for (int col = 0; col < W; col++)
            {
                if (isCheck[row, col])
                    continue;

                count++;
                isCheck[row, col] = true;
                qX.Enqueue(col);
                qY.Enqueue(row);

                while (qX.Count > 0)
                {
                    int x = qX.Dequeue();
                    int y = qY.Dequeue();
                    int[] dx = { 0, 0, 1, -1 };
                    int[] dy = { 1, -1, 0, 0 };
                    for (int i = 0; i < 4; i++)
                    {
                        int nx = x + dx[i];
                        int ny = y + dy[i];
                        if(nx < 0 || nx >= W || ny < 0 || ny >= H)
                            continue;
                        if (isCheck[ny, nx])
                            continue;

                        qX.Enqueue(nx);
                        qY.Enqueue(ny);
                        isCheck[ny, nx] = true;
                    }
                }
            }
        }
        Console.WriteLine(count);
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int W, H;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

W = vs[0];

H = vs[1];

}

int N = int.Parse(Console.ReadLine());

int[] A = new int[N];

int[] B = new int[N];

int[] C = new int[N];

int[] D = new int[N];

for (int i = 0; i < N; i++)

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

A[i] = vs[0];

B[i] = vs[1];

C[i] = vs[2];

D[i] = vs[3];

}

// 配列 A と C を座標圧縮する

List<int> X = new List<int>();

X.Add(0); // 最小値

X.AddRange(A);

X.AddRange(C);

X.Add(W - 1); // 最大値

X = X.Distinct().OrderBy(_ => _).ToList();

// ソート後の配列のインデックスと要素の値をセットに

Dictionary<int, int> dicX = new Dictionary<int, int>();

for (int i = 0; i < X.Count; i++)

dicX.Add(X[i], i);

// 配列 A, C の値を変更

for (int i = 0; i < A.Length; i++)

A[i] = dicX[A[i]];

for (int i = 0; i < C.Length; i++)

C[i] = dicX[C[i]];

// 同様に配列 B と D も座標圧縮する

List<int> Y = new List<int>();

Y.Add(0);

Y.AddRange(B);

Y.AddRange(D);

Y.Add(H - 1);

Y = Y.Distinct().OrderBy(_ => _).ToList();

Dictionary<int, int> dicY = new Dictionary<int, int>();

for (int i = 0; i < Y.Count; i++)

dicY.Add(Y[i], i);

for (int i = 0; i < B.Length; i++)

B[i] = dicY[B[i]];

for (int i = 0; i < D.Length; i++)

D[i] = dicY[D[i]];

// H と W も忘れずに座標圧縮する

H = dicY[H - 1] + 1;

W = dicX[W - 1] + 1;

// 未訪問のセルがなくなるまで幅優先探索を繰り返す

bool[,] isCheck = new bool[H, W];

// マスキングテープが貼られている部分は訪問済みとする

for (int i = 0; i < N; i++)

{

for (int row = B[i]; row < D[i]; row++)

{

for (int col = A[i]; col < C[i]; col++)

isCheck[row, col] = true;

}

// 未訪問のセルを見つけたら上下左右でつながっているセルに幅優先探索で訪問する

// 繰り返すことができた回数が解である。

Queue<int> qX = new Queue<int>();

Queue<int> qY = new Queue<int>();

int count = 0;

for (int row = 0; row < H; row++)

{

for (int col = 0; col < W; col++)

{

if (isCheck[row, col])

continue;

count++;

isCheck[row, col] = true;

qX.Enqueue(col);

qY.Enqueue(row);

while (qX.Count > 0)

{

int x = qX.Dequeue();

int y = qY.Dequeue();

int[] dx = { 0, 0, 1, -1 };

int[] dy = { 1, -1, 0, 0 };

for (int i = 0; i < 4; i++)

{

int nx = x + dx[i];

int ny = y + dy[i];

if(nx < 0 || nx >= W || ny < 0 || ny >= H)

continue;

if (isCheck[ny, nx])

continue;

qX.Enqueue(nx);

qY.Enqueue(ny);

isCheck[ny, nx] = true;

}

Console.WriteLine(count);

}

C – Reorder Cards

H 行 W 列の格子状に H × W 枚のカードが並べられています。i = 1, …, N について、上から A_i 行目、左から B_i 列目にあるカードには数 i が書かれており、それ以外の H × W – N 枚のカードには何も書かれていません。

これらのカードに対し、以下の 2 種類の操作を可能な限り繰り返します。

数の書かれたカードを含まない行が存在するとき、その行のカードを全て取り除き、残りのカードを上へ詰める
数の書かれたカードを含まない列が存在するとき、その列のカードを全て取り除き、残りのカードを左へ詰める

操作が終了したとき、数が書かれたカードがそれぞれどこにあるか求めてください。

N 行出力せよ。操作終了後に数 i が書かれたカードが上から C_i 行目、左から D_i 列目に存在するとき、i 行目には C_i, D_i をこの順に空白区切りで出力せよ。

入力されるデータ
H W N
A_1 B_1
A_2 B_2
　…
A_N B_N

（ただし、1 ≦ H, W ≦ 10^9
1 ≦ N ≦ min(10^5, H × W)
1 ≦ A_i ≦ H, 1 ≦ B_i ≦ W ）

座標圧縮のアルゴリズムを考えれば、座標圧縮によって取り除くべき行と列が取り除かれることに気づきます。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int H, W, N;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            H = vs[0];
            W = vs[1];
            N = vs[2];
        }

        int[] A = new int[N];
        int[] B = new int[N];

        for (int i = 0; i < N; i++)
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            A[i] = vs[0];
            B[i] = vs[1];
        }

        // 前問と同じように座標圧縮する
        // 前問では最初の行（列） と 最終行（列）は無条件に追加したが、
        // 今回は数の書かれたカードが存在しないなら追加しない。
        List<int> Y = new List<int>();
        Y.AddRange(A);

        Y = Y.Distinct().OrderBy(_ => _).ToList();

        Dictionary<int, int> dicY = new Dictionary<int, int>();
        for (int i = 0; i < Y.Count; i++)
            dicY.Add(Y[i], i);

        for (int i = 0; i < A.Length; i++)
            A[i] = dicY[A[i]];

        List<int> X = new List<int>();
        X.AddRange(B);

        X = X.Distinct().OrderBy(_ => _).ToList();

        Dictionary<int, int> dicX = new Dictionary<int, int>();
        for (int i = 0; i < X.Count; i++)
            dicX.Add(X[i], i);

        for (int i = 0; i < B.Length; i++)
            B[i] = dicX[B[i]];

        for (int i = 0; i < N; i++)
            Console.WriteLine($"{A[i] + 1} {B[i] + 1}"); // ここでは座標は 1 から始まるので
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int H, W, N;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

H = vs[0];

W = vs[1];

N = vs[2];

}

int[] A = new int[N];

int[] B = new int[N];

for (int i = 0; i < N; i++)

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

A[i] = vs[0];

B[i] = vs[1];

}

// 前問と同じように座標圧縮する

// 前問では最初の行（列）と最終行（列）は無条件に追加したが、

// 今回は数の書かれたカードが存在しないなら追加しない。

List<int> Y = new List<int>();

Y.AddRange(A);

Y = Y.Distinct().OrderBy(_ => _).ToList();

Dictionary<int, int> dicY = new Dictionary<int, int>();

for (int i = 0; i < Y.Count; i++)

dicY.Add(Y[i], i);

for (int i = 0; i < A.Length; i++)

A[i] = dicY[A[i]];

List<int> X = new List<int>();

X.AddRange(B);

X = X.Distinct().OrderBy(_ => _).ToList();

Dictionary<int, int> dicX = new Dictionary<int, int>();

for (int i = 0; i < X.Count; i++)

dicX.Add(X[i], i);

for (int i = 0; i < B.Length; i++)

B[i] = dicX[B[i]];

for (int i = 0; i < N; i++)

Console.WriteLine($"{A[i] + 1} {B[i] + 1}"); // ここでは座標は 1 から始まるので

}

E – 魚の生息範囲 (Fish)

海の中に N 種類の魚がいる。それぞれの魚には直方体状の生息範囲が定まっている。魚は境界も含めて生息範囲の中のどの場所にも移動できるが、生息範囲の外に出ることは決してない。海の中の点は 3 つの実数 (x, y, d) によって表される。
(x, y, d) は上空から見たときにある地点を基準にして東に x、北に y 進んだ位置であり、海面からの深さが d の点を表す。ただし海面は平面であるとする。

K 種類以上の魚の生息範囲が重なる場所がどのくらいあるかを知りたい。そのような場所全体の体積を求めるプログラムを作成せよ。

N K
a_1 b_1 c_1 d_1 e_1 f_1
a_2 b_2 c_2 d_2 e_2 f_2

a_N b_N c_N d_N e_N f_N

（ただし、1 ≦ K ≦ N ≦ 50
魚は N 種類であり、K 種類以上の魚の生息範囲が重なる場所の体積を求めたいことを表す。
魚 i は a_i ≦ X ≦ d_i, b_i ≦ Y ≦ e_i, c_i ≦ Z ≦ f_i をみたす XYZ 座標のなかにいる。
0 ≦ a_i ＜ d_i ≦ 1,000,000
0 ≦ b_i ＜ e_i ≦ 1,000,000
0 ≦ c_i ＜ f_i ≦ 1,000,000 ）

これも座標圧縮する問題です。3次元配列を定義して何種類の魚がいるのかを調べますが、最大で 1,000,000 だと配列用のメモリーが足りません。しかし座標圧縮をすることで使用するメモリーを減らすことができます。

辞書で座標圧縮する前の座標としたあとの座標を高速で求めることができるようにしています。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int N, K;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            N = vs[0];
            K = vs[1];
        }

        List<int> X1 = new List<int>();
        List<int> Y1 = new List<int>();
        List<int> Z1 = new List<int>();
        List<int> X2 = new List<int>();
        List<int> Y2 = new List<int>();
        List<int> Z2 = new List<int>();

        List<int> X = new List<int>();
        List<int> Y = new List<int>();
        List<int> Z = new List<int>();
        for (int i = 0; i < N; i++)
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            X1.Add(vs[0]);
            Y1.Add(vs[1]);
            Z1.Add(vs[2]);
            X2.Add(vs[3]);
            Y2.Add(vs[4]);
            Z2.Add(vs[5]);
            X.Add(vs[0]);
            Y.Add(vs[1]);
            Z.Add(vs[2]);
            X.Add(vs[3]);
            Y.Add(vs[4]);
            Z.Add(vs[5]);
        }

        X = X.Distinct().OrderBy(_ => _).ToList();
        Y = Y.Distinct().OrderBy(_ => _).ToList();
        Z = Z.Distinct().OrderBy(_ => _).ToList();

        Dictionary<int, int> dicX = new Dictionary<int, int>(); // 圧縮前から圧縮後の座標を取得する
        Dictionary<int, int> dicX2 = new Dictionary<int, int>(); // 圧縮後から圧縮前の座標を取得する
        for (int i = 0; i < X.Count; i++)
        {
            dicX.Add(X[i], i);
            dicX2.Add(i, X[i]);
        }

        Dictionary<int, int> dicY = new Dictionary<int, int>();
        Dictionary<int, int> dicY2 = new Dictionary<int, int>();
        for (int i = 0; i < Y.Count; i++)
        {
            dicY.Add(Y[i], i);
            dicY2.Add(i, Y[i]);
        }

        Dictionary<int, int> dicZ = new Dictionary<int, int>();
        Dictionary<int, int> dicZ2 = new Dictionary<int, int>();
        for (int i = 0; i < Z.Count; i++)
        {
            dicZ.Add(Z[i], i);
            dicZ2.Add(i, Z[i]);
        }

        // 座標圧縮して3次元配列を定義する
        int[,,] arr = new int[dicX.Count, dicY.Count, dicZ.Count];

        for (int i = 0; i < N; i++)
        {
            // XYZ座標から座標圧縮したあとの座標を求め、魚の種類数を配列に記録する
            int cx1 = dicX[X1[i]];
            int cx2 = dicX[X2[i]];

            int cy1 = dicY[Y1[i]];
            int cy2 = dicY[Y2[i]];

            int cz1 = dicZ[Z1[i]];
            int cz2 = dicZ[Z2[i]];

            for (int cx = cx1; cx < cx2; cx++)
            {
                for (int cy = cy1; cy < cy2; cy++)
                {
                    for (int cz = cz1; cz < cz2; cz++)
                        arr[cx, cy, cz]++;
                }
            }
        }

        // 配列から K 種類以上の魚がいる座標を調べる。
        // 圧縮前の座標を求め、該当する要素の体積を求める。
        // その体積の総和が求めるべき解となる。
        long ans = 0;
        for (int cx = 0; cx < dicX.Count; cx++)
        {
            for (int cy = 0; cy < dicY.Count; cy++)
            {
                for (int cz = 0; cz < dicZ.Count; cz++)
                {
                    if (arr[cx, cy, cz] >= K)
                    {
                        long w = dicX2[cx + 1] - dicX2[cx];
                        long h = dicY2[cy + 1] - dicY2[cy];
                        long d = dicZ2[cz + 1] - dicZ2[cz];
                        ans += w * h * d;
                    }
                }
            }
        }
        Console.WriteLine(ans);
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int N, K;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

N = vs[0];

K = vs[1];

}

List<int> X1 = new List<int>();

List<int> Y1 = new List<int>();

List<int> Z1 = new List<int>();

List<int> X2 = new List<int>();

List<int> Y2 = new List<int>();

List<int> Z2 = new List<int>();

List<int> X = new List<int>();

List<int> Y = new List<int>();

List<int> Z = new List<int>();

for (int i = 0; i < N; i++)

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

X1.Add(vs[0]);

Y1.Add(vs[1]);

Z1.Add(vs[2]);

X2.Add(vs[3]);

Y2.Add(vs[4]);

Z2.Add(vs[5]);

X.Add(vs[0]);

Y.Add(vs[1]);

Z.Add(vs[2]);

X.Add(vs[3]);

Y.Add(vs[4]);

Z.Add(vs[5]);

}

X = X.Distinct().OrderBy(_ => _).ToList();

Y = Y.Distinct().OrderBy(_ => _).ToList();

Z = Z.Distinct().OrderBy(_ => _).ToList();

Dictionary<int, int> dicX = new Dictionary<int, int>(); // 圧縮前から圧縮後の座標を取得する

Dictionary<int, int> dicX2 = new Dictionary<int, int>(); // 圧縮後から圧縮前の座標を取得する

for (int i = 0; i < X.Count; i++)

{

dicX.Add(X[i], i);

dicX2.Add(i, X[i]);

}

Dictionary<int, int> dicY = new Dictionary<int, int>();

Dictionary<int, int> dicY2 = new Dictionary<int, int>();

for (int i = 0; i < Y.Count; i++)

{

dicY.Add(Y[i], i);

dicY2.Add(i, Y[i]);

}

Dictionary<int, int> dicZ = new Dictionary<int, int>();

Dictionary<int, int> dicZ2 = new Dictionary<int, int>();

for (int i = 0; i < Z.Count; i++)

{

dicZ.Add(Z[i], i);

dicZ2.Add(i, Z[i]);

}

// 座標圧縮して3次元配列を定義する

int[,,] arr = new int[dicX.Count, dicY.Count, dicZ.Count];

for (int i = 0; i < N; i++)

{

// XYZ座標から座標圧縮したあとの座標を求め、魚の種類数を配列に記録する

int cx1 = dicX[X1[i]];

int cx2 = dicX[X2[i]];

int cy1 = dicY[Y1[i]];

int cy2 = dicY[Y2[i]];

int cz1 = dicZ[Z1[i]];

int cz2 = dicZ[Z2[i]];

for (int cx = cx1; cx < cx2; cx++)

{

for (int cy = cy1; cy < cy2; cy++)

{

for (int cz = cz1; cz < cz2; cz++)

arr[cx, cy, cz]++;

}

// 配列から K 種類以上の魚がいる座標を調べる。

// 圧縮前の座標を求め、該当する要素の体積を求める。

// その体積の総和が求めるべき解となる。

long ans = 0;

for (int cx = 0; cx < dicX.Count; cx++)

{

for (int cy = 0; cy < dicY.Count; cy++)

{

for (int cz = 0; cz < dicZ.Count; cz++)

{

if (arr[cx, cy, cz] >= K)

{

long w = dicX2[cx + 1] - dicX2[cx];

long h = dicY2[cy + 1] - dicY2[cy];

long d = dicZ2[cz + 1] - dicZ2[cz];

ans += w * h * d;

}

Console.WriteLine(ans);

}

座標圧縮領域の個数蟻本読書会

E – ペンキの色

C – Reorder Cards

E – 魚の生息範囲 (Fish)

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ