Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2004年07月28日(水) 今月の情報処理

ネタが無い…

いや、ネタが無いのではなくて文章を書くのが遅いというべきか。

まだ一つ書きたいHaskellネタがあったんだけど。

[]プログラム・プロムナード(7月号) プログラム・プロムナード(7月号)を含むブックマーク プログラム・プロムナード(7月号)のブックマークコメント

久々に情報図書館に行ってきたので読んできた。

テスト勉強に行ったついでなので、キーワード拾ったぐらいなのだが。


今月の問題は

m本のコードの長さ(実数)が与えられて、

それらのコードから同じ長さをn本切り取るとき、

切り取れるコードの最長値はいくつか?

(0<=m,n<=1000)


時間が無かったので最後のほうしか読んでないけど、

  • 動的計画法
  • 二分探索
  • ドント方式

の解法が書かれていたようである。

  • 動的計画法

わからん…もうちょっと考えます

  • 二分探索

0から長さの最大値までの間のどこかに切り取れる/切り取れないの

境界があるのだから、二分探索で解ける。

計算量は、切り取れるかどうかの判定はてきとうにやってもO(m)だから、

長さの最大値をlとするとO(mlogl)ぐらいか。

問題無さそうである。

  • ドント方式

これは思いついた人すごいなぁ。

選挙でおなじみの方式である。

最終的に当選候補者が同じ得票数で当選したとして

もっとも死票が少なくなる方法なのであるが、

この問題にも使える。

各コードの長さを政党の得票数と考え、

n人の当選者を出したとき、最後の候補者を選んだときの

値が答えになる。

計算量は、n回最大値を見つけるので、2分木を使うとO(nlogm)か。

馬鹿サーチでもO(mn)なので、大丈夫そうである。

[]今気づいたけど… 今気づいたけど…を含むブックマーク 今気づいたけど…のブックマークコメント

これ、PDFになってるのね…

http://www.ipsj.or.jp/07editj/promenade/index.html

こんなの去年は無かったぞ。

トラックバック - http://d.hatena.ne.jp/tanakh/20040728