greedyアルゴリズムについて
概要
- 現在が良ければ未来も良いはず、という一部のスケジューリング問題に基づく
- 短期的な最大となる行動を積み重ねると、最適値につくと期待できる場合に使えるアルゴリズム
- 制約; 途中から使用可能になったタスクは消化しない限り実行不能になることはない、という条件が必要
- 証明
- あるときに最良の選択をしなかった場合、後日、最良の選択をした場合と交換可能である
- あるときに最良の選択をしなかった場合、後日、最良の選択を選べないまま終える可能性がある(= より良い選択があるのに選べないで終わる)
覚えておくと便利
- /different_strokes/
- greedyで取るための指標を差分で求めて行う方法
例; 典型的な例(現在選べる最大の効用を選択)
問題
解答
N = int(input())
X = []
for i in range(N):
X.append([])
for i in range(N):
a, b = list(map(int, input().split()))
X[a - 1].append(b)
cnt = [0] * 101
ans = 0
for d in range(N):
# d日までのポイントの大きさをカウント
for b in X[d]:
cnt[b] += 1
# 最大のものを一つ選びデクリメント
for b in range(100, 0, -1):
if cnt[b] > 0:
ans += b
cnt[b] -= 1
break
print(ans)
例; 締切と所要時間があるときすべてのタスクを処理できるかどうか
問題
考え方
- 締切が近いものからやっていく
- 締切が近いものからやなかったときは破綻する条件がある = 締切が近いものから埋めれば良い
解答
N = int(input())
AB=[list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x:x[1])
acc = 0
for a, b in AB:
acc += a
if b < acc:
print("No")
exit()
print("Yes")
類題
例; 複数の大きさの異なる箱に、価値と大きさが異なる荷物を詰めるとき、どの入れ方ならば最適か
問題
AtCoder Beginner Contest 195; D - Shipping Center
考え方
- ２つ指標がある
- 価値が大きいものからその価値の荷物が入る最小の箱を探す
- 小さな箱から見ていき、その箱に入る最大の価値の荷物を入れる
解答
例; 積めるものから荷物を詰めていく
問題
解説
- 積める状態のものから何も気にせず積んでいく
解答
N = int(input())
G = []
for n in range(N):
w = int(input())
for g in G:
if g[-1] >= w:
g.append(w)
break
else:
G.append( [w] )
print(len(G))
例; 後ろから最適値を埋めていく
問題
解説
- 後ろから最適値を探すのが最善手
- 最適値の検索がheapを使わないと難しい点がポイント
解答
import heapq
import collections
N, M = map(int, input().split())
dg = collections.defaultdict(list)
for n in range(N):
day, gain = map(int, input().split())
dg[day].append(gain)
que = []
ans = 0
for m in range(1, M + 1): # 最後の日から見ていく
for gain in dg[m]:
heapq.heappush(que, -gain)
if que:
ans += -heapq.heappop(que)
print(ans)
例; 橋を最低何個壊せばすべての条件を満たすか
問題
解説
- 最も後ろの橋を壊したら最大限の条件を満たす
- 後ろからソートして、一番うしろの橋を壊していく
解答
N,M=map(int,input().split())
AB = []
for _ in range(M):
AB.append(list(map(int,input().split())))
AB.sort(key=lambda x:x[1])
tgt = -1
cnt = 0
for a, b in AB:
if not(a < tgt <= b):
tgt = b
cnt += 1
print(cnt)
例; 特殊な指標を定義する
例; 二次元の差分でペアを作るとき最大の数になるようにペアを作る
問題
解説
- (証明)ソートした上で、あるペアを
(r_a, b_b)と(r_b, b_a)というペアがあったとき、r_a < r_bならば交換可能であり、(r_a, b_a)と(r_b, b_b)とすることができるが、逆はできないことがある- 青い点より x, y 座標が小さく，まだ仲良しペアになっていない赤い点を探す
- なかったらなにもしない
- あったら，その中で最もy座標が大きいものを探し，仲良しペアにする
解答
N = int(input())
red = [list(map(int,input().split())) for _ in range(N)]
blue = [list(map(int,input().split())) for _ in range(N)]
"""考え方; (x,y)でソートしたblueで、redは条件を満たす中で最もyが大きいものを選ぶ"""
"""blueをソートする x, yの順"""
blue.sort()
"""redをソートする -y,xの順"""
red.sort(key=lambda x: (-x[1], x[0]))
matchs = set()
for bx, by in blue:
for ax, ay in red:
if ax < bx and ay < by:
if (ax, ay) in matchs:
continue
else:
matchs.add( (ax, ay) )
break
print(len(matchs))
例; カッコの対応が成立するかの判定
問題
解説
- ２つの組に分ける
- lが多い組 -> rの小さい順にソート
- rが多い組 -> lが大きい順にソート
解答
N = int(input())
L = []
R = []
for _ in range(N):
l, r = 0, 0
s = input()
for i in range(len(s)):
if s[i] == "(":
l += 1
else:
if l:
l -= 1
else:
r += 1
if l >= r:
L.append([l, r])
else:
R.append([l, r])
L.sort(key=lambda x: x[1]) # Rが小さい順で並べる
R.sort(key=lambda x: -x[0]) # Lが大きい順で並び替える
arr = L + R
cnt = 0
for l, r in arr:
if cnt < r:
print("No")
exit()
cnt += l - r # 残りl数
if cnt == 0:
print("Yes")
else:
print("No")
例; なるべく近い方を選ぶgreedy
問題
解答