オーダーを極める思考法
プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。今回は、計算量のオーダーについて学びながら、TopCoderのMedium問題を考えてみましょう。 プログラムの実行時間 業務としてプログラミングをされている方には釈迦に説法かもしれませんが、プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。そしてこれは、TopCoderなどのコンテストでプログラムを組む際にもよく当てはまります。通常、こうしたことは感覚的に理解している方がほとんどだと思いますが、具体的にどれくらいのループを回すと何秒掛かる、といった基準を持っている人は少ないのではないでしょうか？ 非常に基本的なことですが、プログラムの実行時間に関して再確認しておきたいと思います。 TopCoderの制限に関して TopCoderでは、実行時間およびメモリ使
一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
Welcome To PKU JudgeOnline
Problem Set is the place where you can find large amount of problems from different programming contests.Online Judge System allows you to test your solution for every problem. First of all, read carefully Frequently Asked Questions. Then, choose a problem, solve it and submit your solution. If you want to publish your problems or setup your own online contest, just write us. Peking University ICP
About - Project Euler
About Project Euler What is Project Euler? Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems. The motivation for starting Project Euler, and
Project Euler - PukiWiki
Project Euler † プログラムで解く数学の問題集です。 公式サイト 適当に和訳してます。我こそはと思う人はライセンスを確認した上で自由に書いてください。 ↑
ACM/ICPC国内予選突破の手引き
ACM/ICPCの2008年度の大会日程が公開されています。 国内予選は2008年7月4日，アジア地区予選会津大会は2008年10月25日～27日でホスト校は会津大学です。 参加登録締め切りは2008年6月20日です。 ここではACM/ICPC（ACM国際大学対抗プログラミングコンテスト: ACM International Collegiate Programming Contest）で 国内予選を突破するために必要な情報を載せています。 ACM/ICPC自体については2006年度の横浜大会のWebサイトなどを読んでください。 結局のところ，ACM/ICPCで良い成績を残すにはひたすら問題を解く練習をするしかありません。 ですが，出題される問題の多くはいくつかのカテゴリ，例えば探索問題やグラフ問題，あるいは幾何問題などに分類することができます。 つまり，「傾向と対策」が存在します。 本サ
見直されるべきPHP5の組み込みイテレータ - hnwの日記
PHPには5.0.0以降SPL (Standard PHP Libray)という枠組みが導入されています。これにより、Iteratorインターフェースを実装したクラスのインスタンスであれば、foreach文で配列と同じように取り扱えます。自分でクラスを作るときもIteratorを実装すれば使うのが楽ですし、コードも読みやすくなると思います。 また、PHPに標準で組み込まれているクラスにはIteratorを実装しているものが多数あります。たとえば僕の手元のPHP5.2.9には24個のイテレータがあり、そのうちいくつかは十分に実用的なクラスです。ただ、日本語の資料が少ないせいか、かなり知名度は低いように思います。本記事では4つの便利な組み込みイテレータを紹介します。 SPLのクラスにはデザインパターンの考えが多く含まれています。特に、イテレータを元にイテレータを作るような使い方は、保守性の高い
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
ALGORITHM NOTE
X×Y個のセルから成るグリッド上のスタート地点から出発し、全５種類のパチクリ（生物）を捕まえた状態でゴール地点まで行く最短コストを求める問題です。各パチクリはそれぞれ、火、氷、木、土、水の属性を持ち、火のパチクリは氷のパチクリを捕まえることができ、氷のパチクリは木のパチクリを捕まえることができ、といったように火→氷→木→土→水→火というような属性の関連があります。スタート地点で最初に持つパチクリを１つ選ぶことができます。グリッドのサイズx, y はそれぞれ2以上1000以下で、各属性のパチクリの数はそれぞれ0以上1000以下です（全体の数は5000以下）。 最初に１つのパチクリを選んだ後のパチクリを捕まえる順番は、上記属性の関連の順番になります。例えば最初に火の属性をもつパチクリを持っていれば、氷、木、土、水の属性をもつパチクリを順番に捕まえてゴールに行けばよいので、下図に示すDAG（Di
第4回 UTF-8の冗長なエンコード | gihyo.jp
今回は、文字コードに関連するセキュリティの話題では古参ともいえるUTF-8の冗長なエンコードというテーマについて紹介します。 UTF-8とは UTF-8は、各文字を1～4バイトの可変長で表現するUnicodeの符号化方式のひとつです。 U＋0000からU＋007Fの範囲の文字を0x00から0x7Fの1バイトで表現しているため、US-ASCIIと互換性がある、バイト列の途中からでも文字の先頭バイトを簡単に検出できる、多バイト文字の途中に0x00や0x5C（\）、0x2F（/）などが現れない、などの特徴があります。 UTF-8での文字のビットパターンは表1のようになります。 表1 UTF-8でのビットパターン
本文抽出ライブラリWebstemmerのblog本文抽出用特化スクリプト「blogstemmer」を書いてみた - FutureInsight.info
以前のエントリーで本文抽出ライブラリWebstemmerを使ってみました。 Webstemmerによるブログの本文抽出 - FutureInsight.info Webstemmerは非常に興味深い本文抽出ライブラリなのですが、ニュースサイトなどの複雑な階層構造を持っているサイトの本文抽出に特化しているため、逆にblogのようなシンプルなケースでの本文抽出に用いるには、ちょっとオーバースペックです。 Webstemmer Webstemmer はニュースサイトから記事本文と記事のタイトルをプレインテキスト形式で自動的に抽出するソフトウェアです。サイトのトップページの URL さえ与えれば全自動で解析するため、人手の介入はほとんど必要ありません。 そのあたりのことを考慮して、本文抽出ライブラリWebstemmerのblog本文抽出用特化スクリプト「blogstemmer」を作成してみました。
Geekなぺーじ : Mac OS Xネットワークプログラミング
Mac OS Xでのネットワークプログラミングを勉強しながら、少しずつ公開していくコーナー。 コードを書く前の準備 まず、gccを使える状態にしないといけません。 Mac OS Xを普通にインストールしただけでは開発環境は入りません。 Xcodeを含むMac OS X開発環境はOS DVDなどに入っています。 次に、エディタが必要になります。 標準開発環境であるXcodeを利用して書くことができます。 一方で、UNIXやLinuxなどで一般的なエディタであるmule、emacs、xemacsなどを利用することも可能です。 個人的にはviが好きです。 Cocoa ファイル単体をそのままコピペしてgccでコンパイルできるCUIとして書いているので多少特殊な書き方をしている気がします。 GUIを使う場合はNSRunLoopではなく、NSApplicationMainを使ったりするのでご注意下さい
連載：検索エンジンを作る｜gihyo.jp … 技術評論社
運営元のロゴ Copyright © 2007-2024 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
Toriumi Lab.
2024年3月26日 「情報的健康プロジェクト：アテンションエコノミーの暗翳と『情報的健康』−総合知で創出する健全な言論空間」を慶應義塾大&オンラインで開催されました. https://www.kgri.keio.ac.jp/news-event/156808.html 査読付き論文が出版されました．Chujyo, M., Toriumi, F. "Link-limited bypass rewiring for enhancing the robustness of complex networks". Appl Network Science Vol.9, No.17 (2024). (2024年5月) 査読付き論文が出版されました．Lai, C., Toriumi, F. & Yoshida, M. ”A multilingual analysis of pro Russian m
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Windows Application Compatibility - ForensicsWiki
contest
Sinatra
Hyper Estraier: a full-text search system for communities
正規表現の問題集1（基本編）
はてなアンテナ - ACM/ICPCアンテナ - 情報サイト