蟻本初級編攻略 - 2-2 Saruman's Army

蟻本の貪欲法で「交換しても悪化しないことがわかっている中で最大のものをとる」という考えの例題：

Saruman's Army - POJ 3069 - Virtual Judge

直線上に配置された人のうち最小何人選べば、すべての人が選ばれた人の一定距離内におさまるかを求める問題。

左端の人から一定距離以内でもっとも右側の人を選び、「その人から一定距離外でもっとも左側の人」から一定距離以内でもっとも右側の人を選び、とやり続ける：

def saruman(xs, r):
    bearer, edge = False, xs[0]
    for x, y in zip(xs, xs[1:]):
        while y > edge + r:
            if not bearer:
                yield x
                bearer, edge = True, x
            else:
                bearer, edge = False, y
    if not bearer:
        yield y

while True:
    r, n = map(int, input().split())
    if r == n == -1:
        break
    xs = sorted(int(x) for x in input().split())
    print(len(list(saruman(xs, r))))

ちょっとロジックがコードからはわかりにくい。まだ最適な記述を見つけていない気がする。やっぱり添字が一番か？

基本的にPythonでは記述上添字でループを回すことは少ないのだが（Cで実装されているCPythonインタプリタは当然裏で添字でループを回している）、こういう問題の場合は添字が自然な気がする。どういう条件下では添字がベストになるんだろう・・・

それではAtCoderの類題を解いていく。

ABC083C - Multiple Gift

abc083.contest.atcoder.jp

X以上Y以下の数で構成された数列で、n個目の数はn-1個目の数の倍数かずn-1個目の数より真に大きい。この制約で最大の長さを求める。

一回ごとの増加を最低に抑えるのが貪欲ポイント。とすると倍数は２。Xに何回2をかけてY以下に収められるか。

from itertools import count, takewhile
 
x, y = map(int, input().split())
 
print(max(takewhile(lambda i: x * (2**i) <= y,  count())) + 1)

頑張ればO(1)にできたと思うのだが、とりあえずO(log N)。

ARC006C - 積み重ね

arc006.contest.atcoder.jp

順番に入ってくるダンボールを床に置くか、より重いダンボールの上に置くかできる。床に直に置かれているダンボールの数を最小化する問題。

N <= 50なのでO(N²)で問題ない。とすると素直に実装できる：

n = int(input())
ws = [int(input()) for _ in range(n)]
 
xs = []
for w in ws:
    ys = [(x, i) for i, x in enumerate(xs) if x >= w]
    if ys:
        _, i = min(ys)
        xs[i] = w
    else:
        xs.append(w)
print(len(xs))

xsが各山の一番上に乗っているダンボールの重さ。入ってきたダンボールより重いものがあるか調べて、あるならその内の最小のものの上に置く（xsのその添字の値を書き換える）。「入ってきたダンボールより重い、最小のもの」が貪欲法要素。

ABC005C - おいしいたこ焼きの売り方

abc005.contest.atcoder.jp

たこ焼きが出来上がる時間と客が来る時間と、たこ焼きが出来上がってから買われるまでの許容される最長の時間が与えられ、すべての客にすぐにたこ焼きを提供できるか調べる問題。

現在たこ焼きをできた順に、できた時間でキューとして保持して、客が来た時点で許容される時間外のものはキューから削除。その上でキューが空でなければキューの頭にある「許容される上で最も古い」たこ焼きを提供する。（ここが貪欲法）

from collections import deque
 
t = int(input())
n = int(input())
takos = deque(int(x) for x in input().split())
m = int(input())
customers = [int(y) for y in input().split()]
 
q = deque()
for time in customers:
    while q and q[0] < time - t:
        q.popleft()
    while takos and takos[0] <= time:
        q.append(takos.popleft())
    if q:
        q.popleft()
    else:
        print('no')
        break
else:
    print('yes')

これはO(N+M)で計算量のオーダーは最善なはず。

ABC091C - 2D Plane 2N Points

abc091.contest.atcoder.jp

平面にN個ずつ赤い点と青い点がある。赤い点のx,y座標ともに青い点のものより小さい場合ペアにすることができるとして、作れるペアの最大数を求める問題。

x値が最小の青い点からはじめて順番に、ペアになり得る赤い点のうち最もy値が大きいものを選んでいく、という貪欲法：

from collections import defaultdict
 
n = int(input())
reds = [tuple(int(x) for x in input().split())for _ in range(n)]
blues = [tuple(int(x) for x in input().split())for _ in range(n)]
 
blue_dict = defaultdict(list)
for bx, by in blues:
    for rx, ry in reds:
        if rx < bx and ry < by:
            blue_dict[bx, by].append((rx, ry))

for val in blue_dict.values():
    val.sort(key=lambda x:-x[1])
 
red_dict = {}
for blue, red_list in sorted(blue_dict.items(), key=lambda x:x[0][0]):
    for red in red_list:
        if red in red_dict:
            continue
        red_dict[red] = blue
        break
 
print(len(red_dict))

うーん、これももうちょっと綺麗に書ける気がする。

計算量は

各青い点ごとにペアになり得るすべての赤い点のリスト化にO(N²)
各リストのソートにO(N log N)
青い点ごとにペアとなる赤い点をソートされたリストから探すのにO(N²)

なのでワーストケースでO(N²)。N<=100なので問題なし。

Fence Repair問題

貪欲法の章最後の例題であるFence RepairはAtCoderの類題が見つかっていない上に、以前書いた解法を改善する余地が思い浮かばないので飛ばす。

以前書いた記事：

zehnpaard.hatenablog.com

次はようやく動的計画法について。

Arantium Maestum

プログラミング、囲碁、読書の話題