競プロ用ライブラリ / AOJ の「コース」提出コード

更新日 : 2020-03-02

はじめに

この記事は、競技プログラミング用ライブラリ、そして Aizu Online Judge (AOJ) の「コース」で提出したコードを一覧にしています。
GitHub で公開している、

• GitHub - BEN2suzuka/proconlib: (C++ / C++14) 競技プログラミング用ライブラリ / AOJ「コース」提出コード

の README.md をそのまま載せています。
ここで公開しているコードは、競技プログラミングで使用することを想定しています。
そのため、一般的に奨励されない記述が含まれていることをご了承下さい。

まだまだ未熟者ですので、いろいろと目につくところがあるかもしれません (保険)。

目次

競プロ用ライブラリ

整数

• 素数判定
  • AOJ ALDS1 1_C : Prime Numbers
• エラトステネスのふるい
  • 蟻本 素数の個数
  • 蟻本 区間内の素数の個数 (区間ふるい)
• 素因数分解
  • AOJ NTL 1_A : Prime Factorize
• 最大公約数 (GCD)
  • AOJ ALDS1 1_B : Greatest Common Divisor
• 最小公倍数 (LCM)
  • AOJ NTL 1_C : Least Common Multiple
• 二項係数
  • ABC 034 C - 経路 (フェルマーの小定理を利用して逆元を計算)
  • ABC 156 D - Bouquet (n は巨大でも k は小さい)

探索

• 深さ優先探索 (DFS)
  • ABC 126 D - Even Relation
• 幅優先探索 (BFS)
  • ABC 007 C - 幅優先探索

AOJ アルゴリズムとデータ構造入門 (ALDS1)

AOJ アルゴリズムとデータ構造入門 (ALDS1) の提出コードです。

1. 入門
   • A : Insertion Sort
   • B : Greatest Common Divisor
   • C : Prime Numbers
   • D : Maximum Profit
2. 初等的ソート
   • A : Bubble Sort
   • B : Selection Sort
   • C : Stable Sort
   • D : Shell Sort
3. 基本データ構造
   • A : Stack
   • B : Queue
   • C : Doubly Linked List
   • D : Areas on the Cross-Section Diagram
4. 探索
   • A : Linear Search
   • B : Binary Search
   • C : Dictionary
   • D : Allocation
5. 分割統治法
   • A : Exhaustive Search
   • B : Merge Sort
   • C : Koch Curve
   • D : The Number of Inversions
6. ソート
   • A : Counting Sort
   • B : Partition
   • C : Quick Sort
   • D : Minimum Cost Sort
7. 木構造
   • A : Rooted Trees
   • B : Binary Trees
   • C : Tree Walk
   • D : Reconstruction of a Tree
8. 二分探索木
   • A : Binary Search Tree I
   • B : Binary Search Tree II
   • C : Binary Search Tree III
   • D : Treap
9. ヒープ
   • A : Complete Binary Tree
   • B : Maximum Heap
   • C : Priority Queue
10. 動的計画法
    • A : Fibonacci Number
    • B : Matrix Chain Multiplication
    • C : Longest Common Subsequence
    • D : Optimal Binary Search Tree
11. グラフI
    • A : Graph
    • B : Depth First Search
    • C : Breadth First Search
    • D : Connected Components
12. グラフII
    • A : Minimum Spanning Tree
    • B : Single Source Shortest Path I
    • C : Single Source Shortest Path II
13. ヒューリスティック探索
    • A : 8 Queens Problem
    • B : 8 Puzzle
    • C : 15 Puzzle
14. 文字列検索
    • A : Naive String Search
    • B : String Search
    • C : Pattern Search
    • D : Multiple String Matching
15. 貪欲アルゴリズム
    • A : Change Making
    • B : Fractional Knapsack Problem
    • C : Activity Selection Problem
    • D : Huffman Coding

AOJ プログラミング応用 (ITP2)

AOJ プログラミング応用 (ITP2) の提出コードです。

1. 動的配列とリスト
   • A : Vector
   • B : Deque
   • C : List
   • D : Vector II
2. 基本データ構造
   • A : Stack
   • B : Queue
   • C : Priority Queue
   • D : Splice
3. 列に対する操作
   • A : Min-Max
   • B : Min-Max Element
   • C : Count
   • D : Lexicographical Comparison
4. 列に対する変更
   • A : Reverse
   • B : Rotate
   • C : Swap
   • D : Unique
5. 順列
   • A : Sorting Pairs
   • B : Sorting Tuples
   • C : Permutation
   • D : Permutation Enumeration
6. 二分探索
   • A : Binary Search
   • B : Includes
   • C : Lower Bound
   • D : Equal Range
7. 集合
   • A : Set: Search
   • B : Set: Delete
   • C : Set: Range Search
   • D : Multi-Set
8. 辞書
   • A : Map: Search
   • B : Map: Delete
   • C : Map: Range Search
   • D : Multi-Map
9. 集合演算
   • A : Set Union
   • B : Set Intersection
   • C : Set Difference
   • D : Set Symmetric Difference
10. ビットセットI
    • A : Bit Operation I
    • B : Bit Operation II
    • C : Bit Flag
    • D : Bit Mask
11. ビットセットII
    • A : Enumeration of Subsets I
    • B : Enumeration of Subsets II
    • C : Enumeration of Subsets III
    • D : Enumeration of Combinations

AOJ データの集合とクエリ処理 (DSL)

AOJ データの集合とクエリ処理 (DSL) の提出コードです。

1. 集合
   • A : Disjoint Set: Union Find Tree (rank)
   • A : Disjoint Set: Union Find Tree (size)
   • B : Weighted Union Find Trees
2. 区間クエリ
   • A : Range Minimum Query (RMQ)
   • B : Range Sum Query (RSQ)
   • C : Range Search (kD Tree)
   • D : Range Update Query (RUQ)
   • E : Range Add Query (RAQ)
   • F : RMQ and RUQ
   • G : RSQ and RAQ
   • H : RMQ and RAQ
   • I : RSQ and RUQ
3. スライディングウィンドウ
   • A : The Smallest Window I
   • B : The Smallest Window II
   • C : The Number of Windows
   • D : Sliding Minimum Elements
4. 座標圧縮
   • A : Union of Rectangles
5. 累積和
   • A : The Maximum Number of Customers
   • B : The Maximum Number of Overlaps

AOJ 組み合わせ最適化 (DPL)

AOJ 組み合わせ最適化 (DPL) の提出コードです。

1. 組み合わせ
   • A : Coin Changing Problem
   • B : 0-1 Knapsack Problem
   • C : Knapsack Problem
   • D : Longest Increasing Subsequence
   • E : Edit Distance (Levenshtein Distance)
   • F : 0-1 Knapsack Problem II
   • G : Knapsack Problem with Limitations
   • H : Huge Knapsack Problem
   • I : Knapsack Problem with Limitations II
2. 順列
   • A : Traveling Salesman Problem
   • B : Chinese Postman Problem
   • C : Bitonic Traveling Salesman Problem
3. パターン
   • A : Largest Square
   • B : Largest Rectangle
   • C : Largest Rectangle in a Histogram
4. 数え上げ
   • A : Coin Combination Problem
   • B : Coin Combination Problem II
5. 写像12相
   • A : Balls and Boxes 1
   • B : Balls and Boxes 2
   • C : Balls and Boxes 3
   • D : Balls and Boxes 4
   • E : Balls and Boxes 5
   • F : Balls and Boxes 6
   • G : Balls and Boxes 7
   • H : Balls and Boxes 8
   • I : Balls and Boxes 9
   • J : Balls and Boxes 10
   • K : Balls and Boxes 11
   • L : Balls and Boxes 12

AOJ グラフ (GRL)

AOJ グラフ (GRL) の提出コードです。

1. 最短経路
   • A : Single Source Shortest Path
   • B : Single Source Shortest Path (Negative Edges)
   • C : All Pairs Shortest Path
2. 全域木
   • A : Minimum Spanning Tree (Prim)
   • A : Minimum Spanning Tree (Kruskal)
   • B : Minimum-Cost Arborescence
3. 連結成分
   • A : Articulation Points
   • B : Bridges
   • C : Strongly Connected Components
4. サイクル
   • A : Cycle Detection for a Directed Graph
   • B : Topological Sort
5. 木
   • A : Diameter of a Tree
   • B : Height of a Tree
   • C : Lowest Common Ancestor (Doubling)
   • C : Lowest Common Ancestor (Euler Tour)
   • D : Range Query on a Tree
   • E : Range Query on a Tree II
6. ネットワークフロー
   • A : Maximum Flow
   • B : Minimum Cost Flow
7. マッチング
   • A : Bipartite Matching

AOJ 整数論 (NTL)

AOJ 整数論 (NTL) の提出コードです。

1. 整数論
   • A : Prime Factorize
   • B : Power
   • C : Least Common Multiple
   • D : Euler's Phi Function
   • E : Extended Euclid Algorithm
2. 多倍長整数
   • A : Addition of Big Integers
   • B : Difference of Big Integers
   • C : Multiplication of Big Integers
   • D : Division of Big Integers
   • E : Remainder of Big Integers
   • F : Multiplication of Big Integers II