AIで解説 AtCoder攻略　貪欲法

貪欲法ページの位置づけ

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

局所的な選択が全体の最適解につながる条件と、操作で変わらない量を見抜きます。選択の順番を証明できるかが判断軸です。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

最初の一問として、ABC204 B Nuts（公式解説）を解きます。各袋について10個を超えた分だけを合計します。袋ごとの計算が他の袋に影響しないため、局所的にその場で決められます。

N = int(input())
A = list(map(int, input().split()))
print(sum(max(value - 10, 0) for value in A))

袋を1回ずつ見るO(N)時間、O(1)追加メモリです。

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

問題	公式解説	出題意図	difficulty
ABC204 B Nuts	公式解説	Sum max(A_i−10,0) for every tree.	-1132
ABC432 A Permute to Maximize	公式解説	公式Editorialの方針を permute max greedy として整理する。	-999
ABC209 B Can you buy them all?	公式解説	Subtract the one-yen discount for each even-indexed item and compare the total with X.	-978
ABC243 A Shampoo	公式解説	残量からF、M、Tの順に消費し、周期後の残量で最後に消費できる人を判定する。	-841
ABC210 A Cabbages	公式解説	Charge the first min(N,A) cabbages at the regular price and the rest at the discounted price.	-813

問題	公式解説	出題意図	difficulty
ABC171 B Mix Juice	公式解説	ジュースをK本選ぶ費用を最小化するため、価格を昇順に並べて先頭K個を合計する。	-765
ABC213 B Booby Prize	公式解説	得点と番号の組を降順ソートし、2番目の要素の番号を出力する。	-692
ABC394 B cat	公式解説	Sort the input strings by length and concatenate them in ascending-length order.	-630
ABC461 B The Honest Woodcutters	公式解説	Sort woodcutters and choose a feasible order with greedy DP.	-581
ABC360 C Move It	公式解説	Official editorial intent is classified as group move cost.	-559

問題	公式解説	出題意図	difficulty
ABC356 B Nutrients	公式解説	Official editorial intent is classified as nutrient requirement.	-517
ABC432 B Permute to Minimize	公式解説	公式Editorialの方針を permute min greedy として整理する。	-449
ABC353 B AtCoder Amusement Park	公式解説	Official editorial intent is classified as amusement group packing.	-425
ABC354 B AtCoder Janken 2	公式解説	Official editorial intent is classified as janken sort.	-403
ABC368 B Decrease 2 max elements	公式解説	Official editorial intent is classified as decrease two max.	-384