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

001 データの入出力

旧サイトから移行する

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


002 データの加工

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


003 データ構造

PriorityQueue (根が最小) ABC212-D Querying Multiset
PriorityQueue (根が最大) ABC249-F Ignore Operations
UnionFind AOJ DSL_1_A: Disjoint Set: Union Find Tree
UnionFindSizeInfo ABC214-D Sum of Maximum Weights
セグ木(RMQ) AOJ DSL_2_A: Range Minimum Query
セグ木(RMaxQ) 第3回PAST L スーパーマーケット
セグ木(RSQ) AOJ DSL_2_B: Range Sum Query
フェニック木 AOJ DSL_2_B: Range Sum Query
フェニック木 (法を指定可能) ABC263-E Sugoroku 3
遅延セグ木 AOJ DSL_2_F: RMQ and RUQ
遅延セグ木 AOJ DSL_2_G: RSQ and RAQ
遅延セグ木 AOJ DSL_2_H: RMQ and RAQ
遅延セグ木 AOJ DSL_2_I: RSQ and RUQ
遅延セグ木(RMaxQとRAQ) Educational DP Contest W Intervals
セグ木(RMQ)での拡張機能 (最小値と、最小値を持つIndを返す) (全区間のみ) ABC267-E Erasing Vertices 2
セグ木(RMQ)での拡張機能 (最小値と、最小値を持つIndを返す) (区間指定可) ARC134-B Reserve or Reverse
AVL木 ABC241-F Skate
AVL木で構造体でソート ABC267-E Erasing Vertices 2
RBST ABC134-E Sequence Decomposing
ウェーブレット木 AOJ 1549 Hard Beans
スパーステーブル ABC014-D 閉路


004 素数

試し割りで素数判定 AOJ ALDS1_1_C: Prime Numbers
素因数分解し、指数[素数]なDictを返す ABC169-D Div Game
約数列挙 ABC112-D Partition
ユークリッドの互除法 ARC110-A Redundant Redundancy
最大公倍数 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 グラフ

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

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

無向グラフの連結成分分解 ALDS1_11_D: Connected Components

ダイクストラ法 典型アルゴリズム問題集 D 単一始点最短経路問題
ワーシャルフロイド法 典型アルゴリズム問題集 E 全点対最短経路問題
ベルマンフォード法 GRL_1_B: Single Source Shortest Path (Negative Edges)

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

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

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

トポロジカルソート Educational DP G Longest Path

再帰でオイラーツアー(訪問と帰りを表示) 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

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

木のLCAを求める ABC014-D 閉路

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


006 ネットワークフロー

最大流でエドモンズ・カープ GRL_6_A: Maximum Flow
二部マッチングでエドモンズ・カープ GRL_7_A: Bipartite Matching
二部マッチングでフォード・ファルカーソン AOJ 1163 カードゲーム
最小費用流でベルマンフォード法 GRL_6_B: Minimum Cost Flow


007 場合の数

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
nHr を求める(法も指定可)

C++のnext_permutation、prev_permutation C++のnext_permutation、prev_permutation
Rubyの順列、組合せ、重複順列、重複組合せ Rubyの場合の数を求めるメソッド

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


008 合同式

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


009 C++のSIMD

ABC091-D Two Sequences


010 DP

桁DPその1 ABC235-F Variety of Digits
2進数での桁DPその1 ARC129-A Smaller XOR

区間DPその1 AOJ 1611 ダルマ落とし
区間DPその2 第5回PAST L T消し
区間DPその3 Educational DP Contest N Slimes

期待値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その1 AOJ 2895 回文部分列 (Palindromic Subsequences)
部分列DPその2 ARC081-E Don't Be a Subsequence
部分列DPその3 TDP G 辞書順

木DPその1 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


011 LIS

列挙を引数として、LISの長さを返す ARC121-B Dividing Subsequence


012 二分法

二分法でLowerBound ARC121-B RGB Matching
二分法でUpperBound TDP G 辞書順
二分法でLower_Max TDP G 辞書順
二分法でLowerOrEqual_Max ABC172-C Tsundoku
二分法で、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


013 三分探索

三分探索で極小値(long)を求める ABC212-C Min Difference
三分探索で極小値(double)を求める 第6回PAST J ポイントとコストと


014 尺取法

尺取法 ARC022-B 細長いお菓子


015 オーバーフローの検知

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


016 幾何

ベクトルの内積を求める 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


017 数列

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

初項と公比と項数と法を引数として、等比数列の和を返す ABC224-F Problem where +s Separate Digits


018 ハッシュ値

Zobrist Hash ABC250-E Prefix Equality


019 転倒数

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


020 インタラクティブ問題

集合に無い値を返す ABC244-C Yamanote Line Game
二分探索のように、範囲を絞る ABC269-E Last Rook


021 二次元グリッド

右に90度回転させた盤面を返す ABC210-D National Railway
盤面のハッシュ値を求める ABC264-C Matrix Reducing
盤面の指定行を消す ABC264-C Matrix Reducing
盤面の指定列を消す ABC264-C Matrix Reducing


022 階乗

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


090 その他の未整理なもの

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

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

TSP問題のBitDPでの解 ABC180-E Traveling Salesman among Aerial Cities

OverLapした閉区間をマージ ABC256-D Union of Interval

二次元累積和 ARC025-B チョコレート

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

途中からサイクルになる数列 ABC179-E Sequence Sum
途中からサイクルになる情報 ABC258-E Packing Potatoes

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

C++のPopCount ABC242-D ABC Transform

引数のBitSetの部分集合の列挙を返す Educational DP Contest U Grouping


091 C#メモ

C#メモ