二分探索の練習

二分探索の練習。
問題は「プログラミングコンテスト」「二分探索」あたりで適当にググったもの。

- UpperBoundとLowerBound
CのSTD関数をC#で実装。

public static int LowerBound(int[] ar, int val)
{
    var lb = -1;
    var ub = ar.Length;

    while (ub - lb > 1)
    {
        var mid = (lb + ub) / 2;
        if (ar[mid] >= val)
        {
            ub = mid;
        }
        else
        {
            lb = mid;
        }
    }

    return ub;
}

public static int UpperBound(int[] ar, int val)
{
    var lb = -1;
    var ub = ar.Length;

    while (ub - lb > 1)
    {
        var mid = (lb + ub) / 2;
        if (ar[mid] <= val)
        {
            lb = mid;
        }
        else
        {
            ub = mid;
        }
    }

    return lb + 1;
}

- Topcoder SRM676 Div1Easy(WaterTank)
https://community.topcoder.com/stat?c=problem_statement&pm=14019

Cリットル入る水がめと、配列tとxが与えられる。水がめには、t[i]の時間、x[i]リットルの水が注ぎこまれる。水がめが溢れないようになるべく小さい穴をあけたい。
この穴の単位時間あたりの水の排出量を求める。

配列の大きさは1～50、tとxは1～1,000,000、Cは1～10^9

LowerBoundと同じように二分探索する。
最初、1sごとにループするコードを書いてタイムアウトになってしまった。水の増え方が線形なので、t[i]単位でまとめて計算して問題ない。

public class WaterTank {
    double EPS = 1e-8;

    int[] t;
    int[] x;
    double C;

    bool NoOverflow(double rate)
    {
        var tank = 0.0;
        for (int n = 0; n < t.Length; n++)
        {
            //これだと間に合わない！
            //線形に増えるので1sごとにループする必要はない
            //var water = (double)x[n];
            //for (int sec = 0; sec < t[n]; sec++)
            //{
            //    tank += water;
            //    tank -= rate;
            //    if (tank > C) return false;
            //    if (tank < 0) tank = 0.0;
            //}

            tank += (double)x[n] * t[n];    //キャストを忘れない！（忘れてもサンプルテストは通る）
            tank -= rate * t[n];
            if (tank > C) return false;
            if (tank < 0) tank = 0.0;
        }

        return true;
    }

    public double minOutputRate(int[] pt, int[] px, int pC)
    {
        t = pt;
        x = px;
        C = (double)pC;

        double lb = 0.0, ub = 1000001.0;

        while (ub - lb > EPS)
        {
            var mid = (lb + ub) / 2;
            if (NoOverflow(mid))
                ub = mid;
            else
                lb = mid;
        }

        return ub;
    }
}

- Topcoder SRM456 Div2Hard(CutSticks)
https://community.topcoder.com/stat?c=problem_statement&pm=10563&rd=13909

いろいろな長さの棒sticks[]がある。そして最大でC回、棒を取り出して2つに割ることができる（割ってできた棒をさらに割ることもできる）。
最終的にできた棒を、増加しない順にならべて、K番目の棒を取り出す。このとき、その取り出した棒の最大長を求める。
なお、最低でもK本の棒ができるように、割っていく必要がある。

sticks[]の長さ：1～50
sticks[]の各要素：1～1000000000
C：1～1000000000
K:1～sticks[]の長さ+C

「ある長さにできるかどうか」を判定しながら二分探索する。
終了条件を上限と下限の差にすると無限ループになってしまうので、十分大きな固定回数のループにする。

public class CutSticks {
    double EPS = 1e-10;

    bool CanMake(double len, double[] sticks, int C, int K)
    {
        var cnt = 0;
        foreach (var stick in sticks)
        {
            if (stick - len > EPS)
            {
                var maxDevideNum = (int)(stick / len) - 1;
                var devideNum = Math.Min(C, maxDevideNum);

                cnt += (devideNum + 1);
                C -= devideNum;

                if (cnt >= K) return true;
            }
        }

        return false;
    }

    public double maxKth(int[] sticks, int C, int K) {
        double lb = 0;
        double ub = 1000000001;

        var dsticks = sticks.Select(a => (double)a).OrderByDescending(b => b).ToArray();

        //while(ub - lb > EPS)  //これだと (new int[] { 1000000000 }, 1000000000, 1) のケースで終了しない
        for (int i = 0; i < 500; i++)
        {
            var mid = (lb + ub) / 2;

            if (CanMake(mid, dsticks, C, K))
                lb = mid;
            else
                ub = mid;
        }

        return lb;
    }
}

- Topcoder SRM636 Div2Hard(ChocolateDividingHard)
https://community.topcoder.com/stat?c=problem_statement&pm=13388&rd=16079

チョコレートの板String[] chocolateがある。
chocolateの各char要素は、そのセルのクオリティを表している('0'～'9')。
縦に４つ、横に４つに割ったとき、１つの塊のクオリティの合計の最小値を最大にしたい。この値を答えよ。

chocolate[]の縦横の要素数は4～75

最大のクオリティを求める二分探索を行う。
その中で縦（または横）全パターンのループを回し、パターンごとにクオリティを満足する最小の横Indexを二分探索で求めていく。
横に4分割できればOK。

二分探索の中で二分探索をしていて、はまるとデバッグが大変になる問題だと思う。

public class ChocolateDividingHard {
    int[,] sums;
    int rowNum;
    int colNum;
    int sum;

    //row1 < row2, col1 < col2
    //(row1 + 1, col1 + 1) to (row2, col2)
    int GetArea(int row1, int row2, int col1, int col2)
    {
        var ret = sums[row2, col2] -
            (col1 >= 0 ? sums[row2, col1] : 0) -
            (row1 >= 0 ? sums[row1, col2] : 0) +
            (col1 >= 0 && row1 >= 0 ? sums[row1, col1] : 0);

        return ret;
    }

    bool CanDevide(int col1, int col2, int size, int[] rows)
    {
        for (int rowIdx = 0; rowIdx < rows.Length; rowIdx++)
        {
            var row1 = rowIdx > 0 ? rows[rowIdx - 1] : -1;
            var row2 = rows[rowIdx];
            if (GetArea(row1, row2, col1, col2) < size) return false;
        }
        return true;
    }

    int GetMinColIdx(int startIdx, int size, int[] rows)
    {
        //binary search (l, u]
        int l = startIdx - 1;   //ここを l = startIdx にすると、startIdxが答えの時に間違った解を返す！
        int u = colNum;

        while (l < u - 1)
        {
            var mid = (l + u) / 2;
            if (CanDevide(startIdx - 1, mid, size, rows))
                u = mid;
            else
                l = mid;
        }

        return (u == colNum) ? -1 : u;
    }

    bool CanDevide(int size, int[] rows)
    {
        var col = -1;
        for (int i = 0; i < 4; i++)
        {
            col = GetMinColIdx(col + 1, size, rows);
            if (col == -1) return false;
        }
        return true;
    }

    bool CanDevide(int size)
    {
        for (int row1 = 0; row1 < rowNum; row1++)
            for (int row2 = row1 + 1; row2 < rowNum; row2++)
                for (int row3 = row2 + 1; row3 < rowNum; row3++)
                    if (CanDevide(size, new int[] { row1, row2, row3, rowNum - 1 }))
                        return true;
        return false;
    }

    int findBest()
    {
        //binary search [l, u)
        int l = 0;
        int u = sum + 1;

        while (u > l + 1)
        {
            var mid = (l + u) / 2;

            if (CanDevide(mid))
                l = mid;
            else
                u = mid;
        }

        return l;
    }

    public int findBest(string[] chocolate) {
        rowNum = chocolate.Length;
        colNum = chocolate[0].Length;

        sums = new int[rowNum, colNum];
        for (int row = 0; row < rowNum; row++)
        {
            for (int col = 0; col < colNum; col++)
            {
                sums[row, col] = 
                    (row > 0 ? sums[row - 1, col] : 0) +
                    (col > 0 ? sums[row, col - 1] : 0) +
                    ((int)(chocolate[row][col] - '0')) -
                    (row > 0 && col > 0 ? sums[row - 1, col - 1] : 0);
                sum += (int)(chocolate[row][col] - '0');
            }
        }

        return findBest();
    }
}