読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Algorithm

素数判定 (Primality Test)

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

ソート、整列(sorting)

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

最大流問題(Maximum Flow Problem)

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

Network Flow Algorithm

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

強連結成分分解(Decomposition of Strongly Connected Components)

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

Union-Find

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

Cube

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

構文解析(Syntactic Analysis)

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

オイラー路(Euler Path)

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

Fenwick tree, binray indexed tree(BIT)

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

最長増加部分列(longest increasing subsequence)

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

グラフ(Graph)

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

単一始点最短路(Single-Source Shortest Path)

リポジトリ グラフの基本要素はグラフ(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)。図形(点の集合)についても、図形上のすべての点の垂線の足の集合を正射影と呼ぶ。 …

巡回セールスマン問題(Traveling Salesman Problem)

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

全点対間最短路(all-pairs shortest-path)

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

魔方陣(magic square)

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

数値計算(numerical computation)

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

最小全域木(minimum spanning tree)

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

平面幾何(交差判定)

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

nextPermutation

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

平面幾何(plane geometory)

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

2分探索(binary search)

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

日付関連

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

最大公約数、最小公倍数、GCD and LCM(AOJ No.0005)

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

個数制限なしナップザック問題

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

最長共通部分列問題、Common Subsequence(PKU No.1458)

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

01ナップザック問題

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

合同式、オイラーの定理

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

リンク

Wikipedia 数学 数学のいろいろ私の備忘録 tex 物理、プログラミング, etchttp://moondial0.net/archives/www12.plala.or.jp/ksp/ LaTeXコマンドシート一覧 tex,matlab,gnuplot,etc.move @KUMAZAWA Yoshiki C++ 日記2012-02-26 - 思うだけで学ばない日記 リ…

約数、素因数

リポジトリ ※自然数の範囲で考えるものとする 確率的素数判定とかは気が向いたら 素数(prime number) 自分自身と1以外の自然数で割り切れない(正の約数をちょうど2つもつ)自然数のこと。 合成数(Composite number) 素数でない2以上の整数(素数の積で表すこ…

区間スケジューリング問題

区間スケジューリング問題(プログラミングコンテストチャレンジブック p43) N個の仕事がある。各仕事は、時間に始まり、時間[t_i]に終わる。仕事に参加するなら、その仕事のはじめから終わりまで参加しなければならない。参加する仕事の時間帯が重なってはい…

部分和問題

部分和問題(プログラミングコンテストチャレンジブック p34の設定) 整数の中からいくつか選び、その和をちょうどkにすることができるならYes、できないならNoを出力。 制約 アルゴリズム 部分和問題(プログラミングコンテストチャレンジブック p34にあるよう…