DOKICODE
書斎

データ構造

この問題集で鍛えるのは、問題に合った入れ物を選ぶ力です。累積和といもす法はループを回さずに区間の問いに答え、ヒープは最小の要素をいつでも取り出せるようにし、Union-Find はどの要素が同じグループかを管理します。

13 の章は、よく使う全探索のテクニックから始まり、累積和、いもす法、スタック、キューと両端キュー、ヒープ、トライ木、Union-Find、BIT とセグメント木と続き、最後はスプレー木、平方分割（Mo's）、オフラインアルゴリズム、その他の高度なデータ構造で終わります。トラック 1 で最も大きな問題集なので、一章ずつ進めるのがおすすめです。

366 問レーティング 1161–311213 章
書斎を開く

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

零、よく使うBrute-Force Searchテクニック

§0.1 右端をBrute-Force Searchし、左側を管理する

問題レーティング
1. Two Sum1161
1512. Number of Good Pairs1161
2441. Largest Positive Integer That Exists with Its Negative1168
2016. Maximum Difference Between Increasing Elements1246
624. Maximum Distance in Arrays1246
2342. Max Sum of a Pair with Equal Sum of Digits1309
1128. Number of Equivalent Domino Pairs Description1333
1679. Max Number of K Sum Pairs1346
219. Contains Duplicate II1365
2260. Minimum Consecutive Cards to Pick Up1365
2001. Number of Pairs of Interchangeable Rectangles1436
2815. Max Pair Sum in an Array1436
3623. Count Number of Trapezoids I1580
2364. Count Number of Bad Pairs1622
3371. Identify the Largest Outlier in an Array1644
3761. Minimum Absolute Distance Between Mirror Pairs1669
1014. Best Sightseeing Pair1730
1814. Count Nice Pairs in an Array1738
3584. Maximum Product of First AND Last Elements of a Subsequence1763
2905. Find Indices with Index AND Value Difference II1764

§0.1.2 発展

問題レーティング
1010. Pairs of Songs with Total Durations Divisible by 601787
3185. Count Pairs That Form a Complete Day II1787
2748. Number of Beautiful Pairs1787
2506. Count Pairs of Similar Strings1787
1497. Check If Array Pairs Are Divisible by K1787
2555. Maximize Win From Two Segments2081
3267. Count Almost Equal Pairs II2545
3480. Maximize Subarrays After Removing One Conflicting Pair2764

§0.2 中央をBrute-Force Searchする

問題レーティング
3128. Right Triangles1541
447. Number of Boomerangs1583
456. 132 Pattern1583
3067. Count Pairs of Connectable Servers in a Weighted Tree Network1909
1534. Count Good Triplets1909
3455. Shortest Matching Substring2303
2867. Count Valid Paths in a Tree2428

§0.3 対角線の走査

問題レーティング
3446. Sort Matrix by Diagonals1373
1329. Sort the Matrix Diagonally1548
498. Diagonal Traverse1548

一、Prefix Sum

§1.1 基礎

問題レーティング
303. Range Sum Query Immutable1209
3427. Sum of Variable Length Subarrays1209
2559. Count Vowel Strings in Ranges1435
3152. Special Array II1523
3652. Best Time to Buy AND Sell Stock Using Strategy1557
3361. Shift Distance Between Two Strings1557

§1.2 Prefix SumとHash Table

問題レーティング
560. Subarray Sum Equals K1592
930. Binary Subarrays with Sum1592
1524. Number of Sub Arrays with Odd Sum1611
974. Subarray Sums Divisible by K1676
523. Continuous Subarray Sum1676
525. Contiguous Array1697
3755. Find Maximum Balanced XOR Subarray Length1697
3026. Maximum Good Subarray Sum1817
1546. Maximum Number of Non Overlapping Subarrays with Sum Equals Target1855
1124. Longest Well Performing Interval1908
3728. Stable Subarrays with Equal Boundary AND Interior Sum1909
2488. Count Subarrays with Median K1999
1590. Make Sum Divisible by P2039
2845. Count of Interesting Subarrays2073
3739. Count Subarrays with Majority Element II2090
1074. Number of Submatrices That Sum to Target2189
3714. Longest Balanced Substring II2202
2025. Maximum Number of Ways to Partition an Array2218
3729. Count Distinct Subarrays Divisible by K in Sorted Array2248
2949. Count Beautiful Substrings II2445

§1.3 距離の総和

問題レーティング
1685. Sum of Absolute Differences in a Sorted Array1496
2615. Sum of Distances1793
2602. Minimum Operations to Make All Array Elements Equal1903
2968. Apply Operations to Maximize Frequency Score2444
1703. Minimum Adjacent Swaps for K Consecutive Ones2467
3086. Minimum Moves to Pick K Ones2673

§1.4 BitmaskのPrefix Sum

問題レーティング
1177. Can Make Palindrome From Substring1848
1371. Find the Longest Substring Containing Vowels in Even Counts2041
1542. Find Longest Awesome Substring2222
1915. Number of Wonderful Substrings2235
2791. Count Paths That Can Form a Palindrome in a Tree2677

§1.5 発展

問題レーティング
3709. Design Exam Scores Tracker1648
1895. Largest Magic Square1781
2055. Plates Between Candles1819
1744. Can You Eat Your Favorite Candy on Your Favorite Day1859
1878. Get Biggest Three Rhombus Sums in a Grid1898
3756. Concatenate Non Zero Digits AND Multiply by Sum II1968
2245. Maximum Trailing Zeros in a Cornered Path2037
1712. Ways to Split Array Into Three Subarrays2079
1862. Sum of Floored Pairs2170
3748. Count Stable Subarrays2209
2281. Sum of Total Strength of Wizards2621
3445. Maximum Difference Between Even AND Odd Frequency II2694
2983. Palindrome Rearrangement Queries2780

§1.6 2D Prefix Sum

問題レーティング
304. Range Sum Query 2D Immutable1484
1314. Matrix Block Sum1484
3070. Count Submatrices with Top Left Element AND Sum Less Than K1499
1738. Find Kth Largest XOR Coordinate Value1671
3212. Count Submatrices with Equal Frequency of X AND Y1673
1292. Maximum Side Length of a Square with Sum Less Than OR Equal to Threshold1735

二、Difference Array (Imos)

§2.1 1D Difference Array

問題レーティング
2848. Points That Intersect with Cars1230
1893. Check If All the Integers in a Range Are Covered1307
1854. Maximum Population Year1370
2960. Count Tested Devices After Test Operations1370
1094. Car Pooling1441
1109. Corporate Flight Bookings1570
3355. Zero Array Transformation I1591
2381. Shifting Letters II1793
995. Minimum Number of K Consecutive Bit Flips1835
1589. Maximum Sum Obtained of Any Permutation1871
1526. Minimum Number of Increments on Subarrays to Form a Target Array1872
3356. Zero Array Transformation II1913
1943. Describe the Painting1969
3224. Minimum Array Changes to Make Differences Equal1996
2251. Number of Flowers in Full Bloom2022
2772. Apply Operations to Make All Array Elements Equal to Zero2029
3229. Minimum Operations to Make Array Equal to Target2067
3529. Count Cells in Overlapping Horizontal AND Vertical Substrings2105
798. Smallest Rotation with Highest Score2130
3347. Maximum Frequency of an Element After Performing Operations II2156
1674. Minimum Moves to Make Array Complementary2333
3362. Zero Array Transformation III2424
3655. XOR After Range Multiplication Queries II2454
3017. Count the Number of Houses at a Certain Distance II2709

§2.2 2D Difference Array

問題レーティング
2536. Increment Submatrices by One1583
850. Rectangle Area II2236
2132. Stamping the Grid2364

三、Stack

§3.1 基礎

問題レーティング
1441. Build an Array with Stack Operations1180
844. Backspace String Compare1228
682. Baseball Game1228
2390. Removing Stars From a String1348
1472. Design Browser History1454
946. Validate Stack Sequences1462
3412. Find Mirror Score of a String1578
71. Simplify Path1578

§3.2 発展

問題レーティング
3170. Lexicographically Minimum String After Removing Stars1772
155. Min Stack1772
1381. Design a Stack with Increment Operation1772
636. Exclusive Time of Functions1772
2434. Using a Robot to Print the Lexicographically Smallest String1953
895. Maximum Frequency Stack2028
1172. Dinner Plate Stacks2110
2589. Minimum Time to Complete All Tasks2381

§3.3 隣接要素の消去

問題レーティング
2696. Minimum String Length After Removing Substrings1282
1047. Remove All Adjacent Duplicates in String1286
1544. Make the String Great1344
3561. Resulting String After Adjacent Removals1397
1003. Check If Word Is Valid After Substitutions1427
2216. Minimum Deletions to Make Array Beautiful1510
1209. Remove All Adjacent Duplicates in String II1542
3703. Remove K Balanced Substrings1802
1717. Maximum Score From Removing Substrings1868
2197. Replace Non Coprime Numbers in Array2057
735. Asteroid Collision2057
2751. Robot Collisions2092

§3.4 正しい括弧列（RBS）

問題レーティング
20. Valid Parentheses1242
921. Minimum Add to Make Parentheses Valid1242
1021. Remove Outermost Parentheses1311
1614. Maximum Nesting Depth of the Parentheses1323
1190. Reverse Substrings Between Each Pair of Parentheses1486
856. Score of Parentheses1563
1249. Minimum Remove to Make Valid Parentheses1657
1963. Minimum Number of Swaps to Make the String Balanced1689
678. Valid Parenthesis String1700
1111. Maximum Nesting Depth of Two Valid Parentheses Strings1749
1541. Minimum Insertions to Balance a Parentheses String1759
2116. Check If a Parentheses String Can Be Valid2038

§3.5 式の構文解析

問題レーティング
1006. Clumsy Factorial1408
150. Evaluate Reverse Polish Notation1408
394. Decode String1408
8. String to Integer Atoi1408
224. Basic Calculator1408
227. Basic Calculator II1408
726. Number of Atoms1408
1106. Parsing a Boolean Expression1880
591. Tag Validator1880
736. Parse Lisp Expression1880
1096. Brace Expansion II2349
65. Valid Number2532
770. Basic Calculator IV2863

§3.6 二つのStackを向かい合わせる

問題レーティング
2296. Design a Text Editor1912

四、Queue

§4.1 基礎

問題レーティング
933. Number of Recent Calls1338
950. Reveal Cards in Increasing Order1686
649. Dota2 Senate1686

§4.2 設計

問題レーティング
1670. Design Front Middle Back Queue1610
225. Implement Stack Using Queues1851
232. Implement Queue Using Stacks1851
622. Design Circular Queue1851
641. Design Circular Deque1851

§4.3 Deque

問題レーティング
2810. Faulty Keyboard1851

§4.4 Monotonic Queue

問題レーティング
239. Sliding Window Maximum1851
1438. Longest Continuous Subarray with Absolute Diff Less Than OR Equal to Limit1672
2762. Continuous Subarrays1672
2398. Maximum Number of Robots Within Budget1917
3589. Count Prime Gap Balanced Subarrays2235
862. Shortest Subarray with Sum at Least K2307
1499. Max Value of Equation2456

五、Heap（Priority Queue）

§5.1 基礎

問題レーティング
1046. Last Stone Weight1173
3264. Final Array State After K Multiplication Operations I1178
2558. Take Gifts From the Richest Pile1277
2336. Smallest Number in Infinite Set1375
2530. Maximal Score After Applying K Operations1386
3066. Minimum Operations to Exceed Threshold Value II1400
1962. Remove Stones to Minimize the Total1419
703. Kth Largest Element in a Stream1419
3275. K Th Nearest Obstacle Queries1420
1845. Seat Reservation Manager1429
2208. Minimum Operations to Halve Array Sum1550
2233. Maximum Product After K Increments1686
1942. The Number of the Smallest Unoccupied Chair1695
1801. Number of Orders in the Backlog1711
2406. Divide Intervals Into Minimum Number of Groups1713
3478. Choose K Elements with Maximum Sum1753
2462. Total Cost to Hire K Workers1764
1834. Single Threaded Cpu1798
1792. Maximum Average Pass Ratio1818

§5.2 発展

問題レーティング
23. Merge K Sorted Lists1818
2931. Maximum Spending After Buying Items1822
355. Design Twitter1822
502. Ipo1822
1705. Maximum Number of Eaten Apples1930
1882. Process Tasks Using Servers1979
1354. Construct Target Array with Multiple Sums2015
1353. Maximum Number of Events That Can Be Attended2016
632. Smallest Range Covering Elements From K Lists2023
2542. Maximum Subsequence Score2056
1383. Maximum Performance of a Team2091
2402. Meeting Rooms III2093
2503. Maximum Number of Points From Grid Queries2196
857. Minimum Cost to Hire K Workers2260
1606. Find Servers That Handled Most Number of Requests2276
1851. Minimum Interval to Include Each Query2286
407. Trapping Rain Water II2286
2940. Find Building Where Alice AND Bob Can Meet2327
2589. Minimum Time to Complete All Tasks2381
3266. Final Array State After K Multiplication Operations II2509
1675. Minimize Deviation in Array2533
2532. Time to Cross a Bridge2589

§5.3 K 番目に小さい / 大きい値

問題レーティング
264. Ugly Number II1818
23. Merge K Sorted Lists1818

§5.4 要素の並べ替え

問題レーティング
984. String Without Aaa OR Bbb1474
767. Reorganize String1681
1054. Distant Barcodes1702
1405. Longest Happy String1821
3081. Replace Question Marks in String to Minimize Its Value1905
621. Task Scheduler1905

§5.5 後から取り消すHeap

問題レーティング
630. Course Schedule III2074
3362. Zero Array Transformation III2424
2813. Maximum Elegance of a K Length Subsequence2582
3049. Earliest Second to Mark Indices II3111

§5.6 Lazy Deletion Heap

問題レーティング
2349. Design a Number Container System1540
3607. Power Grid Maintenance1700
2353. Design a Food Rating System1782
3092. Most Frequent Ids1793
3408. Design Task Manager1807
2034. Stock Price Fluctuation1832
1172. Dinner Plate Stacks2110
218. The Skyline Problem2110
3510. Minimum Pair Removal to Sort Array II2608

§5.7 二つのHeap（Sliding Windowの K 番目）

問題レーティング
2102. Sequentially Ordinal Rank Tracker2159
295. Find Median From Data Stream2159
480. Sliding Window Median2159
2653. Sliding Subarray Beauty2159
1825. Finding Mk Average2396
3013. Divide an Array Into Subarrays with Minimum Cost II2540
3321. Find X Sum of All K Long Subarrays II2598

六、Trie

§6.1 基礎

問題レーティング
208. Implement Trie Prefix Tree1180
3597. Partition String1180
648. Replace Words1180
720. Longest Word in Dictionary1180
2416. Sum of Prefix Scores of Strings1725
677. Map Sum Pairs1725
1268. Search Suggestions System1725
1233. Remove Sub Folders From the Filesystem1725
820. Short Encoding of Words1725
2261. K Divisible Elements Subarrays1725

§6.2 発展

問題レーティング
211. Design Add AND Search Words Data Structure1725
676. Implement Magic Dictionary1725
212. Word Search II1725
3093. Longest Common Suffix Queries2118
745. Prefix AND Suffix Search2118
3045. Count Prefix AND Suffix Pairs II2328
336. Palindrome Pairs2328
1948. Delete Duplicate Folders in System2534

§6.3 Trieで高速化する DP

問題レーティング
140. Word Break II1725

§6.4 0-1 Trie (XOR Trie)

問題レーティング
1707. Maximum XOR with an Element From Array2359
1938. Maximum Genetic Difference Query2503

七、Union-Find

§7.1 基礎

問題レーティング
3493. Properties Graph1565
990. Satisfiability of Equality Equations1638
3532. Path Existence Queries in a Graph I1725

§7.2 発展

問題レーティング
3551. Minimum Swaps to Sort by Digit Sum1507
2471. Minimum Number of Operations to Sort a Binary Tree by Level1635
1202. Smallest String with Swaps1855
1061. Lexicographically Smallest Equivalent String1855
1722. Minimize Hamming Distance After Swap Operations1892
3608. Minimum Time for K Connected Components1893
765. Couples Holding Hands1999
947. Most Stones Removed with Same Row OR Column2035
839. Similar String Groups2054
1970. Last Day Where You Can Still Cross2124
2076. Process Restricted Friend Requests2131
959. Regions Cut by Slashes2136
2503. Maximum Number of Points From Grid Queries2196
2867. Count Valid Paths in a Tree2428
2421. Number of Good Paths2445
2157. Groups of Strings2499
1632. Rank Transform of a Matrix2530
803. Bricks Falling When Hit2765
3235. Check If the Rectangle Corner Is Reachable2765

§7.3 GCD と Union-Find

問題レーティング
2709. Greatest Common Divisor Traversal2172
1627. Graph Connectivity with Threshold2221
952. Largest Component Size by Common Factor2272
1998. Gcd Sort of an Array2429
3378. Count Connected Components in Lcm Graph2532

§7.4 array上の Union-Find

問題レーティング
1562. Find Latest Group of Size M1928
1488. Avoid Flood in the City1974
1353. Maximum Number of Events That Can Be Attended2016
2382. Maximum Segment Sum After Removals2136
2334. Subarray with Elements Greater Than Varying Threshold2381

§7.5 区間 Union-Find

問題レーティング
3244. Shortest Distance After Road Addition Queries II2270
1851. Minimum Interval to Include Each Query2286

§7.6 重み付き Union-Find（辺重み）

問題レーティング
399. Evaluate Division1725

八、BIT とSegment Tree

§8.1 BIT（Fenwick Tree）

問題レーティング
307. Range Sum Query Mutable1725
3072. Distribute Elements Into Two Arrays II2053
3624. Number of Integers with Popcount Depth Equal to K II2086
3187. Peaks in Array2154
1649. Create Sorted Array Through Instructions2208
1409. Queries on a Permutation with Key2208
2250. Count Number of Rectangles Containing Each Point2208
2179. Count Good Triplets in an Array2272
1395. Count Number of Teams2272
2659. Make Array Empty2282
2653. Sliding Subarray Beauty2282
3515. Shortest Path in a Weighted Tree2312
1505. Minimum Possible Integer After at Most K Adjacent Swaps on Digits2337
2736. Maximum Sum Queries2533
3382. Maximum Area Rectangle with Point Constraints II2723
3590. Kth Smallest Path XOR Sum2646
3245. Alternating Groups III3112
3027. Find the Number of Ways to Place People II2020
60. Permutation Sequence2020

§8.2 転倒数

問題レーティング
315. Count of Smaller Numbers After Self1725
493. Reverse Pairs1725
327. Count of Range Sum1725
2426. Number of Pairs Satisfying Inequality2030
1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number2030
2193. Minimum Number of Moves to Make Palindrome2030

§8.3 Segment Tree（区間更新なし）

問題レーティング
3479. Fruits Into Baskets III2178
2940. Find Building Where Alice AND Bob Can Meet2327
2286. Booking Concert Tickets in Groups2470
3161. Block Placement Queries2513
2213. Longest Substring of One Repeating Character2629
3525. Find X Value of Array II2645
3165. Maximum Sum of Subsequence with Non Adjacent Elements2697
3501. Maximize Active Section with Trade II2941

§8.4 Lazy Segment Tree（区間更新あり）

問題レーティング
2569. Handling Sum Queries After Update2398
1622. Fancy Sequence2476
2502. Design Memory Allocator2476
2589. Minimum Time to Complete All Tasks2381
850. Rectangle Area II2236
3454. Separate Squares II2671
3569. Maximize Count of Distinct Primes After Split2697
3721. Longest Balanced Subarray II2724

§8.5 Dynamic Segment Tree

問題レーティング
699. Falling Squares2286
715. Range Module2286
729. My Calendar I2286
731. My Calendar II2286
732. My Calendar III2286
2276. Count Integers in Intervals2222
3590. Kth Smallest Path XOR Sum2646

§8.6 Persistent Segment Tree

問題レーティング
3762. Minimum Operations to Equalize Subarrays2497

§8.7 Sparse Table

問題レーティング
3501. Maximize Active Section with Trade II2941

九、Splay Tree

§9.1 基礎

問題レーティング
2296. Design a Text Editor1912

十、Sqrt Decomposition系algorithm

§8.1 Sqrt Decomposition

問題レーティング
3655. XOR After Range Multiplication Queries II2454

§8.2 Mo's algorithm

問題レーティング
3636. Threshold Majority Queries2451
3590. Kth Smallest Path XOR Sum2646

§8.3 その他

問題レーティング
3234. Count the Number of Substrings with Dominant Ones2557

特集：Offline Algorithm

§10.1 基礎

問題レーティング
2343. Query Kth Smallest Trimmed Number1652
3607. Power Grid Maintenance1700
1847. Closest Room2082
2503. Maximum Number of Points From Grid Queries2196
1851. Minimum Interval to Include Each Query2286
2940. Find Building Where Alice AND Bob Can Meet2327
2747. Count Zero Request Servers2405
1938. Maximum Genetic Difference Query2503
2736. Maximum Sum Queries2533
3590. Kth Smallest Path XOR Sum2646
3382. Maximum Area Rectangle with Point Constraints II2723

特集：やや複雑な問題

Part A

問題レーティング
2532. Time to Cross a Bridge2589
2056. Number of Valid Move Combinations on Chessboard2611

Part B

問題レーティング
2468. Split Message Based on Limit2382
68. Text Justification2382
13. Roman to Integer1209
12. Integer to Roman1209
273. Integer to English Words2382
420. Strong Password Checker2382
8. String to Integer Atoi1408
65. Valid Number2863
146. Lru Cache2863
460. Lfu Cache2863

レーティングの上限を 1600 か 1900 にしている場合、ここの難しい問題はチャレンジリストで待機し、上限を上げる前にはヒロインが確認してくれます。

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

書斎を開く