動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita
0. はじめに: 非常に素敵な DP の入門コンテンツ 待ちに待ったコンテストの到来です！！！！！ DP (動的計画法) はアルゴリズムの登竜門というべき難所ですが、いくつか問題を解いて行くとパターンのようなものが見えて来ます。まさに「習うより慣れろ」の世界で、たくさん問題を解いて行くうちに、DP な問題の解法を一言で言えるようになって来ます。 典型を学ぶ方法論として、その最も典型的なシンプルな形をした問題をそのまま吸収してしまうのは 1 つの有効な方法だと思います。それにふさわしいシンプルな問題たちを集めた DP コンテストが先日開かれました。DP 以外にもこういうのが欲しい気持ちになりますね。 Educational DP Contest / DP まとめコンテスト 全部で A 問題から Z 問題まで 26 問あります。今回はこれらの問題に対し 簡単なコメントや解説、その他の解説へのリ
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で良い成績を残すにはひたすら問題を解く練習をするしかありません。 ですが，出題される問題の多くはいくつかのカテゴリ，例えば探索問題やグラフ問題，あるいは幾何問題などに分類することができます。 つまり，「傾向と対策」が存在します。 本サ
動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる - じじいのプログラミング
この記事は、Competitive Programming Advent Calendar Div2013（http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83）の8日目の記事です。 動的計画法(Dynamic Programming, DP)についての記事です。 12/9 前編にサンプルプログラム（http://ideone.com/2B7f4v）を追加しました 12/11 前編の図２つを差し替えました。 はじめに まずは、本やネットの資料で、動的計画法についてのすばらしい解説はいろいろありますので、まずはそれらを参考に。 プログラミングコンテストでの動的計画法 http://www.slideshare.net/iwiwi/ss-3578511 最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メ
完備辞書（簡潔ビットベクトル）の解説 - アスペ日記
以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。 LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。 また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。 この「簡潔ビットベクトル」「完備辞書」は、同じものを指しています*1。 今回は、このデータ構造*2について書いてみます。 完備辞書でできること ビット列に対する定数時間の rank と selectです*3。 rank()は、「ビット列の先頭から位置 k までに、1 のビットがいくつあるか」*4。 select()は、「ビット列の先頭から見て、n 個目の 1 のビットの次の位置はどこか」*5。 それぞれ例を挙げます。
プログラミングコンテストでの動的計画法
KMCの例会講座で用いたスライドを一部編集したものです。 ビット演算を組み合わせたトリッキーな方法で様々な操作を高速に行う方法を紹介します。
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
PNG軽量化の減色と圧縮について | GREE Engineering
このテーブルの番号は 1 Byte になっているため、0-255 の 256 個しか登録できません。そのため、画像で使用されている色が 256 個より多い場合は、なんとかして 256 個にしなくてはいけません。 この「なんとかして 256 色にする」というのが減色処理で、なるべく元の画像からの変化を分からないようにしながら色を減らしていくためのアルゴリズム実装です。（この記事では減色アルゴリズムについての説明は省略します。） テーブルを作成したら、画像のそれぞれのピクセルを RGB 形式からテーブルの何番目の色を使うかに置き換えます。 上図のように、1 ピクセルあたり 24bit 必要だった画像が 1 ピクセルあたり 8bit になったので、データサイズは大体 1/3 になります。 （パレットのデータに最大 3 Byte * 256 = 768 Byte 必要とか、同じように圧縮されないと
中学生にもわかるウェーブレット行列 - アスペ日記
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
第7回 多対多の関係を賢く扱う
100×100の格子上に四角形が32個あります（図1）＊1。ある四角形を新たに格子の上に置いたときに，元からある四角形のうち，これに重なるものの番号を示してください。ただし，この問題で扱うすべての四角形のX，Y座標は，0から100までの整数値をとることになります。 私は待ち合わせが苦手です。人の顔を覚えるのがまったく不得意で，ましてや多くの人の中から見つけ出すとなるともうパニックになってしまうからです。そういうときに限って携帯電話を忘れていたりして…。 「多量のデータの中から条件に合致するものを探索する」ことは本当に大変です。一番の問題は，時間がかかるところでしょう。1対多で検索する場合はともかく，多対多で探索するときには，アルゴリズムの優劣がモノをいいます。今回はその一例として「四角形の重なり具合を調べる方法」を取り上げ，ここからアルゴリズムの工夫の仕方について紹介します。 今回紹介する
実践的な衝突判定(AABB編) - 結果だけでなく過程も見てください
自作ゲームに組み込んでいる衝突判定について、整理も兼ねてご紹介します。 説明を簡単にするために2D空間で説明します。 バウンディングボリューム バウンディングボリュームについては、容易に判定可能で実用的ということで 各軸に平行な四角形(以下の図のようなの)を採用します。 このような四角形のことをAABB(axis-aligned bounding box)と言います。 AABBのデータ構造 色々考えられますが、 最小座標とそれぞれの辺の長さ 中心座標とそれぞれの辺の半分の長さ 最小座標と最大座標 ここでは1.を採用します。 データ構造は以下のようになります。 struct AABB { POINT min_; SIZE size_; }; 図にすると以下のようになります。 静止しているAABB同士の衝突判定 上の図でobj1とobj2が衝突する条件を文章で書くと以下のようになります。 ob
いもす法 - いもす研 (imos laboratory)
いもす法とは，累積和のアルゴリズムを多次元，多次数に拡張したものです．競技プログラミングでは 2 次元 1 次のものまでしか出題されませんが，2012 年の研究成果としてこれをより高次元の空間により高次数のいもす法を適用することにより信号処理分野・画像処理分野において利便性があることがわかっています． いもす法の基本: 1 次元 0 次いもす法 最もシンプルな「いもす法」は 1 次元上に 0 次関数（矩形関数や階段関数などのように上部が平らな関数）を足すものです． 問題例 あなたは喫茶店を経営しています．あなたの喫茶店を訪れたそれぞれのお客さん i\ (0 \leq i \lt C) について入店時刻 S_i と出店時刻 E_i が与えられます（0 \leq S_i \lt E_i \leq T）．同時刻にお店にいた客の数の最大値 M はいくつでしょうか．ただし，同時刻に出店と入店がある場
へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
第1回 幅優先探索の基本
皆さんは、アルゴリズムと聞いて、何を思い浮かべますか？ 多くの人は「プログラミングの基礎技術で、学ぶべきもの」という認識を持っていて、実際に書籍などで学習したことのある人も多いでしょう。しかし、一方で「実際にプログラミングを行う上では何に役立つかよくわからない」とも感じているのではないでしょうか？ 例えば、アルゴリズムの書籍では様々なソートアルゴリズムが紹介されていますが、一つ覚えてしまえば実用上困らないでしょうし、そもそも大抵の言語にソート関数は標準で用意されています。最短経路問題を解くことができるダイクストラ法は非常に有名なアルゴリズムですが、実際に自分のプログラムで使ったことがある人はほとんどいないのではないでしょうか？ そういった、使いどころが見いだせない「アルゴリズム」を、具体的な問題に対して適用していく際の考え方を紹介しようというのが、この特別連載です。ここでは数あるアルゴリズ
木メモ - Negative/Positive Thinking
はじめに 立派な庭師になるために、木についてちょっと調べてみたので、まとめておく。 木(構造)とは 閉路を含まない無向グラフを「森」という 連結な森を「木」という 与えられた頂点が全てつながっていて、閉路を含んでいない 閉路を含まない有向グラフは「DAG(Directed acyclic graph)」という ある頂点を根(Root)としてもつ木を「根付き木」という 2点v,wが辺を持ち、vの方が根に近い場合、vを「親」、wを「子」という 2点v,wについて、根とvとの経路にwが存在する場合、wはvの「先祖」、vはwの「子孫」という 子を持たない頂点を「葉」という 根から各点への経路の長さ(1辺を1とする)を「高さ」という 各点の子の数が常にn子の木を「n分木」という 連結グラフGについて、閉路ができなくなるまで辺を除去し続けると、残ったものは「全域木」となる 根付き木を探索などに用いるこ
プログラミングコンテストでの乱択アルゴリズム
前編 (平衡二分探索木編) はこちら http://www.slideshare.net/iwiwi/2-12188757
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
IME本でも紹介されているLOUDSのパワーアップ版、DFUDSを調べた - EchizenBlog-Zwei
「日本語入力を支える技術(IME本)」で紹介されたことで一躍市民権を得た感のあるLOUDS(Level Order Unary Degree Sequence)。LOUDSとは木の簡潔データ構造で、小さいデータサイズで木が実現できるので日本語入力の辞書引きに使うトライ木をLOUDSで実装すると効率が良い。 さて、そんなLOUDSにはパワーアップ版ともいうべきDFUDS(Depth First Unary Degree Sequence)というデータ構造がある。DFUDSはLOUDSが定数時間で扱える操作(parent(親ノードの位置を得る), i-th child(i番目の子ノードの位置を得る), degree(子ノード数を得る))に加えてsubtree size(現在のノードを根とする部分木のノード数を得る)という操作が定数時間で実現できる。よってDFUDSを使うと、トライでpredic
アルゴリズム論 - 坂本直志 東京電機大学工学部情報通信工学科
講義資料 第 1 回 Turing 機械 第 2 回 Turing 機械のプログラミング 第 3 回 計算量理論 第 4 回 万能 Turing 機械 第 5 回 停止問題 第 6 回 線形加速定理、階層定理(2003.5.27 改訂、2003.6.3 三訂) 第 7 回 下限 第 8 回 非決定性(1),オートマトン 第 9 回 非決定性(2)、完全問題 第 10 回 NP完全問題 レポート 同じ問題を解く計算量の異なる二つのプログラムを書き、計算量を評価しなさい。 締切 2003 年 7 月 8 日 参考文献 坂本直志 <sakamoto@c.dendai.ac.jp> 東京電機大学工学部情報通信工学科
プログラム・プロムナード
会誌「情報処理」連載の「プログラム・プロムナード」（2002年4月〜2005年3月掲載）と「Haskellプログラミング」（2005年4月〜2006年3月掲載）はどなたでもご覧になれます。ファイルはすべてPDF形式です。 「Haskellプログラミング」に掲載されたプログラムは http://www.sampou.org/haskell/ipsj/ から取ることができます.
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
システム・エンジニアの基礎知識