某大学の某先生が「妻夫木夫妻」→「DCT-I」とつぶやいたのをパクってにインスパイアされて、DCT全８種の違いについて解説することを思い立ちました。K先生、ありがとうございます。m(_ _)m

みなさん、↓のサイトをご存知でしょうか？？。一般のQ&Aサイトだとグチャグチャでなんのこっちゃわからなくなりがちな数式を、大学の教科書みたく美すぃーく表示して質問・解答できるサイトです。 http://nazolab.net/ 実はこれ↑、数ヶ月に久留米高専の後輩…

NビットのうちM個が'1'となる符号を考えましょう。このような符号の列挙を『数え上げ符号』といいます。研究でこれが必要になったのだけど、実装例がやたら少なくて少々困ってもうた。少ない資料を基にエンコード・デコードを書いたので貼っておきます。どう…

GCJのRound1（前回は所謂Round0ｗ）。Round1にはA,B,Cの３つがあって、そのうちどれかの上位1000人に入ればラウンド２進出。仮にAがダメでもB、BがダメでもCに参加でき、通過した以降の試合への参加はできない。まー要するに3000人がラウンド２に行けると。 …

初参加です。競技系のコンテストは２年ぶり。前はガッツリICPCとか少〜しTopCoderとかしてたくらい。 Dashboard - Qualification Round 2010 - Google Code Jam 予選参加のためのエントリー資格検定試験みたいなやつ（笑）なので、レベルはそんなに高くない…

おっ久しぶりです。最近全然ブログ書いてませんでしたね（汗）。今日は頑張って書いてみましたっ！。 先週のゼミ発表にて先生から「簡潔データ構造についてもっと詳しく説明してくれ」と言われたので、その前哨戦？としてそれに関するエントリを書いてみます…

プログラミングの授業で『関数の再帰呼び出し』を習うと思う。実例で言うと、先生が↓なコードを示した上で「こういう関数を作れば階乗(n!)が計算できます」と説明する。 int fact(int n) { if(n==0) return 1; return n*fact(n-1); } しかし学生は↓なコード…

考えられる全てのパターンを検証することで答えを導く手法を全探索・総当り探索(full search, exhaustive search)と言う。数ある探索手法の中で、最も素直（そして愚直）なやり方である。 RPGで言えば、全探索は「素手攻撃」に似ている。与えるダメージは確…

【id:wosugi-research:20090710】に書いたが、最小全域木を求めるアルゴリズムはとても有名なのに、全域木の列挙に関する情報はあまりないように思う。ちょうどそんなコードが必要になったので、簡単な考察をしてみる。 あるグラフ（頂点数V・辺数E）の全域…

例えば日本みたいにたくさんの島があって、それら全ての島を車で往来できるように橋をかけたい。ただし、島A→島B→島C→島Aみたいにループするようには橋をかけないものとする。このような橋の作り方をグラフ理論では全域木(spanning tree)と呼び、特にその橋…

例えば 0・1・2・3 を適当に並べ替えてできる「2 3 0 1」とか「3 0 2 1」とかを順列といいます。この順列を全て列挙したいときは、STL の next_permutation() を使うと簡単です。これは順列の 昇べきの順〜降べきの順 までを順番にはじき出してくれます。便…

Suffix Array を使った、ちょっとした実験をしてみたので、今日のゼミでそれを披露する予定だったのですが、ゼミが延期に。あぼーん↓↓。 構築が STL の sort() なので結構時間かかりますね。たぶん O(N^2 logN) になるのかな？。O(NlogN) とか O(N) とかが最…

オレは高専時代にプログラミングコンテストにハマってて、よく後輩たちにアルゴリズム講義をしていた。今だったらこうやって説明するぜ！っていう話を少し書いてみる。断わっておくけど、あまり自分は知的レベルは高くはないので、同等の知的レベルの人向け…