-- 基礎から学ぶコンピュータ -- 《第五十九号》
┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓ ┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛ -- 基礎から学ぶコンピュータ -- 《第五十九号》 ┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓┏┓ ┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗┛┗ ┳━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━ ┃コンピュータとデータ┃ ┻━━━━━━━━━━┻ ∈≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡∋ 実数(13) ∈≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡∋ ■ ulp と機械イプシロン ■ ある桁で丸めた時に発生する誤差を「丸め誤差」と言います。10進数の有限 小数を2進数で表すと、そのほとんどが循環小数に
簡単そうで難しい組合せ最適化
簡単そうで難しい組合せ最適化 簡単そうで難しい組合せ最適化 高校生，高専生，大学学部生の皆さん 私たちの研究室では，組合せ最適化（離散最適化）という ものを研究の対象にしています．これは離散数学の問題で すが，私たちの身近なところにも現れています．ここでは 組合せ最適化問題の例を挙げて，その解決に向けた研究に ついて説明いたします 京都大学工学部情報学科 数理工学コース 京都大学大学院情報学研究科 数理工学専攻 離散数理分野 長方形詰め込み問題 最初にパズルのような問題を紹介しましょう．左の図のようにいくつかの長方 形が与えられ，これらを入れ物に重ならないように詰めます．このとき，右の 図のように詰めた結果の高さをできるだけ低くすることがこの問題の目的です． １ ２ ３ ７ ６ ４ ５ ６ ８ ９ ２ ８ ５ ７ ４ ９ １ ３ 与えられた長方形 入れ物 詰めた
平面幾何におけるベクトル演算 » 直線と線分
で求まります（ここで |x×y| は実数に対する絶対値， |x| はベクトルに対する絶対値と「絶対値」の意味が異なっている点に注意してください）。 コーディングは以下の通りです*1： // 点a,bを通る直線と点cとの距離 double distance_l_p(P a, P b, P c) { return abs(cross(b-a, c-a)) / abs(b-a); } 線分と点の距離 今度は線分と点の距離を考えてみましょう。 距離としてどのような値が欲しいのか，というのは問題依存なのですが， ここでは一般的な距離の定義に従って，点から「線分のどこか」への最短距離としてみます。 そうすると，線分 ab に垂直な直線で点 a を通る直線と点 b を通る直線に囲まれた領域（下図の左の赤色領域に相当）にある点であれば， 点から直線 ab への垂線が最短距離になります。 また，点 c がこ
TCO10 Marathon Round 3 - てきとーな日記
Subgraph Isomorphismする問題 暫定8位だけど、おそらくシステムテストで順位が超入れ替わると思われるので安心出来ない 通過できてるといいなぁ 戦略上重要なこと スコアが絶対評価なので、点が稼げるところで一気に稼がないといけない 難しいケースは頑張っても20〜40点とかそれくらいの点数しかとれないのに対し、簡単なケースは300点以上取れる forum情報だと１ケースで2600点とった人までいるとか… このことに終盤で気づいたので、そっからは点数低いのをあげようとするのをやめて、点数高いやつをさらに高くするために頑張った 基本的な方針 基本的には全探索するだけ まず最初に、H(小さい方のグラフ)の頂点の順番を固定し、その順に探索を行う 固定せずに、候補数の少ない点からやったほうがよさそうな気がするが、候補数の計算に時間がかかる、ちょっと先の方に難しい場所があってもそっち方法に
Algebraic DP: 動的計画法を書きやすく
PFI社内セミナー（2012/11/22）で動的計画法の新手法・代数的動的計画法について発表した際の発表資料です。発表の模様はこちら： http://www.ustream.tv/recorded/27196711
ウェーブレット行列の省メモリ構築方法 - アスペ日記
ウェーブレット行列の構築方法について。 前に書いた記事とは違って、「ウェーブレット行列大好き！」って人*1以外が読んでもあんまり益がない記事だということをあらかじめ書いておく。 内容としては、相変わらず中学生以上の知識が必要ということはないけれど。 上の記事で書いたように、ウェーブレット行列は 2進数の基数ソートと同じような感じで構築できる。 で、基数ソートをするには、元の配列と同じだけの領域が必要になる。 だが、ウェーブレット行列のように各段階でのビット列だけが必要であるなら、その領域は必要ない。 ウェーブレット行列でも、ウェーブレット木のノードのようなものを持っておくことで、配列長のオーダーでなく、文字の種類のオーダー（一般的に配列長よりずっと小さい）だけの記憶領域で構築できる。 ぼくのウェーブレット行列ライブラリである wavelet-matrix-cpp や、 id:echizen
DP特集
プログラミングコンテスト勉強会での発表スライド。2012年国内予選出場者向けの、グラフとDPを用いて解く問題の解説
First improvement of fundamental algorithm in 10 years
*Terms of Use: Images for download on the MIT News office website are made available to non-commercial entities, press and the general public under a Creative Commons Attribution Non-Commercial No Derivatives license. You may not alter the images provided, other than to crop them to size. A credit line must be used when reproducing images; if one is not provided below, credit the images to "MIT."
Xorshift 乱数生成アルゴリズムを書いてみた。 - 野良C++erの雑記帳
前回 BarrageLL の乱数について触れたので、今回もその続き。 計算機の応用において、擬似乱数というのは大切です。 なので、世の中には、いろいろな擬似乱数の生成アルゴリズムが存在するわけですが、 今回はその中で比較的新しいアルゴリズム、 xorshift 法の実装を書いてみました。 このアルゴリズムは、詳しくは検索すれば論文が出てくるのでそれを参照してもらうとして、大雑把には 内部状態が小さい。他の有名な乱数生成アルゴリズムである mt19937 が 623*32 bit の内部状態を持つのに対し、 xorshift アルゴリズムの代表的な例である xor128 の内部状態は 128bit のみである。 計算が速い。このアルゴリズムはビットシフトと xor 演算のみで構成されており、かつ条件分岐を含まないため、殆どのアーキテクチャで高速に実行できる。 上記の性質を持つにも関わらず、周
古くて新しい自動迷路生成アルゴリズム|ガジェット通信 GetNews
今回はやねうらおさんのブログ『やねうらお－俺のブログがこんなによっちゃんイカなわけがない』からご寄稿いただきました。 ※すべての画像が表示されない場合は、https://getnews.jp/archives/288113をごらんください。 最近、ゲーム界隈ではプロシージャルテクスチャー生成だとか、プロシージャルマップ生成だとか、手続き的にゲーム上で必要なデータを生成してしまおうというのが流行りであるが、その起源はどこにあるのだろうか。 メガデモでは初期のころから少ないデータでなるべくど派手な演出をするためにプロシージャルな生成は活用されてきたが、ゲームの世界でプロシージャル生成が初めて導入されたのは、もしかするとドルアーガの塔(1984年/ナムコ)の迷路の自動生成かも知れない。 なぜ私が迷路のことを突然思い出したのかと言うと、最近、Twitterで「30年前、父が7年と数ヶ月の歳月をかけ
宮代 隆平 の web ページ（整数計画法メモ）
整数計画法メモ トップページへ戻る 本ページのURLが https://www.tuat.ac.jp/~miya/ipmemo.html から https://web.tuat.ac.jp/~miya/ipmemo.html へ変更になりました． それに応じて，本ページからリンクされているダウンロード可能なファイルについても，URLが変更になっています． はじめに このページには，数理最適化問題，特に整数最適化問題（整数計画問題）をソルバーで解く際に，知っていると役に立つかもしれない情報を雑多に記しています． 数理最適化および整数最適化（整数計画法）は強力な最適化手法の一つなのですが，「実際に解きたい時に日本語の情報があまり無い」と耳にしたのがこのページを作ったきっかけです． おことわり このページに書いてある情報は無保証であり，筆者は一切の責任を持ちません． 自己責任でご利用ください．
平面幾何におけるベクトル演算 » 内積と外積
内積・外積 ベクトルの内積 (inner product, dot product, scalar product) と外積 (outer product, cross product, vector product) という演算を用いると幾何の問題を解く考え方が簡単になります。 幾何学における内積や外積はもともと3次元空間上で定義されるものなので，まずは3次元空間上で幾何学的な内積・外積を導入し， それらが線形代数的なベクトル演算と等価であることを利用し，内積・外積を2次元平面上に拡張（縮小？）します。 3次元空間上において，ベクトルの内積（ドット積）は a⋅b で表され， 以下の式で定義されます： 内積はcosを使って定義されている点と，内積の結果は単一の値＝スカラーになる点に注意してください。 また，ベクトルの外積（クロス積）は a×b で表され， その大きさ |a×b| は で与え
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
第9回「再帰的アルゴリズムの基礎」 - 「アルゴリズムとデータ構造」講義日程
softist.com
shuffling and NRooks constraint preservation
2013 TCO Marathon Round 2 (yowa)
ギークアカデミー：先端を走る技を、ギークに学ぶ
「G番目の数字」の解説
有効なWikiNameではありません - ACM-ICPC Japanese Alumni Group
競技プログラミングでの線型方程式系
