最小値の最大化（二分探索）と、反転操作回数の最小化

面白い問題があったのでPythonで記載。

問題 1

N個の牛小屋について、M頭の牛を買っている。 x・・・牛小屋の位置 最も近い牛の間隔を最大化するためにどうするか

解法

最小・最大化問題について、収束判定するために二分探索が用いられるらしい --> 総当たり的な感じ

class IntervalOptimize(object):
    def __init__(self, N, M, x_):
        self.N = N
        self.M = M
        self.x_ = sorted(x_)
        self._max = max(self.x_)

    def assetion(self, d):
        last = 0
        for i in range(self.M):
            crt = last + 1
            while (crt < self.N) and (self.x_[crt] - self.x_[last] < d):
                crt += 1
            if crt > self.N:
                return False
            last = crt
        return True

    def solve(self):
        lb, ub = 0, self._max

        while ub - lb > 1:
            mid = (ub + lb) // 2
            if self.assetion(mid):
                lb = mid
            else:
                ub = mid

        return lb

In [114]: i = IntervalOptimize(5, 3, [1,2,8,4,9])

In [115]: i.solve()

Out[115]: 3

問題 2

N頭に並んでいる牛が前か後ろ向いている（1: 前、2: 後ろ）。 連続するK頭ずつ反転させることができる。 最小の操作回数Mと、それを達成するための最小のKを求めよ。

解法

反転する順番は順不同なため、はじめから順に反転させる。あとは、貪欲に。。

class CowReverse(object):
    def __init__(self, N, direction_):
        self.N = N
        self.direction_ = direction_

    def calc(self, k):
        f = [0 for i in range(self.N)]
        res = 0
        _sum = 0

        for i in range(self.N - k + 1):
            if (self.direction_[i] + _sum) % 2 != 0:
                res += 1
                f[i] = 1
            _sum += f[i]
            if i - k + 1 >= 0:
                _sum -= f[i - k + 1]

        for i in range(self.N - k + 1, self.N):
            if (self.direction_[i] + _sum) % 2 != 0:
                return -1
            _sum += f[i]
            if i - k + 1 >= 0:
                _sum -= f[i - k + 1]

        return res

    def solve(self):
        K = 1
        M = self.N
        for k in range(1, self.N + 1):
            m = self.calc(k)
            if m >= 0 and M > m:
                K = k
                M = m

        return '{:d} {:d}'.format(K, M)

In [126]: direction_list = '1101011'

In [134]: c =　CowReverse(len(direction_list), [int(i) for i in list(direction_list)])

In [135]: c.solve()
Out[135]: '3 3'