Pythonで解く蟻本（2-2: 猪突猛進！ "貪欲法"）
※自分の勉強の備忘録として書くので、ちゃんとした説明はない記事です。
記事の構成としては、ざっくりとこんな感じです。
- 蟻本の答案をPython3に変換したもの
- AtCoderの例題のPython3解答
蟻本と似たような問題は、Qiitaの記事（AtCoder 版！蟻本 (初級編) - Qiita）を参考に探しました。
AtCoderの解答解説を読んでもコーディングで躓く、他の人のACコードを見ても何が起きてるか分からない、という方の助けになれば幸いです。
この記事では、貪欲法の話しか出てこないです。
なお、持っている蟻本は以下の第2版です。
リンク
- 硬貨の問題（蟻本 P.42）
- 区間スケジューリング問題（蟻本 P.43）
- Best Cow（蟻本 P.45）
- Saruman's Army (POJ No.3069)
- Fence Repair (POJ No.3253)
- まとめ
硬貨の問題（蟻本 P.42）
2-1までの深さ優先探索や幅優先探索のコードと比較するとかなりシンプルですね。
（実際の問題だと、そもそも法則を見つけにくかったりするんだろうな...）
できるだけ高い金額のコインから消費していきます。
V = [1, 5, 10, 50, 100, 500] C = list(map(int, input().split())) A = int(input()) ans = 0 for i in reversed(range(6)): t = min(A // V[i], C[i]) A -= t * V[i] ans += t print(ans)
JOI 2007 予選 A おつり
これは上記の問題とほぼ同じ感じで解けますね。
できるだけ高い金額のコインから消費するものの、コインの上限がなくなったパターンです。
values = [1, 5, 10, 50, 100, 500] buy = int(input()) ans = 0 rest = 1000 - buy for i in reversed(range(6)): coin = rest // values[i] ans += coin rest -= coin * values[i] print(ans)
AOJ Course コイン問題
一瞬同じ問題に見えつつも、先ほどまでと同様にやっていてはいきなり躓くことがサンプルケースの時点で分かります。
コインの金額の差が不揃いなのが原因のようですね。
nが5,000以下なので、二重ループでも2.5e+7の計算量となるので間に合うため、全探索します。
INF = 10**8 n, m = map(int, input().split()) c = list(map(int, input().split())) d = [INF] * (n + 1) d[0] = 0 for coin in c: for price in range(coin, n + 1): d[price] = min(d[price], d[price - coin] + 1) print(d[n])
区間スケジューリング問題（蟻本 P.43）
これは、コーディング自体は全く難しくないですね。
終端に注目する、という所に気付けずにハマってしまうと辛そうな雰囲気の問題です。
N = int(input()) S = list(map(int, input().split())) T = list(map(int, input().split())) itv = [[0] * 2 for _ in range(N)] for i in range(N): itv[i][0] = T[i] itv[i][1] = S[i] itv.sort() ans = 0 t = 0 for i in range(N): if(t < itv[i][1]): ans += 1 t = itv[i][0] print(ans)
キーエンス プログラミング コンテスト 2020 B - Robot Arms
これも、上記とほぼ同じ形で解けるので簡単ですね。
ロボットアームの右側に着目します。
と言いつつ、この流れで解いてるから簡単なだけで実際には結構悩む気がしました。
こういう問題の解き方にパッと気付けるようになりたい。
n = int(input()) position = [] for i in range(n): x_in, l_in = map(int, input().split()) position.append([x_in + l_in, x_in - l_in]) position.sort() ans = 0 t = - (10 ** 9 + 1) for i in range(n): if t <= position[i][1]: ans += 1 t = position[i][0] print(ans)
ABC 103 D - Islands War
これも同じように実装すればいけますね。
島の番号が大きい方から橋を分断していきます。
n, m = map(int, input().split()) ba = [] for i in range(m): ba.append(list(map(int, input().split()))) ba[i][0], ba[i][1] = ba[i][1] - 1, ba[i][0] - 1 ba.sort() bridge = [ba[0][0] - 1] for i in range(1, m): if ba[i][1] > bridge[-1]: bridge.append(ba[i][0] - 1) print(len(bridge))
Codeforces 296 DIV1 B Clique Problem
ちょっと問題の意味が分からず、、断念しました。
ABC 038 D プレゼント
これは難しかったので解答を見てしまいました。
なるほど。片方を昇順に並べてもう片方を降順に並べる...！
思いつかなかった...！
bisect関数を二次元リストに使ってるのも個人的にはなるほどという感じでした。
from bisect import bisect_left from operator import itemgetter n = int(input()) box = [list(map(int, input().split())) for i in range(n)] # h_i は昇順にした上で、h_i が等しい場合 w_i は降順にソートする box = sorted(box, key=itemgetter(0), reverse=True) # w_i box = sorted(box, key=itemgetter(1)) # h_i dp = [float("inf")] * n for i in range(n): dp[bisect_left(dp, box[i][0])] = box[i][0] print(bisect_left(dp, float("inf")))
Best Cow（蟻本 P.45）
C++ の for文と Python の for文 の仕様が違うのでwhile文で実装します。
n = int(input()) s = input() t = "" a, b = 0, n - 1 while a <= b: left = False i = 0 while a + i <= b: if s[a + i] < s[b-i]: left = True break elif s[a + i] > s[b - i]: left = False break i += 1 if left: t += s[a] a += 1 else: t += s[b] b -= 1 print(t)
ABC 076 C Dubious Document 2
これは、以下のような考えでコードを書いてみました。
- Sの中にTが含まれている場合は、?を全部aに変換する
- 含まれていない場合は、Sの後ろの文字からT文字数文抜き出してTと比較
- Tが見つかったら、SにTを埋め込んだあとに残った?を全部aに変換する
?をaに変換するときは、replace関数を使った方が良いことにはてな投稿時に気付きましたが気にしないことにします。
S = list(input()) T = list(input()) flag = False for i in reversed(range(len(S) - len(T) + 1)): T_flg = S[i: i + len(T)] for j in range(len(T)): if T_flg[j] != T[j] and T_flg[j] != "?": break else: flag = True S[i:i + len(T)] = T break if flag == False: print("UNRESTORABLE") else: for i in range(len(S)): if S[i] == "?": S[i] = "a" print("".join(map(str,S)))
ABC 007 B 辞書式順序
これはめちゃくちゃ簡単ですね...！
A = input() if A == "a": print(-1) else: print("a")
ABC 009 C 辞書式順序ふたたび
これは難しかったので、解説と他の人のAC解答をみました。
抽象的には理解したものの、辞書型変数同士の減算やCounter関数がちょっと独特でまだ頭の中でイメージしにくいのでこれは修行が必要な予感がします。
from collections import Counter n, k = map(int, input().split()) s = list(input()) s_sort = sorted(s) t = "" # 元の位置と違う文字の数 diff = 0 # 見終わったけどまだ使ってない文字 counter = Counter(s[:1]) counts = sum(counter.values()) # 1文字目から順に見ていく for i in range(n): # t + c が可能か調べる for c in s_sort: # t + c の中で元の位置と違う文字の数 if c != s[i]: diff1 = diff + 1 else: diff1 = diff # まだ使ってない文字の中で元の位置と違う文字の数 if counter[c] > 0: diff2 = counts - 1 else: diff2 = counts # 両方を足して k 以下ならば t + c が可能 if diff1 + diff2 <= k: t += c s_sort.remove(c) diff = diff1 counter = Counter(s[:i + 2]) - Counter(t) counts = sum(counter.values()) break print(t)
Saruman's Army (POJ No.3069)
これは結構直感的に解けますね。
n = int(input()) r = int(input()) x = list(map(int, input().split())) x.sort() i = 0 ans = 0 while i < n: s = x[i] i += 1 while i < n and x[i] <= s + r: i += 1 p = x[i - 1] while i < n and x[i] <= p + r: i += 1 ans += 1 print(ans)
ABC 083 C Multiple Gift
数列Aが最大となるためには、常に2倍ずつ大きくするのが最良なので以下のコードになります。
x, y = map(int, input().split()) ans = 0 while x <= y: x *= 2 ans += 1 print(ans)
ARC 006 C 積み重ね
床に積まれた段ボールの山の中に、新しくトラックから運んできた段ボールが積める山がある場合は絶対に積む、というロジックで解決できます。
n = int(input()) w = [int(input()) for _ in range(n)] floor = [w[0]] for i in range(1, n): for j in range(len(floor)): if floor[j] >= w[i]: floor[j] = w[i] break else: floor.append(w[i]) print(len(floor))
ABC 005 C おいしいたこ焼きの売り方
たこ焼きを古い順に確認して、お客さんが来る時間 - t 以降に作られたたこ焼きが今あるかどうか確認していきます。
t = int(input()) n = int(input()) a = list(map(int, input().split())) m = int(input()) b = list(map(int, input().split())) flag = True if n < m: print("no") exit() j = 0 ans = 0 for i in range(m): while j < n: if b[i] - t <= a[j] <= b[i]: j += 1 ans += 1 break else: j += 1 if ans == m: print("yes") else: print("no")
SRM 560 DIV1 Easy TomekPhone
TopCoder Statistics - Problem Statement
自分自身の理解が浅いからなのか、TopCoderの問題文に辿り着けずどんな問題か分かりませんでした...！
ABC 091 C 2D Plane 2N Points
これは最初、マッチする点が少ない物同士をペアにしていけば良いかと思ったのですが、そうではなかったです。
解説をみたら納得したのですが、もっとシンプルに、青い点をx座標が小さい順に見ていって、赤い点をy座標が大きい順にペアにしていけば良かったようです。
うーん、やっぱり貪欲法はパッと考えると難しいですね。
from operator import itemgetter n = int(input()) ab = [list(map(int, input().split())) for _ in range(n)] cd = [list(map(int, input().split())) for _ in range(n)] ans = 0 dp_ab = [False] * n dp_cd = [False] * n ab.sort(key = itemgetter(1), reverse = True) cd.sort() for i in range(n): for j in range(n): if cd[i][0] > ab[j][0] and cd[i][1] > ab[j][1] and dp_cd[i] == False and dp_ab[j] == False: dp_cd[i] = True dp_ab[j] = True ans += 1 print(ans)
Fence Repair (POJ No.3253)
だいぶ表現の仕方は違いますが、Pythonだったらこんな感じでよりすっきり書ける気がしています。
import bisect N = int(input()) L = list(map(int, input().split())) L.sort() ans = 0 while N > 1: mii1 = 0 mii2 = 1 t = L[mii1] + L[mii2] ans += t L.pop(mii2) L.pop(mii1) idx = bisect.bisect_left(L, t) L.insert(idx, t) N -= 1 print(ans)
Codeforces 263 DIV2 C Appleman and Toastman
applemanが、常に一番小さい数字とそれ以外のペアに分割していくのが最適解となります。
そうすると、一番小さい数字は2回, 二番目に小さい数字は3回, ... n-1番に小さい数字はn回で、n番目に小さい（つまり一番大きい）数字もn回の足し算となります。
なので、以下のコードとなりますね。
n = int(input()) a = list(map(int, input().split())) a.sort() score = sum(a) + a[n - 1] * (n - 1) for i in range(1, n): score += a[i - 1] * i print(score)
まとめ
うーん、貪欲法のまとめはなんていうか、最適なパターンを思いついたら、とりあえず考えてみて実装してみる！ということでしょうか...？
