AOJ 0580 魚の生息範囲

問題へのリンク(AOJ)
問題へのリンク(AtCoder)

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3 2");
            WillReturn.Add("30 50 0 50 70 100");
            WillReturn.Add("10 20 20 70 90 60");
            WillReturn.Add("40 60 20 90 90 70");
            //49000
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 1");
            WillReturn.Add("0 0 0 1000000 1000000 1000000");
            //1000000000000000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    struct XYZInfoDef
    {
        internal long XSta;
        internal long YSta;
        internal long ZSta;
        internal long XEnd;
        internal long YEnd;
        internal long ZEnd;
    }
    static List<XYZInfoDef> mXYZInfoList = new List<XYZInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        SplitAct(InputList[0]);
        long K = wkArr[1];
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            XYZInfoDef WillAdd;
            WillAdd.XSta = wkArr[0];
            WillAdd.YSta = wkArr[1];
            WillAdd.ZSta = wkArr[2];
            WillAdd.XEnd = wkArr[3];
            WillAdd.YEnd = wkArr[4];
            WillAdd.ZEnd = wkArr[5];
            mXYZInfoList.Add(WillAdd);
        }

        var XSet = new HashSet<long>();
        XSet.UnionWith(mXYZInfoList.Select(pX => pX.XSta));
        XSet.UnionWith(mXYZInfoList.Select(pX => pX.XEnd));

        var YSet = new HashSet<long>();
        YSet.UnionWith(mXYZInfoList.Select(pX => pX.YSta));
        YSet.UnionWith(mXYZInfoList.Select(pX => pX.YEnd));

        var ZSet = new HashSet<long>();
        ZSet.UnionWith(mXYZInfoList.Select(pX => pX.ZSta));
        ZSet.UnionWith(mXYZInfoList.Select(pX => pX.ZEnd));

        Dictionary<long, long> ZaatuDictX = DeriveZaatuDict(XSet);
        Dictionary<long, long> ZaatuDictY = DeriveZaatuDict(YSet);
        Dictionary<long, long> ZaatuDictZ = DeriveZaatuDict(ZSet);

        // 3次元いもす法
        long[, ,] ImosArr = new long[XSet.Count, YSet.Count, ZSet.Count];
        long UB_X = ImosArr.GetUpperBound(0);
        long UB_Y = ImosArr.GetUpperBound(1);
        long UB_Z = ImosArr.GetUpperBound(2);
        foreach (XYZInfoDef EachXYZInfo in mXYZInfoList) {
            long ImosStaX = ZaatuDictX[EachXYZInfo.XSta];
            long ImosEndX = ZaatuDictX[EachXYZInfo.XEnd];
            long ImosStaY = ZaatuDictY[EachXYZInfo.YSta];
            long ImosEndY = ZaatuDictY[EachXYZInfo.YEnd];
            long ImosStaZ = ZaatuDictZ[EachXYZInfo.ZSta];
            long ImosEndZ = ZaatuDictZ[EachXYZInfo.ZEnd];

            ImosArr[ImosStaX, ImosStaY, ImosStaZ]++;
            ImosArr[ImosEndX, ImosStaY, ImosStaZ]--;
            ImosArr[ImosStaX, ImosEndY, ImosStaZ]--;
            ImosArr[ImosEndX, ImosEndY, ImosStaZ]++;

            ImosArr[ImosStaX, ImosStaY, ImosEndZ]--;
            ImosArr[ImosEndX, ImosStaY, ImosEndZ]++;
            ImosArr[ImosStaX, ImosEndY, ImosEndZ]++;
            ImosArr[ImosEndX, ImosEndY, ImosEndZ]--;
        }

        long[] ZaatuDictXKeysArr = ZaatuDictX.Keys.ToArray();
        long[] ZaatuDictYKeysArr = ZaatuDictY.Keys.ToArray();
        long[] ZaatuDictZKeysArr = ZaatuDictZ.Keys.ToArray();
        Array.Sort(ZaatuDictXKeysArr);
        Array.Sort(ZaatuDictYKeysArr);
        Array.Sort(ZaatuDictZKeysArr);

        // X方向の累積和を求める
        for (int X = 1; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                for (int Z = 0; Z <= UB_Z; Z++) {
                    ImosArr[X, Y, Z] += ImosArr[X - 1, Y, Z];
                }
            }
        }

        // Y方向の累積和を求める
        for (int Y = 1; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                for (int Z = 0; Z <= UB_Z; Z++) {
                    ImosArr[X, Y, Z] += ImosArr[X, Y - 1, Z];
                }
            }
        }

        // Z方向の累積和を求める
        for (int Z = 1; Z <= UB_Z; Z++) {
            for (int X = 0; X <= UB_X; X++) {
                for (int Y = 0; Y <= UB_Y; Y++) {
                    ImosArr[X, Y, Z] += ImosArr[X, Y, Z - 1];
                }
            }
        }

        long Answer = 0;
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                for (int Z = 0; Z <= UB_Z; Z++) {
                    if (ImosArr[X, Y, Z] >= K) {
                        long XDiff = ZaatuDictXKeysArr[X + 1] - ZaatuDictXKeysArr[X];
                        long YDiff = ZaatuDictYKeysArr[Y + 1] - ZaatuDictYKeysArr[Y];
                        long ZDiff = ZaatuDictZKeysArr[Z + 1] - ZaatuDictZKeysArr[Z];
                        Answer += XDiff * YDiff * ZDiff;
                    }
                }
            }
        }
        Console.WriteLine(Answer);
    }

    //////////////////////////////////////////////////////////////////////////
    // 列挙を引数として、座標圧縮し、座圧後の値[座圧前の値]なDictを返す
    //////////////////////////////////////////////////////////////////////////
    static Dictionary<long, long> DeriveZaatuDict(IEnumerable<long> pEnum)
    {
        var ZaatuDict = new Dictionary<long, long>();
        var ValSet = new HashSet<long>(pEnum);
        long No = 0;
        foreach (long EachVal in ValSet.OrderBy(pX => pX)) {
            ZaatuDict[EachVal] = No;
            No++;
        }
        return ZaatuDict;
    }
}

解説

魚は最大50匹で
50**3 = 125000
なのでX座標、Y座標、Z座標
をそれぞれ座標圧縮し、いもす法で区間加算してます。
その後、積分の考え方で体積を集計してます。

3次元いもす法でのZ座標への加減算は下記のようになります。

Z座標がMinのXY平面
＋□□−
□□□□
□□□□
−□□＋

Z座標がMaxのXY平面
−□□＋
□□□□
□□□□
＋□□−