ノルウェーの突撃隊：天下一プログラマーコンテストの紹介

8/1, 8/2と、「天下一プログラマーコンテスト」の本選に行ってました。

こうゆう競技プログラミングは「TopCoder」以外では初めてだったけど、
非常に楽しんで参加することができました。

主催側（KLab株式会社）の話ではどうやら来年度以降も開催する（したい）意向のようなので、
「次はどうしようかな」という人に向けて紹介をしようと思う。

ノルウェーの突撃隊：Dokanの紹介（１）

「Dokan」は、infocraftの荒川氏らが開発したフリーソフトである。
その有用性は、わざわざデバドラを書かなくても（！！）ファイルシステムを作ることができるという点にあり、つまり「FUSE」のWindows版と言える。

今回は、荒川氏の書いた記事を元に簡単な"HELLOWORLD"プログラムを試しに書いてみたので、この場で少し紹介したいと思う。

ノルウェーの突撃隊：フリーソフトの配布

ここから、私の作ったフリーソフトをセットアップファイル形式でダウンロードできます、という告知。
（※リンク先のページが拙い英語で書かれているのは、「世界的に需要のあるフリーソフトを作ってやるぜ」という意気込みの表れ）

こことは別ページで、これまでは主にソースコードを公開していたけど（Developer向け）、セットアップ形式のフリーソフトのダウンロード用のページも作りました（User向け、だけど一応ソースコードも添付してあるヨ）。
今のところ、公開しているのは以下の二つだけだけど、これから研究・開発活動などを通して、有用なソフトウェアを作って豆に公開・アップデートしていこうと思います。
意見・質問・要望などがあれば、どのエントリーでもいいのでコメント欄にお願いします。それが開発意欲の糧となるので。

とりあえず2つのフリーソフトの説明。

・「CV_Doppler」(過去のエントリーで紹介)
静止画像のCG処理とサウンドファイルの音源処理ができるソフト。OPENなCVとかALとかいろいろ使ってます。
CGの方は、いま流行りの顔認識とか、エッジ処理とかです。自分用にリアルタイムの動画用（WEBカメとか）のソフトも作ってるけど、要望があればそっちも公開します。
後者では、音源の位置と速度をいじれます。そうすると例えばドップラー効果がしみゅれーとできます。自分の声が極端に高くなったり低くなったりするのも面白いです。


・「PTest」
入力した数が素数かどうかを判断できる優れものです。
とりあえず”18,446,744,073,709,551,615.0”というPrime Nuber(一応、素数。もはや何と読むのかさえ分からない)を入力したら、結果出力まで自分の環境で２分くらい掛りました。。
それというのもこのプログラムでは素数判定法のアルゴリズムに「試し割り法」を用いているから。初めは「ラビン法」で行こうと思ったんだけど、数式中の「N%M =(-1)」が理解できなく諦めました（余りが－１？N-1ってこと？）。
誰かわかる人は教えてください。


両方とも「read_me」はついているけど、「インストールしたけど動かない」とか「訳が分らない」とか「アルゴリズムについて詳しく知りたい」とかあれば遠慮なく質問を。

以上。

ノルウェーの突撃隊：閾値秘密分散共有法

『閾値秘密分散共有法』についてネットで調べてみたが意外と資料が少なかったので、折角だから分かったことをここに載せておこうと思う｡

『閾値秘密分散共有法』は情報の分散と共有によって情報を保護するためのセキュリティ技術である。
今回は特に『(k,n)閾値秘密分散共有法』について説明する｡
（以下からは『(k,n)閾値秘密分散共有法』のアルゴリズムを実装したソースコードに沿って説明する）

ノルウェーの突撃隊：OpenCV, OpenAL, OpenGL, GLUI

 画像処理 & 音声処理のソフト「CG_Doppler」を作ってみた(Codeとセットアップファイルのダウンロード)｡

とはいっても、自分で『OpenCV』『OpenAL』を使って何かをしてみたいがためだけに書いた自己満足な作品だけど…orz
でも、ちゃんとUI（GLUI）も付けたし、それなりに外に向けたものっぽくはなっていると思う｡
以下からちょっとした「read_me」的な内容を書いていくんだけど、Open{GL,CV,AL,UI}の ライブラリの設定は実はそれなりに面倒くさい。けどこれらに関しては結構色んなサイトで丁寧な説明がなされている（例えば、下記を参照のこと）｡
OpenGL
--「GLUTによる手抜きOpenGL入門」（very famous!）
OpenCV
--http://gihyo.jp/dev/feature/01/opencv
OpenAL
--http://www.memorize-being.net/releases/oal11spec-ja/index.html

---------------------------------
さて、ソフトウェアの説明｡
ソフトウェアの処理内容は大きく分けて二つに分かれている｡
・ひとつは「ImageのCG処理」(主に対応している拡張子; jpg,bmp,png...)
これはUIのテキストボックスで指定したファイルを読み込み、OpenCVでそれを取り込みディスプレイに出力してくれる（言語はCだから、直下以外の場所にあるファイルを指定する時は「\」を[\\]というふうに重ねるのを忘れないこと（Ex. C:\\program\\OpenCV\\lena.jpg））｡ちなみに存在しないファイル名を入れたり何も入力しないと、デフォルトで「lena」を用いる｡
そして、UIにはラジオボタンが備わっており、それを操作することでそのImageにCG処理を施すことが出来る｡

ラジオボタンは全部で以下の4つ｡
[Original] --元画像のまま
[Monotone] --白黒画像にする
[Edge] --エッジ抽出
[FindFace] --顔検出
さらに一番下のテキストボックスからはCG処理した後のImageを保存できる｡拡張子も忘れない｡

・もうひとつは3D-Sound処理機能（OpenAL、利用可能な拡張子は[wav]など）｡音源の位置だとか、移動速度だとかをいじれる｡つまり、ドップラー効果をシミュレートできる｡
最初のテキストボックスは上と同様、ロードするファイル名｡こちらはデフォルトでは「Hello World(何処かの異人さんがひたすら「Hello World」と発声する)」が設定されている｡
そして、スピン付きのテキストボックス（Velocity & Distance）から速度と距離を操作する｡

-----------------------------------------

さて以上がこのソフトの「read_me」である（read_meにプログラムの説明って要らないよね?）｡
まあ直感的に理解できないようなUIでは無いと思うけど、何か疑問があればコメント欄にどうぞ｡
上で行なった処理のひとつひとつは、多分ライブラリーを整えたら15分くらいで誰でも作れるようなものばかりなので、是非CVやALを使ってみるといいと思う（一昔前まで画像の処理プログラムはバグの温床だったのだが、今ではCVでこんな簡単に扱える!…自分もサーブされる側からする側に回れるように懸命に努めなければ）｡

蛇足だけど、GLUIは今回初めて使ってみて、凄く簡単で驚いた｡スクロールバーがないとか大きさが設定できないとか自由度はあまりないけど、これだけ楽にUIを作れるならトレードオフを考えれば結構有用かなと思った｡

TopCoder: SRM434: Division2 :Easy-problem

さて、以前のエントリーにでTopCoderの説明みたいなのをしたけど、今回はきまぐれにTopCoderの問題の解説をしてみようと思う｡
でもあんまり難しいとちゃんと解説できないかもしれないし、第1回目だし、一番簡単な問題でいいかな｡

======   Question ==========
タイトルの回の問題は…
「引数として与えられる二つの配列A, B(長さは一緒)を考えた時、それぞれの要素同士を乗算して、その積を足して、その和が最小となる組み合わせを求め、その和を返せ」
って感じ｡
具体的に例を示すと…
A=[1,4,6,2]
B=[10,4,5,5]
１つずつ要素を掛けて、それを足して、答えが最小になるようにだから…
Answer= 1*10 + 2*5 + 4*5 + 6*4 = 64　

こんな感じの計算をするメソッドを作るのがタスクなんだけど…まあ簡単だよね?
じゃあ、問題の解法を続きで解説します｡

Top Coder

「Top Coder」
--http://www.topcoder.com/

「top coder」とは…
TopCoder社が主催する競技プログラミングコンテスの総称である。
「Single Round Match(SRM)」「Marathon Match」「Bug Race」等の種目からなり、現在世界で最も勢いのある競技プログラミングコンテストの一つである。
TopCoderの各種目に参加すると自分のプログラミングの腕前を表すレーティングと呼ばれる数値が付けられる。特に一定以上のレーティングを持ち、名前が赤で表示されている人物は「レッドコーダー」と呼ばれており、他の参加者から尊敬の眼差しで見られている。なお、日本人でレッドコーダーの称号を持っている人物は10人程度しか存在しない｡
（出展:http://dic.nicovideo.jp/a/topcoder）