DOKICODE
書斎

貪欲法

貪欲法は、各ステップでその場で一番よさそうな選択をし、後から取り消しません。大変なのは、その局所的な選択が本当に正しいと納得することです。だから貪欲法の問題は、コードは短いのに自信を持ちにくいのです。

8 つの章は、一般的な貪欲戦略、区間スケジューリング、文字列の貪欲法、数学の貪欲法、構築と発想問題、構築問題、インタラクティブ問題、その他の貪欲法の順です。中程度の配列問題は解けるようになって、なぜその貪欲な選択で正しいのかを見抜く力をつけたい人に向いています。

254 問レーティング 1148–30778 章
書斎を開く

誰かと一緒にこの問題集を進めたいなら、ログインして書斎を開いてみてください。ヒロインが一問ずつ出題してくれます。

一、Greedy Strategy

§1.1 最小 / 最大からGreedyに決める

問題レーティング
3074. Apple Redistribution Into Boxes1198
3545. Minimum Deletions for at Most K Distinct Characters1211
2279. Maximum Bags with Full Capacity of Rocks1249
1833. Maximum Ice Cream Bars1253
1005. Maximize Sum of Array After K Negations1275
1481. Least Number of Unique Integers After K Removals1284
1403. Minimum Subsequence in Non Increasing Order1288
3010. Divide an Array Into Subarrays with Minimum Cost I1292
1338. Reduce Array Size to the Half1303
1710. Maximum Units on a Truck1310
3075. Maximize Happiness of Selected Children1326
2554. Maximum Number of Integers to Choose From a Range I1333
2126. Destroying Asteroids1335
2587. Rearrange Array to Maximize Prefix Score1337
976. Largest Perimeter Triangle1341
1561. Maximum Number of Coins You Can Get1406
3627. Maximum Median Sum of Subsequences of Size 31561
3462. Maximum Sum with at Most K Elements1416
2099. Find Subsequence of Length K with the Largest Sum1447
3301. Maximize the Total Height of Unique Towers1448
945. Minimum Increment to Make Array Unique1448
1846. Maximum Element After Decreasing AND Rearranging1454
3727. Maximum Alternating Sum of Squares1455
1647. Minimum Deletions to Make Character Frequencies Unique1510
2971. Find Polygon with the Largest Perimeter1521
2178. Maximum Split of Positive Even Integers1538
1578. Minimum Time to Make Rope Colorful1574
2567. Minimum Score by Changing Two Elements1609
1509. Minimum Difference Between Largest AND Smallest Value in Three Moves1653
3397. Maximum Number of Distinct Elements After Operations1687
3457. Eat Pizzas1704
948. Bag of Tokens1762
1775. Equal Sum Arrays with Minimum Number of Operations1850
3440. Reschedule Meetings for Maximum Free Time II1998
2333. Minimum Sum of Squared Difference2011
3645. Maximum Total From Optimal Activation Order2019

§1.2 単一列のペアリング

問題レーティング
2144. Minimum Cost of Buying Candies with Discount1261
561. Array Partition1300
1877. Minimize Maximum Pair Sum in Array1301
881. Boats to Save People1530
2592. Maximize Greatness of an Array1569

§1.3 二つの列のペアリング

問題レーティング
2037. Minimum Number of Moves to Seat Everyone1357
455. Assign Cookies1381
2410. Maximum Matching of Players with Trainers1381
1433. Check If a String Can Break Another String1436
870. Advantage Shuffle1648
826. Most Profit Assigning Work1709
2449. Minimum Number of Operations to Make Arrays Similar2076
1889. Minimum Space Wasted From Packaging2214
2561. Rearranging Fruits2222

§1.4 左端 / 右端からGreedyに決める

問題レーティング
3402. Minimum Operations to Make Columns Strictly Increasing1246
3191. Minimum Operations to Make Binary Array Elements Equal to One I1312
1827. Minimum Operations to Make the Array Increasing1315
2027. Minimum Moves to Convert String1346
605. Can Place Flowers1400
3111. Minimum Rectangles to Cover Points1401
2957. Remove Adjacent Almost Equal Characters1430
3192. Minimum Operations to Make Binary Array Elements Equal to One II1433
1529. Minimum Suffix Flips未評価
2789. Largest Element in an Array After Merge Operations1485
3576. Transform Array to All Equal Elements1489
1144. Decrease Elements to Make Array Zigzag1559
3228. Maximum Number of Operations to Move Ones to the End1593
2086. Minimum Number of Food Buckets to Feed the Hamsters1623
1536. Minimum Swaps to Arrange a Binary Grid1881
2673. Make Costs of Paths Equal in a Binary Tree1917
861. Score After Flipping Matrix2000
955. Delete Columns to Make Sorted II2000
2366. Minimum Replacements to Sort the Array2060

§1.5 分割型のGreedy

問題レーティング
1221. Split a String in Balanced Strings1220
2405. Optimal Partition of String1355
2294. Partition Array Such That Maximum Difference Is K1416
2358. Maximum Number of Groups Entering a Competition1503
2522. Partition String Into Substrings with Values at Most K1605
3557. Find Maximum Number of Non Intersecting Substrings1720

§1.6 Brute-Force SearchしてからGreedy

問題レーティング
2171. Removing Minimum Number of Magic Beans1748
3085. Minimum Deletions to Make String K Special1765
1727. Largest Submatrix with Rearrangements1927
2910. Minimum Number of Groups to Create a Valid Assignment2132
2234. Maximum Total Beauty of the Gardens2562

§1.7 Exchange Argument

問題レーティング
2895. Minimum Processing Time1352
3457. Eat Pizzas1704
1665. Minimum Initial Energy to Finish Tasks1901
3273. Minimum Amount of Damage Dealt to Bob2013
2136. Earliest Possible Day of Full Bloom2033
2561. Rearranging Fruits2222

§1.8 隣接要素を異なるものにする

問題レーティング
2335. Minimum Amount of Time to Fill Cups1360
3659. Partition Array Into K Distinct Groups1440
1753. Maximum Score From Removing Stones1488
2856. Minimum Array Length After Pair Removals1750
1953. Maximum Number of Weeks for Which You Can Work1804
3664. Two Letter Card Game2158
3495. Minimum Operations to Make Array Elements Zero2206
3139. Minimum Cost to Equalize Array2666

二、区間のGreedy

§2.1 交わらない区間

問題レーティング
435. Non Overlapping Intervals1700
646. Maximum Length of Pair Chain未評価
1520. Maximum Number of Non Overlapping Substrings2363
3458. Select K Disjoint Special Substrings未評価

§2.3 区間に点を選ぶ

問題レーティング
452. Minimum Number of Arrows to Burst Balloons1700
757. Set Intersection Size at Least Two2379

§2.4 区間被覆

問題レーティング
45. Jump Game II1700
1024. Video Stitching1746
1326. Minimum Number of Taps to Open to Water a Garden1885

§2.5 区間のマージ

問題レーティング
56. Merge Intervals未評価
57. Insert Interval未評価
55. Jump Game未評価
763. Partition Labels1443
3169. Count Days Without Meetings1483
2580. Count Ways to Group Overlapping Ranges1632
3394. Check If Grid Can Be Cut Into Sections1916

§2.6 その他の区間Greedy

問題レーティング
1288. Remove Covered Intervals未評価

三、文字列のGreedy

§3.1 辞書順最小 / 最大

問題レーティング
1323. Maximum 69 Number1194
3216. Lexicographically Smallest String After a Swap1243
2697. Lexicographically Smallest Palindrome1304
3517. Smallest Palindromic Rearrangement I1357
1881. Maximum Value After Insertion1381
2734. Lexicographically Smallest String After Substring Operation1405
1432. Max Difference You Can Get From Changing an Integer1427
1946. Largest Number After Mutating Substring1445
1663. Smallest String with a Given Numeric Value1461
1328. Break a Palindrome1474
2259. Remove Digit From Number to Maximize Result未評価
2566. Maximum Difference by Remapping a Digit未評価
670. Maximum Swap未評価
3106. Lexicographically Smallest String After Operations with Constraint1515
3723. Maximize Sum of Squares of Digits1537
1053. Previous Permutation with One Swap1633
2375. Construct Smallest Number From Di String1642
2182. Construct String with Repeat Limit1680
738. Monotone Increasing Digits1700
3403. Find the Lexicographically Largest String From the Box I1762
1754. Largest Merge of Two Strings1829
2948. Make Lexicographically Smallest Array by Swapping Elements2047
3474. Lexicographically Smallest Generated String2605

§3.2 回文のGreedy

問題レーティング
409. Longest Palindrome1250
2697. Lexicographically Smallest Palindrome1304
3517. Smallest Palindromic Rearrangement I1357
680. Valid Palindrome II1400
1328. Break a Palindrome1474
1400. Construct K Palindrome Strings1530
2131. Longest Palindrome by Concatenating Two Letter Words1557
2384. Largest Palindromic Number1636
3035. Maximum Palindromes After Operations1857
1616. Split Two Strings to Make Palindrome1868
1147. Longest Chunked Palindrome Decomposition1912
3734. Lexicographically Smallest Palindromic Permutation Greater Than Target2330

四、数学的なGreedy

§4.1 基礎

問題レーティング
2160. Minimum Sum of Four Digit Number After Splitting Digits1314
2578. Split with Minimum Sum1351
2244. Minimum Rounds to Complete All Tasks1372
2870. Minimum Number of Operations to Make Array Empty1392
1217. Minimum Cost to Move Chips to the Same Position1408

§4.2 積のGreedy

問題レーティング
628. Maximum Product of Three Numbers未評価
3732. Maximum Product of Three Elements After One Replacement1529

§4.3 並べ替え不等式

問題レーティング
2285. Maximum Total Importance of Roads1496
3016. Minimum Number of Pushes to Type Word II1534
1402. Reducing Dishes1679

§4.4 相加相乗平均の不等式

問題レーティング
1969. Minimum Non Zero Product of the Array Elements1967
3723. Maximize Sum of Squares of Digits1537

§4.5 中央値のGreedy

問題レーティング
462. Minimum Moves to Equal Array Elements II未評価
2033. Minimum Operations to Make a Uni Value Grid1672
2448. Minimum Cost to Make Array Equal2005

§4.6 帰納法

問題レーティング
2952. Minimum Number of Coins to Be Added1784
330. Patching Array未評価
1798. Maximum Number of Consecutive Values You Can Make1931

§4.7 その他の数学的なGreedy

問題レーティング
3107. Minimum Operations to Make Median of Array Equal to K1605
754. Reach a Number2000

五、思考問題

§5.1 特殊なケースから一般化する

問題レーティング
2745. Construct the Longest New String1607
2611. Mice AND Cheese1663
1029. Two City Scheduling未評価
2645. Minimum Additions to Make Valid String未評価
2202. Maximize the Topmost Element After K Moves1717
1702. Maximum Binary String After Change1825
2350. Shortest Impossible Sequence of Rolls1961
3660. Jump Game IX2187
517. Super Washing Machines未評価
2499. Minimum Total Cost to Make Arrays Unequal2633
3357. Minimize the Maximum Adjacent Element Difference3077

§5.2 ひらめき問題

問題レーティング
2733. Neither Minimum Nor Maximum1148
3432. Count Partitions with Even Sum Difference1200
1903. Largest Odd Number in String1249
2549. Count Distinct Numbers on Board1266
1689. Partitioning Into Minimum Number of Deci Binary Numbers1355
3674. Minimum Operations to Equalize Array1369
3689. Maximum Total Subarray Value I1371
598. Range Addition II1400
521. Longest Uncommon Subsequence I1400
3675. Minimum Operations to Transform String1414
3638. Maximum Balanced Shipments1463
3702. Longest Subsequence with Non Zero Bitwise XOR1489
3424. Minimum Cost to Make Arrays Identical1503
1992. Find All Groups of Farmland1539
1007. Minimum Domino Rotations for Equal Row1541
2811. Check If It Is Possible to Split Array1543
463. Island Perimeter未評価
2211. Count Collisions on a Road1581
3207. Maximum Points After Enemy Battles1591
3471. Find the Largest Almost Missing Integer未評価
1503. Last Moment Before All Ants Fall Out of a Plank1619
2860. Happy Students1626
1332. Remove Palindromic Subsequences1629
1975. Maximum Matrix Sum1648
1145. Binary Tree Coloring Game1741
1297. Maximum Number of Occurrences of a Substring1748
3577. Count the Number of Computer Unlocking Permutations1750
3282. Reach End of Array with Max Score1772
2712. Minimum Cost to Make All Characters Equal1791
2311. Longest Binary Subsequence Less Than OR Equal to K1840
2332. The Latest Time to Catch a Bus1841
2731. Movement of Robots1923
2556. Disconnect Path in a Binary Matrix by at Most One Flip2369

§5.3 逆から考える

問題レーティング
2139. Minimum Moves to Reach Target Score1417
869. Reordered Power of 21505
554. Brick Wall1700
780. Reaching Points1897
417. Pacific Atlantic Water Flow1900
2227. Encrypt AND Decrypt Strings1945
3614. Process String with Special Operations II未評価
3609. Minimum Moves to Reach Target in Grid2419
936. Stamping the Sequence2583

§5.4 同値な問題への言い換え

問題レーティング
453. Minimum Moves to Equal Array Elements未評価
3375. Minimum Operations to Make Array Values Equal to K1383
2914. Minimum Number of Changes to Make Binary String Beautiful1480
3365. Rearrange K Substrings to Form Target String1514
1657. Determine If Two Strings Are Close1530
2551. Put Marbles in Bags2042
1585. Check If String Is Transformable with Substring Sort Operations2333
1040. Moving Stones Until Consecutive II2456
49. Group Anagrams未評価

六、構築問題

§6.1 構築問題

問題レーティング
1304. Find N Unique Integers Sum Up to Zero1167
942. Di String Match1444
1253. Reconstruct a 2 Row Binary Matrix1506
3513. Number of Unique XOR Triplets I1663
2182. Construct String with Repeat Limit1680
969. Pancake Sorting未評価
1605. Find Valid Matrix Given Row AND Column Sums1868
2375. Construct Smallest Number From Di String未評価
324. Wiggle Sort II未評価
667. Beautiful Arrangement II未評価
2122. Recover the Original Array2159
932. Beautiful Array未評価
3311. Construct 2D Grid Matching Graph Layout2664
2573. Find the String with LCP2682
1982. Find Array Given Subset Sums2872
1980. Find Unique Binary String未評価

七、インタラクティブ問題

七、インタラクティブ問題

問題レーティング
1237. Find Positive Integer Solution for a Given Equation未評価
843. Guess the Word2078

八、その他

八、その他

問題レーティング
2740. Find the Value of the Partition1302
1033. Moving Stones Until Consecutive1421
3523. Make Array Non Decreasing1435
781. Rabbits in Forest1453
3587. Minimum Adjacent Swaps to Alternate Parity1548
1864. Minimum Number of Swaps to Make the Binary String Alternating1601
1899. Merge Triplets to Form Target Triplet1636
2498. Frog Jump II1759
3724. Minimum Operations to Transform Array1790
134. Gas Station未評価
3635. Earliest Finish Time for Land AND Water Rides II1870
3002. Maximum Size of a Set After Removals1917
1733. Minimum Number of People to Teach1984
659. Split Array Into Consecutive Subsequences未評価
2790. Maximum Number of Groups with Increasing Length2620
782. Transform to Chessboard未評価

ルートでは「ビット演算」と「数学」の間に置かれています。すでに練習した章やセクションは、個別にチェックして飛ばせます。

レーティングは zerotrac さんによる LeetCode コンテストレーティングです。zerotrac のレーティングがない問題は「未評価」と表示されます。

書斎を開く