リポジトリ 競プロ的なことを久しぶりにしたので、http://kanetai.hatenablog.com/entry/20110519/1305833341の一部を少し整理。 term description 約数(divisor), 因数,因子(factor) ある自然数を割り切る整数。 素数(prime number) 自分自身と１以外の自然…

リポジトリ Arrays.sortに習って、a[fromIndex, toIndex)がソートされるようにしてみる。 また、javaにはswap()がないので適当に実装しておく。 public static final void xxxSort(T a[], int fromIndex, int toIndex) { ... } public static final int[] sw…

最小費用流問題を特殊化。 ソース節点sが複数ユニットを配布節点w経由でシンク節点に到達するように流す。各辺には、容量と実際のフローが付随する。 目標：ネットワークフローFを最大にする コード 残余ネットワークから増加パスを求める系のアルゴリズムを…

Network Flow Algorithms フローネットワーク(Flow network)/輸送網(Transportation network)を扱うアルゴリズム。 各アークに容量(capacity)を設定し、各アークをフロー(flow)が流れる。 ネットワークフローアルゴリズムの適用分やには次のような物がある。…

リポジトリ 有向グラフ(directed graph, digraph) 強連結(strongly connected)： 有向グラフの任意の２頂点u, vに対して、uからvに到達可能かつvからuに到達可能、すなわち、任意の２頂点に双方向の道が存在するとき、その有向グラフは強連結であるという。 …

リポジトリ Union-Find データの集合を素集合（互いにオーバーラップしない集合）に分割して保持する素集合データ構造(disjoint-set data structure)に対して行う、次の操作をUnion-Findアルゴリズムと呼ぶ。 Find: 特定の要素がどの集合(グループ)に属して…

立方体のユーティリティークラス Spaghetti Source - さいころを参考。つーかただの翻訳。 右手系で、x軸の正方向がFRONT, z軸の正方向がTOP. 同値判定と全回転状態の生成では，x 軸周りの回転と y 軸周りの回転を交互に行いながら，z 軸周りの回転を 4 回繰…

()ありの四則演算するだけのやつ トップダウン構文解析で解く。 BNFで書くと ::= | ::= | ::= '(' ')' | ::= '+' | '-' ::= '*' | '/' 左再帰を取り除くと ::= ::= | ε ::= ::= | ε ::= '(' ')' | ::= '+' | '-' ::= '*' | '/' 末尾再帰はループで書ける ::=…

リポジトリ グラフ理論（Graph theory） 周遊可能(traversable) : 多重グラフの全ての頂点を含み,各辺をちょうど１回だけ用いる歩道が存在する(一筆書きができるグラフ)。 オイラーグラフ(Eulerian graph) : オイラー小道が存在するグラフ 準オイラーグラフ(…

リポジトリ Fenwick tree, binray indexed tree(BIT) が与えられたとき、 累積和 加算更新 の操作ができるデータ構造で、空間計算量は、構築にかかる計算量は(n回addするので)。 当然だが(頻繁に)更新を行わないのであれば、普通にでテーブル作った方がいい…

リポジトリ 数列が与えられたとき、からいくつかの項を脱落させた数列を考える。 においてが成立するときを最長増加部分列(Longest Increasing Subsequence;LIS)という。 版 を最終要素とするLIS長とすると [tex: DP_i = \max \left \{ \begin{array}{lr} DP…

リポジトリ グラフ理論（Graph theory） 単一始点最短路(Single-Source Shortest Path) 全点対間最短路(all-pairs shortest-path) 最小全域木(minimum spanning tree) 巡回セールスマン問題(Traveling Salesman Problem) グラフアルゴリズムで共通で使う要素…

リポジトリ グラフの基本要素はグラフ(Graph) - kanetaiの二次記憶装置のほうにまとめる。 計算結果の単一始点最短距離とバックポインタ。buildPathで最短経路を構築する。 /** Results of Single-Source Shortest Path (SSSP) Algorithm */ public static c…

リポジトリ TODO: distanceLP distanceLL distanceLS 点間距離だけでなくいろいろあった方が便利なので作っとく 線分と点 のへの正射影を求めて、が上にあれば、 無ければ、 //instance method of Point class public final double distancePS(Line s){ Poin…

正射影(orthograph, orthogonal projection) 射影(projection)、鏡映(reflection) 一点からある直線または平面上に下ろした垂線の交点(垂線の足:foot of a perpendicular)。図形(点の集合)についても、図形上のすべての点の垂線の足の集合を正射影と呼ぶ。 …

リポジトリ 巡回セールスマン問題(TSP: Traveling Salesman Problem) 最短ハミルトン閉路(各頂点を1回だけ含む(開始・終了点を除く)閉じた歩道(閉路))を見つける問題 NP困難なため、多項式時間で解けない。競技プログラミングでは、ビットDPによる解法を知っ…

リポジトリ 計算結果（最短距離とバックポインタ） 最短経路はbuildPath()で復元。 /** Results of All-Pairs Shortest Path (APSP) Algorithm */ public static class APSPResult{ private int[][] dist; // dist[d]:= shortest path to d private int[][] …

参考ページ 魔方陣 - Wikipedia http://www2u.biglobe.ne.jp/~zed/m_stitle.htm 魔方陣(magic square) 正方形で縦・横・斜の数字の合計がすべて等しい方陣。 特に、(次)の行列の方陣の要素として()を重複なく使用したものを魔方陣と呼ぶことが多い。 その場…

リポジトリ ニュートン法(Newton's method), ニュートン・ラフソン法(Newton-Raphson method) 非線型方程式の反復的な数値解法の一つ。 もう少し詳しい説明はニュートン法 - Wikipedia。 初期値を与えて、を収束するまで(例えば、増分が小さくなる()まで)繰…

リポジトリ 全域木(spanning tree), 極大木 : においてとなる辺集合があるとき、グラフが木（閉路を持たないグラフ）であるなら、 をの全域木と呼ぶ。 (全域木が存在することと連結であることは同値) 最小全域木(MST: Minimum Spanning Tree) : 使われる辺の…

リポジトリ TODO: intersect_LS intersect_LP 参考ページ月の杜工房 - 2直線の交点を求める 直線 平面幾何(plane geometory) を使って、直線クラスを作ってみた。(直線(line)といいつつも、線分(segment)としても使うので注意) public static class Line{ pr…

リポジトリ next_permutation - C++ Reference Javaにnext_permutationが無いので、作ってみた。 C++のstd::next_permutationもそうだが、順列を全列挙したいならはじめに昇順ソートしておいて、do-whileのwhileの中でnextPermutationを使わないといけない。…

リポジトリ 点(point) complexクラスがあればそれで代用してもいい。 演算子オーバーロードが無いと面倒すぎる。 法線ベクトルは複素数を考えればすぐわかる import java.awt.geom.Point2D; static final double EPS = 1e-10; static boolean equal(double a…

リポジトリ binary_search - C++ Reference lower_bound - C++ Reference upper_bound - C++ Reference ※ほぼ全部未検証 2分探索(binary search) ソート済のデータに対してで探索を行う(はデータ数)。 たいていの言語に標準で2分探索の関数が用意されてるの…

リポジトリ 参考になりそうなページ ＭＡの天文計算サンプル集 − 日時とユリウス日の変換 雑食系猫的楽書帳 閏年(leap year) ユリウス暦(Julian calendar)は、紀元前46年、古代ローマで採用された。4年に1回、西暦年が4で割り切れる年を閏年としていた。現行…

リポジトリ 参考になりそうなページ 再帰アルゴリズムによるユークリッド互除法 最大公約数(GCD;Greatest Common Divisor) 2つ以上の整数の最大公約数はの最大の公約数 Euclidの互除法(Euclidean algorithm, Euclid's algorithm) について、が成立することを…

個数制限なしナップザック問題(プログラミングコンテストチャレンジブック p58) 重さと価値がそれぞれであるような個の品物がある。 これらの中から重さの総和がを超えないように選んだ時の価値の総和の最大値を求める。 ただし、同じ品物をいくつでも選んで…

最長共通部分列問題(LCS; Longest Common Subsequence) 二つの値の列が与えられて，最長の共通部分列を見つける問題。 部分列は連続している必要はないが，順序は変更してはい。 LCSは一般的に複数ある。 Common Subsequence(PKU No.1458) 二つの文字列とが…

01ナップザック問題(プログラミングコンテストチャレンジブック p34) 重さと価値がそれぞれであるような個の品物がある。 これらの中から重さの総和がを超えないように選んだ時の価値の総和の最大値を求める。 制約 アルゴリズム1 i番目以降の品物から重さの…

リポジトリ TODO: 連立線形合同 中国剰余定理 mod_fact cCk mod p ... 合同式(modular equality) 二つの整数, 自然数について、 なら、 , () と書き、がを法(modulus)として合同(congruent)という。 上の性質より、加減乗除を組み合わせた合同演算では、途中…