ALGORITHM NOTE こだわり
入力例 3 9 500 300 800 200 100 600 900 700 400 4 3 1000 1000 1000 0 0 出力例 1800 1000 解説 Partition Problem といいます。 [この問題では、本の厚さの制限が緩いので、力任せ(本棚の幅を少しづづ厚くしていき貪欲に解く)で解けたのかもしれませんが、点数から察して、悲しいことに設定ミスか、または意図的に難易度を下げたか、または実行時間の制限を厳しくしているのでしょうか。力任せで解けないのであれば難易度はさらに高くなります。] 出題者が求めた解法は、動的計画法または二分法だと思います。 ここでは、動的計画法でこの Partition Problem を解きます。 Partition Problem とは、n 個の数からなる数列 S = {s1, ..... sn} を k 個の部分に分割するときに、各部分
Persistence
人には様々なこだわりがあります。例えば、本に関することでも「本は読むと汚れるのでカバーを外して読む様にし、カバーはクリアファイルなどにとっておく」や「本は 1巻から並んでいないと気が済まない」など様々はこだわりがあります。 太郎君もその一人で、本はきちんと 1巻から順に並んでいないと気が済まないようです。そんな太郎君はとある小説にはまっています。その小説は全部で n 巻あり、各巻で本の厚さが異なります。太郎君はこの小説が大変気に入ったので、その小説専用の本棚を買おうと思っています。しかし、部屋に大きな本棚を置くとかなり狭くなってしまうので、出来るだけ本棚の幅が小さくなるように工夫しなければなりません。床から天井の高さを測ったところ、どうやら m 段の本棚なら置けることが分かりました。そこで、小説 n 巻をどのように分ければ m 段の本棚の幅を最小に出来るでしょうか?もちろん、各段に納める小
完全理解「3DMark Vantage」（2）グラフィックスエンジン・後
ポストプロセス（Post Process）は，直訳すれば「後処理」だが，3Dグラフィックスでは「レンダリング結果としての2Dフレームに対し，画像処理を行うこと」を指すことが多い。デジタルカメラで撮影した写真に対しては，フォトレタッチソフトなどを用いて色味を補正したり，輪郭を強調したり，赤目修正を行ったりするものだが，3Dグラフィックスにおけるポストプロセスは，この作業とよく似ている。ポストプロセスとは「ピクセルシェーダを使ったレタッチである」といってもいいだろう。 フォトレタッチがそうであるように，ポストプロセスも悪くいえば「インチキ臭いフェイク処理」なのだが，実のところ，昨今の3Dゲームグラフィックスにおいては，このポストプロセスが重大なウェイトを占めている。そして，この流れを受け，3DMark Vantageでもかなりリッチなポストプロセスを実施している。個人的な感想を言わせてもらえば
完全理解「3DMark 11」（前）〜レンダリングエンジンの秘密
西川善司連載 / 完全理解「3DMark 11」（前）〜レンダリングエンジンの秘密 2010年12月7日，業界標準3Dベンチマークシリーズとして知られる，Futuremarkの「3DMark 11」がリリースされた。 「動作には，DirectX 11世代，Shader Model 5.0仕様のGPU環境が必須」という思い切った足切り策は，ベンチマーカーやPCゲームファンに，かなり強いインパクトを与えたのではないだろうか。 動作環境や，無償版や有料版など3つ用意されたエディションの詳細は，別途掲載してある3DMark 11紹介記事を参照してほしい。本稿では，数回に分けて，3DMark 11で使用されている3Dグラフィックス技術にフォーカスし，解説していくことにする。 Futuremarkは，3DMarkの開発コンセプトとして，「現在のPCゲームだけでなく，数年先のPCゲームの負荷形態を想定し
プログラム・プロムナード
会誌「情報処理」連載の「プログラム・プロムナード」（2002年4月〜2005年3月掲載）と「Haskellプログラミング」（2005年4月〜2006年3月掲載）はどなたでもご覧になれます。ファイルはすべてPDF形式です。 「Haskellプログラミング」に掲載されたプログラムは http://www.sampou.org/haskell/ipsj/ から取ることができます.
A*アルゴリズムについて整理 - yasuhisa's blog
辞書を参考にしながら。NAISTのI期辺りでやったはずなんだが、かなりすっ飛んでいる。 デジタル人工知能学事典 [CD-ROM付] 作者: 人工知能学会出版社/メーカー: 共立出版発売日: 2008/05/16メディア: 単行本購入: 1人 クリック: 6回この商品を含むブログ (6件) を見る A*アルゴリズムとは?グラフ探索アルゴリズムの一つ。「開始ノードから現在位置に至るまでのコスト」と「現在位置からゴールまでの推定コスト」の2つのコストを用いてadmissibleな条件(後述)の元でコストが最小であるような経路を効率的に見つけることができるアルゴリズムである。1960年代に開発されたアルゴリズムであるが、50年経った今でもばしばし使われている。 現在いるノードをp、開始ノードからpまでの最小コストをg(p)、pからゴールまでの最小コストをh(p)と書くとすればpを経由して開始ノード
ウェーブレット変換 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "ウェーブレット変換" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2022年2月) ウェーブレット変換（ウェーブレットへんかん、英: wavelet transformation）は、周波数解析の手法の一つ。基底関数として、ウェーブレット関数を用いる。フーリエ変換によって周波数特性を求める際に失われる時間領域の情報を、この変換においては残すことが可能である。フーリエ変換でも窓関数を用いる窓フーリエ変換で時間領域の情報は残せたが、窓幅を周波数に合わせて固定する必要があるため、広い周波数領域の解析には向かなかった。ウェーブレット変換では
diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
ソートアルゴリズムを映像化してみた - jsdo.it - Share JavaScript, HTML5 and CSS
よくあるやつです。ぼんやり眺めてると、とても癒されます。 2014/2/25 追記: 全面的に書き直しました。 // https://github.com/norahiko/sort-visualize var helper = { range: function(min, max) { var res = []; for(var i = min; i < max; i++) { res.push(i); } return res; }, shuffle: function(ary) { for(var i = ary.length - 1; 0 <= i; i--) { var rnd = Math.random() * (i + 1) | 0; helper.swap(ary, i, rnd); } }, swap: function(ary, a, b) { if(a < 0 ||
見事な取捨選択 - 書評 - 数学ガール/乱択アルゴリズム : 404 Blog Not Found
2011年03月09日22:00 カテゴリ書評/画評/品評Math 見事な取捨選択 - 書評 - 数学ガール/乱択アルゴリズム 数学ガール/乱択アルゴリズム 結城浩 著者ご本人より督促が。 弾さん、ツッコミRTもうれしいのですが、書評を書いて下さらんか（半分マジ） RT @dankogai: ミルカミザルカ< @hyuki: 数学セガール／沈黙のアルゴリズムless than a minute ago via Echofon結城浩 hyuki お待たせしました。 「カルキュラスのアリエッティ」でも「算法少女ミルカ☆テトラ」でもありません。本当の第四作です。 本書「数学ガール/乱択アルゴリズム」は、大好評シリーズとなった数学ガール第四作。 404 Blog Not Found:書評 - 数学ガール 404 Blog Not Found:孤独解消型数学入門 - 書評 - 数学ガール/フェルマー
情報オリンピック参加者の皆さんへ - 簡潔なQ
情報オリンピックに参加した皆さんこんにちは。僕はqnighyです。一応すごい人です。 予選で終わってしまった人も、本選で終わってしまった人も、これから合宿に行けるという人もいると思いますが、これ以降も競技プログラミングに精進したい！という人のために、いち競技者としての経験から、ちょっとアドヴァイスを書いていきたいと思います。(僕自身実践できていないものもあります。) いろいろな大会に参加しましょう。 情報オリンピック以外にも、さまざまな競技プログラミングの大会が存在します。その一例を挙げますから、ぜひとも臆せず参加してみてください。 大会に参加したり、練習したりしないと、競技プログラミングの腕は上がらないようです。 SuperCon 東工大と阪大が主催する高校生向けのコンテストです。このコンテストの最大の特徴は、大学のスーパーコンピューターを借りてコンテストを行うということです。 Supe
探索 - Wikipedia
探索（たんさく、英: search）とは、特定の制約条件を満たす物を見つけ出す行動のこと。 何か問題を解くに当たって、有効な解析的な解法を用いることのできない場合は、試行錯誤によって解を得る場合もある。 一部のアルゴリズムは、元々、機械学習と並んで人工知能の分野のアルゴリズムであるが、現在はその他の分野にも応用されている。類義語として検索（英: search）も参照。 探索アルゴリズムとは、大まかに言えば、問題を入力として、考えられるいくつもの解を評価した後、解を返すアルゴリズムである。 まず解くべき問題を状態（英: state）と状態変化（行動、英: action）に分ける。 最初に与えられる状態を初期状態（英: initial state）といい、目的とする状態は最終状態（ゴール、英: final state, goal）と呼ばれる。 初期状態から最終状態に至る、状態及び状態変化の並び
開発メモ: Kyoto Cabinetのロック機構の改善
Kyoto CabinetはIO負荷が高い場合にCPU負荷も高くなりがちだという指摘を受けて、それを解決すべくロック機構を見直したという話。 スロットロック ハッシュテーブルの操作はハッシュバケット毎に完全に独立して実行できるのが強みだ。ハッシュテーブルは計算量が有利なだけでなく、並列性にも優れるということ。実際には下層のファイルIOで実装依存の排他制御が行われることになるが、ハッシュ層だけ見れば理想的な並列性を備えている。ただし、同じバケットに連なるレコード群の操作は互いに依存関係があるので、それらは一括して排他制御してやる必要がある。となると、バケット毎にロックを用意するのが理想だが、実際にはメモリを節約するために、予め決めた数のロックを用意して、ここのロックに複数のバケットを割り当てる構成をとる。リソース空間をスロットに分けるというイメージから、これをスロットロックと呼ぼう。 スロッ
情報科学コース『数理科学特論』ならびに情報科学科３年『応用幾何学』のページ
情報科学コース『数理科学特論』ならびに情報科学科３年『応用幾何学』のページ この講義ではかつて金子研の卒研・院研のテーマとしても取り上げられたこと がある，計算幾何の基本を取り上げます．主に 下記の本の解説とプログラミングの指導を行います． 主な内容は，凸包の計算, 線分交又, 平面の多角形分割, 美術館問題の解法, 領域探索と Kd 木, ボロノイ図, ドロネー３角形分割, ロボットモーションプ ラニングなどです． M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf 著 『Computational Geometry』, 2nd Ed., Springer, 2000. (日本語訳もあります．) 【実際の講義概要と予定】 １０月６日(月)：第１回 凸包の計算． 第１章の内容を紹介します．計算幾何を概観した後，凸包の計算
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
JOI合宿 問題と解説
External Memory - FC2 BLOG パスワード認証
乱択アルゴリズム紹介(Bloom Filter) - Preferred Networks Research & Development
Wavelet transform - Wikipedia
From Network Diagram to Structured Text
How to Implement World Fastest Grep.