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

Python3

面白い問題があったので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'

最小全域木問題について（プリム法）

Python3 
class MinimumSpanningTree(object):
    def __init__(self, v):
        self.v = v
        self.e = 0
        self.mincost = [float("inf") for i in range(v)]
        self.cost = [[float("inf") for i in range(v)] for i in range(v)]
        self.used = [0 for  i in range(v)]

    def append(self, _from, _to, _cost):
        self.cost[_from][_to] = _cost
        self.e += 1

    def prim(self):
        res = 0
        self.mincost = [float("inf") for i in range(v)]
        self.used = [0 for  i in range(v)]

        self.mincost[0] = 0

        while 1:
            v = -1
            for u in range(self.v):
                if not self.used[u] and (v == -1 or self.mincost[u] < self.mincost[v]):
                    v = u

            if v == -1:
                break

            self.used[v] = 1
            res += self.mincost[v]

            for u in range(self.v):
                self.mincost[u] = min(self.mincost[u], self.cost[v][u])

        return res

    def append_test(self):
        self.append(0, 2, 1)
        self.append(1, 2, 2)
        self.append(1, 4, 10)
        self.append(2, 0, 1)
        self.append(2, 1, 2)
        self.append(2, 3, 3)
        self.append(2, 5, 7)
        self.append(3, 2, 3)
        self.append(3, 5, 1)
        self.append(3, 6, 5)
        self.append(4, 1, 10)
        self.append(4, 5, 5)
        self.append(5, 2, 7)
        self.append(5, 3, 1)
        self.append(5, 4, 4)
        self.append(5, 6, 8)
        self.append(6, 3, 5)
        self.append(6, 5, 8)

pip install で詰まった時の話

Python3 Python2

python2.6 の pip install で詰まった時の話。 HTTP Error 403: SSL is required

http://pypi.python.org/simple/ で pip install しようとしている場合、 以下で指定すると、うまくいく。

$ pip install xxxx -i https://pypi.python.org/simple/

$ pip install git+https://github.com/<user>/<project>

stackoverflow.com

プロセス監視する時の /service 配下の設定とか

Linux

daemontoolsをインストールして、ごちょごちょ設定行う。
スティッキービットを立てるとか言うらしい。

$ chmod +t test_job

keisyu.hateblo.jp

daemontools howto

大きく分けると...らしい。

  • svscan サービスディレクトリの監視
  • supervise プロセスの監視および制御
  • multilog ロギング

http://cr.yp.to/daemontools.html