Maximum cut - Wikipedia
An example of a maximum cut In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets S and T, such that the number of edges between S and T is as large as possible. Finding such a cut is known as the max-cut problem. The problem can be stated simply as follows. One wants a subset S of the ver
第二版が出ます！プログラミングコンテストチャレンジブック - iwiwiの日記
一昨年 9 月に初版が出て以来「蟻本」の愛称で皆様にご好評頂いていた僕と岩田 (id:wata_orz) と北川の「プログラミングコンテストチャレンジブック」ですが，お陰様で，このたび第二版が出版されます！第二版の発売日は 1/27 の予定です．よろしくお願いします． （初版の紹介記事はこちら） 改訂による追加部分は，以下になります． 4 つの新しいトピック：計算幾何，枝刈り探索，分割統治法，文字列アルゴリズム 練習問題コーナー 発展内容コーナー ページは 50 ページ増となっています． 練習問題コーナー 練習問題コーナーでは，本書で取り上げた各トピックに関連したオンラインジャッジ上の問題を紹介しています．例題を理解するだけでなく，実際に練習問題を自分で解くことで，一層の定着や応用力の増強を図ることができます． 発展内容コーナー 発展内容コーナーでは，難易度や本の性質の都合等で本書で紹介し
高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
algorithm - ソート済み配列をソートしなおすべからず : 404 Blog Not Found
2012年01月08日20:30 カテゴリアルゴリズム百選Math algorithm - ソート済み配列をソートしなおすべからず 珠玉のプログラミング Jon Bentley / 小林健一郎訳 ぐぬぅ。男子ゆえ女子をこじらせようがないとはいえ、風邪が普通にこじれている。 というわけでアルゴリズムのことなどつらつら考えていた。 高速な安定ソートアルゴリズム “TimSort” の解説 : Preferred Research Timsort - Wikipedia, the free encyclopedia 要はソートすべき配列中にすでに存在する秩序を活用するのがtimsortなのだと。 だけどすでにソート済みの配列を活用するなら、こういう方法もありではというわけでentry。 If it ain't broke, don't fix it. ソート済みの配列に要素を加えるなら、要素を加
11011110: Top ten algorithms preprints of 2011
Last year when I rounded up the algorithms preprints on the cs.DS section of the arXiv, there were 643 preprints there. This year, there are 798. So the growth rate is slowing a little, down to around 5/4 from a higher rate of 3/2 from 2008 to 2009, but in absolute numbers cs.DS is still growing significantly. Here is a very personal top 10, in chronological order. The same ground rules as last ti
Sony Japan | 新卒採用｜ソニー株式会社 採用情報 | 新卒採用 | GO FOR IT コードで世界は変えられる
あなたならどう答えますか？ 我こそはと思う方、腕試ししたい方、あなたのちからを世の中に示してみませんか？ 2012年2月6日（予定）にこちらのページで発表される問題を解き、あなたの解答をだれよりも早くネットに公開してください。 詳細は後日、こちらのページにてご案内します。 ソニーは小型化・軽量化といったハードウェアの開発が得意な会社、という印象を持っている方もいるでしょう。 しかし、ソフトウェアやネットワークサービスを通じて、新たなユーザー体験をお客さまに提供することもソニーの重要なミッションです。 ソフトウェアエンジニアが活躍する場は数多くあり、これからも拡大します。 ソニーは、高いソフトウェア開発力を持つエンジニア(ソフトウェアスペシャリスト)を必要としています。 2013年新卒採用では、「ソフトウェアスペシャリスト」向けの選考コースを新設し、ソフトウェアの専門性を発揮できる
第2回採用クイズ | 株式会社アイリッジ
3つの角が全て整数度の三角形で、互いに相似ではないものを考える。 1° / 1° / 178° 1° / 2° / 177° ... 1° / 89° / 90° 2° / 2° / 176° 2° / 3° / 175° ... 60° / 60° / 60° これらの三角形の一番長い辺の長さが1であるとして、xy平面上の1辺の長さがLの正方形の内部（辺を含む）に互いに重ならないように配置することができたとき、Lを可能な限り小さくするような三角形の配置を与えよ。 ＜詳細ルール＞ ■ 2つの三角形が頂点ないし辺のみを共有する場合、その2つの三角形は重なっていないものとする。 ■ 回答は以下のように三角形の3つの頂点A(x1, y1), B(x2, y2), C(x3, y3)のxy座標を半角空白文字で区切って x1 y1 x2 y2 x3 y3 と出力したものとし、
scratch@tc: 中央値を求めるアルゴリズム
基本というか、簡単に考えられるのは、 - ソートしたのち、真ん中の要素を選択する という方法だが、全ての要素をソートしないと答えが得られないというのは少し計算量が大きすぎる。 いろいろ調べてみると、クイックソートのアルゴリズムの発展型で、クイックセレクトなるアルゴリズムがあるらしい。 http://d.hatena.ne.jp/agw/20090505/1241602074 http://d.hatena.ne.jp/agw/20090513/1242290109 要するに、中央値が求まるくらいまでクイックソートを計算し、省略できる計算はしないということのようである。 このときに、クイックソートを計算するにあたり、最初に選択するパーティションの値をできるだけ中央値に近い値を選択するのが、アルゴリズムを高速化するコツであるということが書いてある。 http://d.hatena.ne.jp/
コルメン本、アルゴリズム・イントロダクション: ホットコーナー
ブログ(iiyu.asablo.jpの検索) ホットコーナー内の検索 でもASAHIネット(asahi-net.or.jp)全体の検索です。 検索したい言葉のあとに、空白で区切ってki4s-nkmrを入れるといいかも。 例 中村(show) ki4s-nkmr ウェブ全体の検索 ASAHIネット(http://www.asahi-net.or.jp)のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。 --- http://iiyu.asablo.jp/blog/2009/07/23/4450605 気になったプログラミング本の新刊 で、コルメン本という言葉を出したせいでもないだろうが、「アルゴリズム・ イントロダクション」が売れていました。これ、コルメンという人が書いてい るから、おれ、コルメン本
Monash
~lloyd You may have been redirected here because Monash University closed down the www.cs.monash.edu.au and www.csse.monash.edu.au web-servers in 2014, and the users.monash.edu.au web-server in 2024. You can probably find what you are looking for here [cantab.net/users/mmlist/] (a Cambridge University (cantab) Users web-site), including Publications, Bibliography, Bioinformatics, Algorithms and Da
Video Lectures | Introduction to Algorithms (SMA 5503) | Electrical Engineering and Computer Science | MIT OpenCourseWare
X Exclude words from your search Put - in front of a word you want to leave out. For example, jaguar speed -car Search for an exact match Put a word or phrase inside quotes. For example, "tallest building". Search for wildcards or unknown words Put a * in your word or phrase where you want to leave a placeholder. For example, "largest * in the world". Search within a range of numbers Put .. betwee
Introduction to Algorithmsに関するサイト - nagayoshi3のブログ
「Introduction to Algorithms」は，アルゴリズムについての定番の書籍である． 本書についての情報をまとめられたWebページがある． http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/ 全25回のビデオによる講義もあるので，本書を理解するのに助けになりそうだ．． http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/ テキスト（2nd Edition）
iOSの「マップ」アプリが渋滞状況の表示に対応
グーグルマップが国内での交通状況の表示に対応。 iOSの「マップ」アプリでも、渋滞状況の表示が開始されています。[source: Google Japan Blog ] Android向けではありますが、こちらのわかりやすい動画をどうぞ。 iOSに標準の「マップ」アプリで交通状況をみるには、画面右下のボタンをタップし、「渋滞状況を表示」を選択します。 渋滞状況は首都圏だけでなく、日本全国の一般道・高速が対象。データ収集の仕組み(後述)により、ユーザーの多い都市部の方が精度が高くなるようです。 渋滞の状況はマップアプリにレイヤーとして追加されるため、マップの拡大・縮小も自由に行え、「航空写真」「地図+写真」のフォーマットにも対応しています。 iPadのマップでも同様に渋滞情報を確認することができます。 興味深いのは、道路に設置されているセンサーではなく、スマートフォンの位置情報データを集積し
HALOBET: Situs Judi Online Terdepan, Slot Gacor & Slot88 Terbaik, Login Mudah!
Pemeliharaan Terjadwal: Spinix pada 01-Oct-2024 dari 23:00:00 sampai 31-Dec-2025 23:59:59. Selama waktu ini, Spinix permainan tidak akan tersedia. Kami memohon maaf atas ketidaknyamanan yang mungkin ditimbulkan. Pemeliharaan Terjadwal: Fairbet pada 14-Jan-2025 dari 12:00:00 sampai 01-Jan-2026 00:00:00. Selama waktu ini, Fairbet permainan tidak akan tersedia. Kami memohon maaf atas ketidaknyamanan
Bloom Filter をせこく使って、せこく処理時間を省く - 日記
先日、Bloom Filter を利用して重複部分をフィルタすることで処理を簡潔にする、という記事を書きました。実際、3, 4秒の改善が図れたということも書きました。でも、普通の設計方法では、std::setより遅くなります。ご注意ください。 原因は、２つあります。ハッシュ値の計算 (std::string → size_t) が遅い。ハッシュ関数の個数が多い。std::set は、平衡二分木で実装されています。dblp.xml 内の著者数は、だいたい72万なので木の高さは19くらいになります。一方で、Bloom filter では、false positive probability を1%にするとハッシュ関数の個数は7、0.1%にすると10程度になります。std::setでの「最大19回の分岐処理」と Bloom filter での「いつも10回ハッシュ値計算」だと、totalでみて前
数値演算言語OCTAVEによるプログラム入門 - mamedalove
最新の20件2025-03-20 競馬に関するアンケート 2024-05-10 支持率と勝率の関係とは? 2018-07-17 The Songs Festivals Of Portland, Oregon Music In The City 2018-03-01 KeHa Tickets Usa Headlining Tour 2018-02-13 2010 West Virginia Condition Fair Concerts 2012-11-17 ま女神のページ in English 2010-03-16 TARGET frontier JV 2010-03-11 Microsoft Excel 2015-12-23 コメント/分割コロガシのページ 2015-06-12 リンク集 2015-04-01 大庭和弥 2014-11-11 騎手別詳細分析 2014-07-25 mime
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Lecture 4 - 6.891 Approximation Algorithms
1482F 実践的アルゴリズム特論 (14) 乱択アルゴリズム：乱択による近似
Introduction to Algorithms
準乱数および議事乱数を用いて円周率を求めるFORTRANプログラム