競技プログラミングのソース置場   WEB+DB 115   AOJ本   PAST本   けんちょん本   E8本(数学)   アリ本   ライブラリ   AOJ   ABC   ARC   PAST

目次

001 データの入出力
002 データの加工 
003 データ構造 
004 素数 
005 場合の数 
006 合同式 
007 グラフ 
008 ネットワークフロー 
009 C++のSIMD 
010 DP 
011 DP復元 
012 TSP問題 
013 LIS 
014 二分法 
015 三分探索 
016 尺取法 
017 オーバーフローの検知 
018 幾何 
019 等差数列 
020 等比数列 
021 群数列 
022 ハッシュ値 
023 転倒数 
024 インタラクティブ問題 
025 二次元グリッド 
026 01BFS 
027 45度回転で、マンハッタン距離とチェス盤距離を変換 
028 階乗 
029 文字列 
030 ビット演算 
031 途中からサイクルになる数列
032 イベントソート 
033 乱択アルゴリズム 
034 ゲーム問題 

090 その他の未整理なもの 
091 C#メモ 


001 データの入出力

旧サイトから移行する

001-01 ランダムデータでテスト
001-02 Dictionaryのデバッグ出力
001-03 セパレータと数値型の列挙を引数として、結合したstringを返す
001-04 二次元配列の入出力
001-05 ソートを定義した構造体とクラス
001-06 BigIntegerクラスのサンプル
001-07 サンプルの入出力作成ツール


002 データの加工

文字列のランレングス圧縮結果を返す ABC259-C XX to XXX
longの配列のランレングス圧縮結果を返す ARC023-C タコヤ木
列挙を引数として、座標圧縮し、座圧後の値[座圧前の値]なDictを返す ABC261-F Sorting Color Balls

IndStaとIndEndとUBを引数とし、IndEndがUBを超えたら、0から開始に変更し、区間のListを返す ABC340-E Mancala 2
OverLapした閉区間をマージ ABC256-D Union of Interval
HashSetのUnionWithでのマージテク ABC329-F Colored Ball

日暦算の感覚で、1オリジンでmod管理 ABC410-C Rotatable Array

10進数をK進数に変換して返す ABC414-C Palindromic in Both Bases


003 データ構造

PriorityQueue (根が最小) (内部でDictionary使用) ABC212-D Querying Multiset
PriorityQueue (根が最大) (内部でDictionary使用) ABC249-F Ignore Operations
PriorityQueue (根が最小) (内部で配列使用) ABC323-D Merge Slimes
PriorityQueue (根が最小) (複数ソートキー) (内部で配列使用) 第7回PAST K 急ぎ旅
PriorityQueue (根が最大) (内部で配列使用) 第15回PAST J 忍者
UnionFind AOJ DSL_1_A: Disjoint Set: Union Find Tree
UnionFindSizeInfo ABC214-D Sum of Maximum Weights
UnionFindSizeAndEdgeCntInfo ABC292-D Unicyclic Components
UnionFindMinMaxInfo AOJ 0647 ストーブ
UnionfFindWithAnyInfo ABC229-E Graph Destruction
UnionfFindWithAnyInfo(木の最小ノードと最大ノードも取得可能) ABC414-D Transmission Mission
セグ木(RMinQ) AOJ DSL_2_A: Range Minimum Query
セグ木(RMaxQ) 第3回PAST L スーパーマーケット
セグ木(RSQ) AOJ DSL_2_B: Range Sum Query
セグ木でモノイドを指定 ABC343-F Second Largest Query
フェニック木 ABC351-E Jump Distance Sum
フェニック木 (法を指定可能) ABC263-E Sugoroku 3
双対セグ木(区間加算、1点取得) AOJ DSL_2_E: Range Add Query (RAQ)
双対セグ木(区間加算、1点取得) (法を指定可能) ABC341-E Alternating String
遅延セグ木(RMinQとRUQ) AOJ DSL_2_F: RMQ and RUQ
遅延セグ木(RSumQとRAQ) AOJ DSL_2_G: RSQ and RAQ
遅延セグ木(RMinQとRAQ) AOJ DSL_2_H: RMQ and RAQ
遅延セグ木(RSumQとRUQ) AOJ DSL_2_I: RSQ and RUQ
遅延セグ木(RMaxQとRAQ) Educational DP Contest W Intervals
遅延セグ木(RMaxQとRUQ) ABC386-D Diagonal Separation
セグ木(RMQ)での拡張機能 (最小値と、最小値を持つIndを返す) (全区間のみ) ABC267-E Erasing Vertices 2
セグ木(RMQ)での拡張機能 (最小値と、最小値を持つIndを返す) (区間指定可) ARC134-B Reserve or Reverse
AVL木 ABC281-E Least Elements
AVL木で構造体でソート ABC267-E Erasing Vertices 2
AVL木と下限と上限を引数とし、区間削除を行い、削除した値のListを返す ABC385-D Santa Claus 2
RBST ABC134-E Sequence Decomposing
ウェーブレット木 AOJ 1549 Hard Beans
スパーステーブル ABC014-D 閉路
Deque AOJ DSL_3_D: Sliding Minimum Elements
ImplicitTreap ARC153-B Grid Rotations
kD Tree AOJ DSL_2_C: Range Search (kD Tree)

遅延セグ木の区間加算で累積和の差分更新その1 CodeQUEEN 2025 決勝 D 特訓
遅延セグ木の区間加算で累積和の差分更新その2 AOJ 0648 美術展(Art Exhibition)


004 素数

試し割りで素数判定 AOJ ALDS1_1_C: Prime Numbers
素因数分解し、指数[素数]なDictを返す ABC169-D Div Game
約数列挙 ABC112-D Partition
ユークリッドの互除法 ARC110-A Redundant Redundancy
エラトステネスの篩 ABC250-D 250-like Number

IEnumerable<long> を引数とし、最大公約数を返す E8本(数学) 015 Greatest Common Divisor of N Integers
IEnumerable<long> を引数とし、最小公倍数を返す ABC150-D Semi Common Multiple


005 場合の数

AOJの写像12相 AOJ DPL_5_C: Balls and Boxes 3
階乗 (mod Hou)を求める ARC143-B Counting Grids
nPr (mod Hou)を求める ARC143-B Counting Grids
nCr (mod Hou)を求める ARC039-B 高橋幼稚園
nCr をnの最大値指定で事前準備し、高速に求める ABC151-E Max-Min Sums
パスカルの三角形を作成する ABC425-E Count Sequences 2

C++のnext_permutation、prev_permutation C++のnext_permutation、prev_permutation
Rubyの順列、組合せ、重複順列、重複組合せ Rubyの場合の数を求めるメソッド
集合をベル数で分割 ABC390-D Stone XOR
列挙、取得数下限、取得数上限を引数とし、配列の列挙を返す 競技プログラミングの鉄則 A72 Tile Painting

包除原理その1 E8本(数学) 068 Number of Multiples 2
包除原理その2 ABC246-F typewriter


006 合同式

ModPow(繰返し2乗法) ARC039-B 高橋幼稚園
フェルマーの小定理で逆元を求める ARC039-B 高橋幼稚園
フェルマーの小定理で逆元を求める(キャッシュ付き) ABC280-E Critical Hit
合同方程式、A*X ≡ B (mod M) を解く ABC186-E Throne
中国剰余定理 ABC193-E Oversleeping


007 グラフ

004-01 DFSのテンプレート
004-02 BFSのテンプレート

再帰でDFSその1(訪問済ノードをグローバルに持つ) ABC293-C Make Takahashi Happy
再帰でDFSその2(訪問済ノードをグローバルに持つ) ABC284-E Count Simple Paths

隣接リストのデータ作成(枝にコスト有り) 第8回PAST H 最短経路
隣接リストのデータ作成(枝にコスト無し) ABC199-D RGB Coloring 2

無向グラフの連結成分分解その1(代表ノード[ノード]なDict) ALDS1_11_D: Connected Components
無向グラフの連結成分分解その2(ノードList[代表ノード]なDict) ABC199-D RGB Coloring 2

有向グラフで強連結成分分解 ABC245-F Endless Walk

トポロジカルソート(DFS) Educational DP G Longest Path
トポロジカルソート(BFSで小さいノード番号を優先) ABC223-D Restricted Permutation

有向グラフでの閉路判定 第7回PAST J 終わりなき旅
無向グラフでの閉路判定 ABC231-D Neighbors

ファンクショナルグラフでの閉路数を返す ARC114-B Special Subsets

ダイクストラ法(コストが単数)その1 ABC340-D Super Takahashi Bros.
ダイクストラ法(コストが単数)その2 競技プログラミングの鉄則 A64 Shortest Path 2
ダイクストラ法(コストが単数)その3 ABC325-E Our clients, please wait a moment
ダイクストラ法(コストが文字列) ABC417-E A Path in A Dictionary
ダイクストラ法(複数ソートキー) 競技プログラミングの鉄則 A73 Marathon Route
ダイクストラ法(逆辺)その1 ABC342-E Last Train
ワーシャルフロイド法(コストが単数) 典型アルゴリズム問題集 E 全点対最短経路問題
ワーシャルフロイド法(コストを構造体で管理) ABC286-E Souvenir
ワーシャルフロイド法(頂点を倍加) 第17回PAST L 割引券
ワーシャルフロイド法(辺の追加による部分更新) ABC416-E Development
ベルマンフォード法 GRL_1_B: Single Source Shortest Path (Negative Edges)

クラスカル法 典型アルゴリズム問題集 F 最小全域木問題
プリム法 ALDS1_12_A: Minimum Spanning Tree

再帰でオイラーツアー(訪問と帰りを表示) ABC213-D Takahashi Tour
Stackでオイラーツアー(訪問と最後の帰りを表示) ABC202-E Count Descendants

ダイクストラ木 ABC252-E Road Reduction
DFS木 ABC251-F Two Spanning Trees
BFS木 ABC251-F Two Spanning Trees

木のLCAのレベルを求める ABC014-D 閉路
木のLCAのノードを求める 典型問題(上級) D 最小共通祖先
木の直径を求める GRL_5_A: Diameter of a Tree

無向グラフの橋の列挙を返す ABC266-F Well-defined Path Queries on a Namori

最良優先探索(ソートを定義した構造体) AOJ 0705 パレード


008 ネットワークフロー

最大流でエドモンズ・カープ(BFS) GRL_6_A: Maximum Flow
二部マッチングでエドモンズ・カープ(BFS) GRL_7_A: Bipartite Matching
二部マッチングでフォード・ファルカーソン(DFS) AOJ 1163 カードゲーム
最小費用流でベルマンフォード法その1 GRL_6_B: Minimum Cost Flow
最小費用流でベルマンフォード法その2 典型問題(上級) F 最小費用流


009 C++のSIMD

ABC091-D Two Sequences


010 DP

構造体のハッシュ値を状態に持つDP ABC322-E Product Development

桁DPその1 Educational DP Contest S Digit Sum
桁DPその2 ABC336-E Digit Sum Divisible
桁DPその3 ARC173-A Neq Number
桁DPその4 ABC387-C Snake Numbers
2進数での桁DPその1 ARC129-A Smaller XOR

場合の数と合計を持って桁DPその1 ABC235-F Variety of Digits
場合の数と合計を持って桁DPその2 ABC406-E Popcount Sum 3

区間DPその1 AOJ 1611 ダルマ落とし
区間DPその2 第5回PAST L T消し
区間DPその3 Educational DP Contest N Slimes
区間DPその4 競技プログラミングの鉄則 A21 Block Game

期待値DPその1 ABC184-D increment of coins
期待値DPその2 Educational DP Contest J Sushi
期待値DPその3 TDP J ボール
期待値DPその4 PAST5回 K 的あて
期待値DPその5 ABC280-E Critical Hit
期待値DPその6 ABC350-E Toward 0

部分列DPその1 AOJ 2895 回文部分列 (Palindromic Subsequences)
部分列DPその2 ARC081-E Don't Be a Subsequence
部分列DPその3 TDP G 辞書順

木DPその1 競技プログラミングの鉄則 B65 Road to Promotion Hard
木DPその2 ABC239-E Subtree K-th Max

全方位木DPその1 AOJ 1595 Traffic Tree
全方位木DPその2 Educational DP Contest V Subtree
全方位木DPその3 ABC160-F Distributing Integers
全方位木DPその4 ABC220-F Distance Sums 2

円環で、先頭と直前を状態に持つDPその1 ABC229-F Make Bipartite
円環で、先頭と直前を状態に持つDPその2 ABC251-E Tahakashi and Animals

いもす法で配るDPその1 Educational DP Contest M Candies
いもす法で配るDPその2 ABC179-D Leaping Tak
いもす法で配るDPその3 ABC222-D Between Two Arrays
いもす法で配るDPその4 ABC249-E RLE
いもす法で配るDPその5 ABC253-E Distance Sequence

連結DPその1 ABC248-F Keep Connect

キューを使って、遅延更新するDP CodeQUEEN 2024 決勝 C Attraction on Rainy Day

Bool値DPからの計算量の改善その1 ABC364-E Maximum Glutton
Bool値DPからの計算量の改善その2 ABC410-E Battles in a Row


011 DP復元

DP復元その1 競技プログラミングの鉄則 A17 Dungeon 2
DP復元その2 典型90問 056 Lucky Bag(★5)
DP復元その3 第17回PAST K 正しいチェックディジット


012 TSP問題

TSP問題その1 競技プログラミングの鉄則 B23 Traveling Salesman Problem
TSP問題その2 ABC180-E Traveling Salesman among Aerial Cities
TSP問題その3 ABC274-E Booster


013 LIS

列挙を引数として、狭義単調増加なLISの長さを返す ARC121-B Dividing Subsequence
広義単調増加なLISを求める ABC369-F Gather Coins


014 二分法

二分法でLowerBound(配列) ARC121-B RGB Matching
二分法でUpperBound(配列) TDP G 辞書順
二分法でLower_Max(配列) TDP G 辞書順
二分法でLowerOrEqual_Max(配列) ABC172-C Tsundoku

二分法でLowerBound(List) ABC360-D Ghost Ants
二分法でUpperBound(List) ABC346-F SSttrriinngg in StringString
二分法でLowerOrEqual_Max(List) ABC360-D Ghost Ants

二分法で、Valとの差の最小値を返す ARC121-B RGB Matching

CanAchieveメソッドを使った二分法その1(long型) ABC144-E Gluttony
CanAchieveメソッドを使った二分法その2(decimal型) ABC236-E Average and Median
CanAchieveメソッドを使った二分法その3(double型) ABC255-B Light It Up

二分法で広義単調減少での連続した値の区間を求める ABC230-E Fraction Floor Sum
二分法で関数の最大下界を求める ABC342-E Last Train
{昇順にソートされた配列,Min,Max}を引数とし、Min以上Max以下な値の個数を返す ABC364-D K-th Nearest
{昇順にソートされたList,Min,Max}を引数とし、Min以上Max以下な値の個数を返す yukicoder 2758 RDQ
二分法でdecimal型のsqrtを求める ABC279-D Freefall


015 三分探索

三分探索で極小値(long)を求めるその1 ABC212-C Min Difference
三分探索で極小値(long)を求めるその2 ABC279-D Freefall
三分探索で極小値(double)を求めるその1 第6回PAST J ポイントとコストと
三分探索で極小値(double)を求めるその2 ABC426-E Closest Moment


016 尺取法

尺取法その1 ARC022-B 細長いお菓子
尺取法その2 ABC032-C 列
尺取法その3 典型90問 034 There are few types of elements(★4)
尺取法その4 AOJ DSL_3_A: The Smallest Window I
尺取法その5 yukicoder 2930 Larger Mex


017 オーバーフローの検知

2つの非負整数の足し算が、Limitを超えるかを返す TDP G 辞書順
long型の2正数の掛け算が、Limitを超えるかを返す E8本(数学) 089 Log Inequality 2
decimal型の2正数の掛け算が、Limitを超えるかを返す ABC406-B Product Calculator


018 幾何

ベクトルの内積を求める ARC042-B アリの高橋くん
ベクトルの外積を求める ARC042-B アリの高橋くん

線分の交差判定 AOJ CGL_2_B: Intersection

点と線分との距離を求める ARC042-B アリの高橋くん
線分と線分との距離を求める AOJ CGL_2_D: Distance

度数法の角度をラジアンに変換 ABC259-B Counterclockwise Rotation
ベクトルとSinとCosを引数として、回転したベクトルを返す ABC259-B Counterclockwise Rotation

円の軌跡が指定座標を含むかを返す ABC259-D Circumferences
円と円の位置関係を判定する E8本(数学) 035 Two Circles

2次元ベクトルの各成分を、GCD(X成分,Y成分)で割る ABC248-E K-colinear Line
変位ベクトルをタンジェントで同一化 ABC418-E Trapezium

(X1,Y1) , (X2,Y2) を引数とし、2点を通る直線の、aX + bY + c = 0 の (a,b,c)を設定 ABC422-E Colinear


019 等差数列

初項と公差と項数を引数として、等差数列の和を返す ABC253-D FizzBuzz Sum Hard
初項と公差と項数と法を引数として、等差数列の和を返す ABC238-C digitnum
初項と末項と公差と法を引数として、等差数列の和を返す HHKB 2020 D Squares


020 等比数列

初項,公比,項数,法を引数とし、等比数列の和を返す(法が逆元を持つ場合) ABC224-F Problem where +s Separate Digits
初項,公比,項数,法を引数とし、等比数列の和を返す(法が逆元を持たなくても可)  ABC293-E Geometric Progression


021 群数列

群数列その1 ABC-029-D 1
群数列その2 競技プログラミングの鉄則 B37 Sum of Digits


022 ハッシュ値

Zobrist Hash ABC250-E Prefix Equality


023 転倒数

列挙を引数として、列挙内での転倒数を返す ABC261-F Sorting Color Balls


024 インタラクティブ問題

集合に無い値を返す ABC244-C Yamanote Line Game
二分探索のように、範囲を絞るその1 ABC299-D Find by Query
二分探索のように、範囲を絞るその2 ABC269-E Last Rook


025 二次元グリッド

ベクトルのX成分とY成分を引数とし、90度回転させた値を設定 ABC339-B Langton's Takahashi

右に90度回転させた盤面を返す ABC210-D National Railway
盤面のハッシュ値を求める ABC264-C Matrix Reducing
盤面の指定行を消す ABC264-C Matrix Reducing
盤面の指定列を消す ABC264-C Matrix Reducing
2次元配列の使用してない部分を縮小して返す(char型の2次元配列用) ABC322-D Polyomino

2次元グリッドへの敷き詰めその1 ABC196-D Hanjo
2次元グリッドへの敷き詰めその2 ABC322-D Polyomino
2次元グリッドへの敷き詰めその3 ABC345-D Tiling

二次元累積和その1 ARC025-B チョコレート
二次元累積和その2 競技プログラミングの鉄則 A08 Two Dimensional Sum
二次元累積和その3 典型90問 081 Friendly Group(★5)

二次元いもす法その1 競技プログラミングの鉄則 A09 Winter in ALGO Kingdom
二次元いもす法その2 典型90問 028 Cluttered Paper(★4)

三次元いもす法その1 AOJ 0580 魚の生息範囲

コンピュータ座標の矩形の数値和を求めるクラス ABC331-D Tile Pattern
ユークリッド座標の矩形の数値和を求めるクラス ABC354-D AtCoder Wallpaper


026 01BFS

01BFSその1 典型90問 043 Maze Challenge with Lack of Sleep(★4)
01BFSその2 ABC213-E Stronger Takahashi
01BFSその3 ABC277-E Crystal Switches
01BFSその4 ARC177-C Routing


027 45度回転で、マンハッタン距離とチェス盤距離を変換

45度回転その1 典型90問 036 Max Manhattan Distance(★5)
45度回転その2 ABC351-E Jump Distance Sum


028 階乗

ルジャンドルの定理 ABC280-D Factorial and Multiple


029 文字列

文字列のソートでStringComparer.Ordinalの指定で定数倍の高速化 ABC155-C Poll

ローリングハッシュ(long型) 競技プログラミングの鉄則 A56 String Hash
ローリングハッシュ(decimal型) ABC287-E Karuta
ローリングハッシュ(decimal型) で左や右に文字追加の拡張機能 ARC172-C Election

トライ木 ABC411-D Conflict 2

文字列Sが、文字列Tの(連続してなくてもよい)部分列かを判定 ARC154-B New Place
文字列を引数とし、部分集合の文字列の個数を返す 第11回PAST K 部分列
string型を引数とし、回文判定を行う ABC359-D Avoid K Palindrome
string型を引数とし、reverse ABC414-C Palindromic in Both Bases


030 ビット演算

引数のBitSetの部分集合の列挙を返す Educational DP Contest U Grouping
C++のPopCount ABC242-D ABC Transform
Nを引数とし、0からNまでの2進数表現での、0の個数を返す ABC356-D Masked Popcount

ビット全探索と島判定 ABC219-E Moat


031 途中からサイクルになる数列

途中からサイクルになる数列その1 ABC179-E Sequence Sum
途中からサイクルになる数列その2 典型90問 058 Original Calculator(★4)
途中からサイクルになる情報 ABC258-E Packing Potatoes

ダブリングその1 競技プログラミングの鉄則 A57 Doubling
ダブリングその2 競技プログラミングの鉄則 B57 Calculator

ファンクショナルグラフでのダブリング ABC367-E Permute K times


032 イベントソート

イベントソートその1 ABC274-F Fishing


033 乱択アルゴリズム

ラスベガス法(Guidでランダマイズソート) ABC315-D Magical Cookies
モンテカルロ法(1.9秒の間、最良値を調べる) ARC173-B Make Many Triangles


034 ゲーム問題

勝敗をメモ化再帰で求めるその1 競技プログラミングの鉄則 A32 Game 1
勝敗をメモ化再帰で求めるその2 ABC349-E Weighted Tic-Tac-Toe


090 その他の未整理なもの

平衡三進数に変換 第7回PAST G べき表現

行列での繰り返し二乗法 Educational DP Contest R Walk

decimal型でのsqrtメソッド ABC279-D Freefall


091 C#メモ

C#メモ