はじめに - アルゴリズムとデータ構造大全
はじめに このドキュメントは，主に競技プログラミングで出題される問題を解く際に利用できるアルゴリズムやデータ構造をまとめたものです．特定の問題にはあまりフォーカスしないため，問題を解く際の考察の仕方等の内容はありません．詳しく，正確に，分かりやすく書いていこうと思っています． このドキュメントは執筆途中です． 想定する読者 C++を用いたプログラミングに慣れている方を読者として想定しており，C++言語の仕様や，文法にはあまり触れません．また，計算量という用語についても説明しません．ただし，償却計算量など，計算量の見積もりが複雑なものについては必要に応じて説明します． コードについて このドキュメントで登場するコードは，可読性向上のため，以下のようなコードがファイルの先頭に記述してあることを前提としています．また，適切な問題を用いてコードの検証がなされている場合は，コード周辺にのように，検証
超高速！多倍長整数の計算手法【後編：N! の計算から円周率 100 万桁の挑戦まで】 - Qiita
4-1. N! の高速な計算 $N! = 1 \times 2 \times 3 \times 4 \times \cdots \times N$ を計算してみましょう。 $N!$ は場合の数を求める問題でよく出てきて、こんな感じのものが求まります。 $1, 2, ..., N$ が書かれたトランプのカードが 1 枚ずつあるとき、これを一列に並べる順番は何通りあるか？ 例えば、$N = 13$ の場合 $13! = 6,227,020,800$ 通り、のように計算できます。 また、$N!$ は二項係数 $_NC_K$ を求めるのにも使われます。 $N!$ が求まれば、$_NC_K = N! \div K! \div (N-K)!$ で掛け算・割り算するだけで計算できますね。 $N$ 個の区別できるボールから $K$ 個を選ぶ方法は何通りか？ これが $_NC_K$ になります。例えば、$N
わかりやすい画像のdiffを求めて - Qiita
どうも。フロントエンドエンジニアの @Quramy です。 さて、前回、1日10万枚の画像を検証するためにやったことで書いているとおり、reg-suitという画像に特化した回帰テストツールをメンテしています。 画像回帰テストという文脈において、差分の可視化方法はとても重要なファクターです。なぜなら、画像(=スナップショット)に差分が発生したからといって、それすなわち棄却、というわけではなく、その差分の内容を判断して、意図せぬ変更であれば棄却、意図した変更であればexpectedを更新する必要があります。すなわち、ワークフローに目視による差分のレビューが発生するのです。 そこで、少しだけ異なる2枚の画像について差分を効果的に可視化する、というテーマに向き合ってみました。 主にC++とOpenCVでの実装ですが、これらの知識が無くとも読めるよう、コードやAPIへの言及を少なくして、中間画像で説
PythonでOpenCVに頼らずNumpy+PILで画像処理のフィルタを1から作って理解する - karaage. [からあげ]
画像処理を基礎から学ぶ 私は、カメラが好きなこともあり、画像処理に関しても興味あります。一般的には、RAW現像とかPhotoShopのテクニックなどを身につける人が多いようですが、私の場合は、何故かpythonやOpenCVという便利な画像処理ライブラリを使って画像処理ソフトを自作するところから始めようとしています。 ただ、OpenCVは便利なのですが、便利さがゆえにブラックスボックス的に使ってしまっているのが気になっていました。やっぱり内部で何をしているかわかっていないと、ちょっとAPIに無い処理をしたいときや、問題が発生したときに何をどうすれば良いのか全然分からないですし、OpenCVを使うまでもない処理にOpenCVを使ってしまうのもよろしく無いなと思います。Open CVインストール手間ですし結構時間かかるので（特にRaspberry Piとかだと）。 基礎から理解するには、Ope
![PythonでOpenCVに頼らずNumpy+PILで画像処理のフィルタを1から作って理解する - karaage. [からあげ]](https://cdn-ak-scissors.b.st-hatena.com/image/square/754d90fc67a9ebbd8541fc950f6cfad558a793c1/height=288;version=1;width=512/https%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Fk%2Fkaraage%2F20170724%2F20170724112939.jpg)
マルコフモデル ～概要から原理まで～ （前編） | POSTD
本記事は、元記事を翻訳した記事の前編となります。 B/C/D節については後編をご参照ください。 “マルコフモデルとは何か” という議論は昔からありますが、もし皆さんがその答えを知りたいのであれば、正直なところ、ウィキペディアを見る（または以下のTLDRだけを読む????）ことをお勧めします。一方、マルコフモデルの概要やこのモデルが重要である理由、およびその実装方法に興味があり、サンプルを通じて理解を深めたいという方は、この記事を引き続きご覧ください(^ ^)。以下で、 具体例を挙げて説明します。 TLDR： 確率論 において、マルコフモデルは不規則に変化するシステムを モデル化 するための 確率モデル である。なお、未来の状態は現在の状態のみに左右され、過去に起きた事象には影響されないと仮定する（つまり、 マルコフ性 を仮定する）。 引用元： https://en.wikipedia.or
ベジエ曲線を整数の加減算だけで描画する方法 - Studio RAIN's diary
だいぶ前にちらっと書いたことがあるのだが、かれこれ 20 年ほど前に、ベジエ曲線を整数の加減算だけで描画する方法を考えたことがある。こういう会社員時代の仕事を紹介するためには、いろいろと制約があったりするのだが、このアルゴリズムは多分守秘義務には含まれていないし、技術自体がいい加減時代遅れの技術で、多分今はもっといい方法が開発されているはずなので、公開してもどこからも文句は来ないと思う。だから、機会があればいつか紹介したいと思っていた。 だだ、このアルゴリズムを説明するには、ややこしい数式を並べる必要があって、それが面倒で避けていたところもあった。しかし、今回 Maxima を使って計算したら、わりと簡単に再現できたので、せっかくだから記録にとどめておくことにする。 ベジエ曲線というのは、空間からいくつかの点を選択したときに、その点との関係で定義される。たとえば、２次のベジエ曲線だったら、
一から学ぶベジェ曲線 | POSTD
(編注：SVGアニメーションを元記事にならい追加しました。リクエストありがとうございました。) 皆さんは線分のことをどう表現しますか？ 線分は、端点によって考えられるかもしれません。その端点を P0 、 P1 と呼ぶことにしましょう。 線分を厳密に定義するならば、「 P0 と P1 を結ぶ直線において、 P0 と P1 の間にある全ての点の集合」と言えるかもしれません。これは以下のように表せるでしょう。 便利なことに、上記の定義から、その線分上のどこにある点の座標でも簡単に求めることができます。例えば、中点は L(0.5) にあります。 実は、2点間のどんな値でも、任意の精度で 線形補間する ことが可能です。そのため、時間関数 L(t) の t で線をたどるといった、より複雑なことができるのです。 ここまで来ると、「それが曲線と何の関係があるのか？」と不思議に思うかもしれません。2つの点だ
Bezier Curves from the Ground Up
Bezier Curves from the Ground Up This post is also available in Japanese: 一から学ぶベジェ曲線. How do you describe a straight line segment? We might think about a line segment in terms of its endpoints. Let’s call those endpoints \( P_0 \) and \( P_1 \). P0 P1 To define the line segment rigorously, we might say “the set of all points along the line through \( P_0 \) and \( P_1 \) which lie between \( P_0 \
NTP（Network Time Protocol）とは
◆ NTPとは NTP（Network Time Protocol）は、コンピュータに内蔵されているシステムクロックをネットワークを 介して正しく同期させるためのプロトコル。NTPにより時刻同期を行うことで指定時間に正しくサービス を動作させたり、出力ログを正しく管理できたり、証明書を利用した認証なども正しく行うことができます。 ◆ NTPのパケット NTPクライアントがNTPサーバにアクセスする際、宛先ポート番号としてUDPポート番号123を使用。 NTPクライアントがNTPサーバにアクセスする際の送信元ポート番号も、ポート番号123を使用します。 ◆ NTP - 階層構造 NTPはstratumと呼ばれる階層構造を持っており、最上位のNTPサーバが原子時計やGPSの正確な 時刻源から正しい時刻情報を得て、下位のNTPサーバはそれを参照して時刻同期を行っていきます。 最上位のNTPサーバ
【音付き】15種のソートアルゴリズムの可視化
Youtubeからの転載です。http://www.youtube.com/watch?v=kPRA0W1kECg-----① 選択ソート（Selection Sort）② 挿入ソート（Insertion Sort）③ クイックソート（Quick Sort）④ マージソート（Merge Sort）⑤ ヒープソート（Heap Sort）⑥ 直接基数法による基数ソート（LSD Radix Sort）⑦ 基数交換法による基数ソート（MSD Radix Sort）⑧ イントロソート（Intro Sort）※GCC標準ソート⑨ 適応型反復マージソート（Adaptive Merge Sort）※GCC標準安定ソート⑩ シェルソート（Shell Sort）⑪ バブルソート（Bubble Sort）⑫ シェーカーソート（Cocktail sort / Shaker Sort）⑬ ノームソート（Gnome
ある三角形の頂点のうち、最後の頂点を求める方法 - 株式会社CFlatの明後日スタイルのブログ
今日は小ネタです。 三角形ABCの各頂点の座標が、a, b, c であるものとします。 この三角形ABCのうち、外から渡した座標 d, e のいずれでもない、最後の頂点を求めて下さい。ただし d, e は、必ず a, b, c のうちのいずれかと一致し、また d≠e であるものとします。 答え：a + b + c - d - e 案外、思いつかないものです。 ちなみにこの方法は、a〜e が頂点座標ではなく、頂点配列のインデックスの場合にも利用できます。 似たようなテクニックに、「3つの数字のうち、真ん中の値を求める」のがあります。 template <class T> T middle(const T& a, const T& b, const T& c) { return a + b + c - std::min(a, std::min(b, c)) - std::max(a, std:
多倍精度整数の基礎 ( 四則演算編 ) - Qiita
coe は次数 i ごとの任意の係数, radix は基数. 具体的には std::vector の template 引数に coe を指定し配列の添え字を i とする. 実装 準備 まずクラスに与えられるべき必要な template parameters を確認する. template< class UInt = std::uint16_t, class DoubleUInt = std::uint32_t, class DoubleInt = std::int32_t, DoubleUInt BitNum = sizeof(UInt) * CHAR_BIT > class integer; class UInt = std::uint16_t ここには coe の型を指定する. coe で表現できる最も大きな値 + 1 が radix になる. class DoubleUInt =
コンピュータを進化させてきた偉大なるアルゴリズムまとめ
By Kai Schreiber IT技術の進化のスピードには目を見張るものがありますが、それを支えているのはアルゴリズムと呼ばれる処理方法(技術的アイデア)です。さまざまなアルゴリズムの中でも、コンピュータの進化に革命的な影響をもたらしたとされる偉大なアルゴリズムは以下の通りです。 Great Algorithms that Revolutionized Computing http://en.docsity.com/news/interesting-facts/great-algorithms-revolutionized-computing/ ◆ハフマン符号(圧縮アルゴリズム) Huffman coding(ハフマン符号)は、1951年にデービッド・ハフマン氏によって開発されたアルゴリズム。頻出頻度の大小によって対戦するトーナメントツリーを考えて、ブロックごとに0と1の符号をもたせる
中学生にもわかるウェーブレット行列 - アスペ日記
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
ウェーブレット木の世界
2013/1/9に統数研チャンネルにて、ウェーブレット木の解説をしました。岩波書店より出版されました「高速文字列解析の世界」の解説になっています。
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Learn Contemporary C++ | Concise&Visual Examples
Maze Algorithms
緯度経度であらわされる２点の間の地点を求める式を教えてください Pa：(lat1, lng1) Pb：(lat2, lng2) PaとPbの間のPcを求める式を教えてください。…
速水桃子「パターン認識と機械学習入門」
