[0, x)の整数に一様分布する疑似乱数を生成するとき，区間すべての整数を得るには何回ぐらい試行すればいいんですか？

わかんないヽ(°▽、°)ﾉ←

数学が出来る人は既に予想できると思うんですが，
なにぶん，自分は全く数学ができないので・・・←
シミュレーションを行うプログラムを作成し，
おおよその数を得ることにしました．

以下，結果から得られた図です．
両対数のグラフで，横軸がx，縦軸が試行回数を表しています．
xは10, 100, 1000, 10000, 100000, 1000000, 10000000で
各10回ずつシミュレーションを行いました．
プロットされているのはその平均です．
擬似乱数生成器はmt19937を使いました．
点線はgnuplotのfit（設定はデフォルト）により得られたもの．

線形．なんていうかほぼ線形関係みたいですね．
なるほど・・・．← 全然わかっていない
だいたいxの10倍の数だけ乱数を生成すれば，区間すべての整数が得られるみたいです．

重複組み合わせなどを用いて考えると10倍すれば，
まぁ，得られるんじゃね？ってことは想像できるんですが・・・ orz
例えば，n種類ある整数をm個取り出す(重複組合せの数)をnHmとすれば，
m個取り出す内，各種類必ず1つ以上選択したときの重複組合せの数はnHm-nになる．
また，nHm-n/nHmってmを大きくするとだんたん1に近づくじゃないですか．←
この値が1に近いほどそのm個取り出したときに各整数が少なくとも1つ以上含まれている
組み合わせの割合が大きくなると考えられます．
分子に注目するとnHm-nとなっていますが，m>>nになるとだんだんと
nを無視できるようになります．
このことから，ｍがnの10倍らへんで値が大幅に上昇するんじゃないかなと思います．

うん．自分の数学力ではここまでです．(´・ω・｀)
数学ができる方，教えて下さい．←

// 以下　2012年12月19日追記
おうふ

この問題はクーポン収集問題っていうらしいですね．
大学生にもなって知らないとかまじわろす・・・．
っで，全部の整数が少なくとも1回は選択されるまでの回数の期待値なんか簡単に求まるみたいですね．ちょっと詳しく書くと，0からx-1までの整数において少なくとも1回選択されている整数の数の各状態を考え，その状態に要する選択回数の期待値を足せばいいそうです．これにもたどり着けないとかまじ俺の数学力わろす・・・．具体的には，今回の問題設定の場合には期待値nは以下の式により求まります．

また近似式[1]が良い感じらしいです．ここでγはオイラーの定数（約0.5772）です．
期待値を求めてみたところ以下のようになりました．

Σ(ﾟДﾟ；)
凄い見にくいんですが，実験で得られた値と期待値はおおよそ同じ値（なんだそれ）をとっています．なるほどでした．


[1] 岩沢宏和，続確率パズルの迷宮 確率クイズ，数学セミナー，Vol.51，No.6，pp.50-55，2012．

int型の変数においてbitが立っている数に関して降順にソートする

#include <iostream>
#include <algorithm>
#include <array>
#include <bitset>

int main()
{
    std::array<int, 10> arr;
    std::generate(arr.begin(), arr.end(), []{static int index; return index++;});

    std::cout << "before: ";
    std::for_each(arr.begin(), arr.end(), [](int value){ std::cout << std::bitset<4>(value) << " "; });
    std::cout << std::endl;

    std::sort(arr.begin(), arr.end(), [](const int &l, const int &r){ return __builtin_popcount(l) > __builtin_popcount(r); });

    std::cout << "after : ";
    std::for_each(arr.begin(), arr.end(), [](int value){ std::cout << std::bitset<4>(value) << " "; });
    std::cout << std::endl;

    return 0;
}

/* Output
before: 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001
after : 0111 0011 0101 0110 1001 0001 0010 0100 1000 0000
*/

どうでもいいソース．(；´∀｀)

数学と将棋がわからない人が5五将棋の最大分岐数を求めるとこうなった

Twitterでmath26さんが以下のようなツイートをされていて
わたし、木になります！(*´∀｀*)教えて、ホータロー

問題：５五将棋の最大分岐数（ある局面で可能な指し手の数の最大値）を求めよ。（値が推測できてもそれが最大値である証明を書くのが意外と面倒かも）

— math26さん (@math26) 11月 28, 2012

分岐数は合法手の数と考えられるので，
ようは5五将棋で合法手は最大何手なのかっていう問題だと思います．
まずはホワイトボードを使って考えてみました．
すると，以下のことに気が付きました

• 相手は玉だけが一番都合がよさそう・・・
• 持ち駒はそれぞれ1種類ずつ持っていたほうがいい
• 駒を盤上に置くと打つ場所が１つ減るので，持ち駒は最大5種類であるから全体として最大で5つの合法手がなくなる

こんなことに注意しながら考えると次のような局面が得られました．

自分，打ち歩詰めに関しての知識が乏しいのですが，たぶんこの局面の分岐数は138です．（案外ある・・・

次に，この問題は玉2枚は必ず盤面上に配置し，また金銀（または成銀）飛車（または龍）角（または馬）をそれぞれ1枚ずつ盤面または駒台に配置し，残りの駒は自分側の駒台に配置した場合に，合法手の数が最大になる局面を見つけるのと同じなんじゃないかと考えました．ただし，当然その局面は相手の玉に対して利きがないものを対象とします．以下そう考えた理由が続きます・・・。

駒台には駒は1種類ずつあったほうが良い理由としては，盤上において１つの駒の合法手の最大数は利きに駒がない状態の3三馬や4三龍などで得られる12です．一方，打つ駒以外が盤面にすべて配置されていたとしても打つ合法手はおよそ14あります．このことから，駒は1種類ずつ自分の駒台にあったほうが良いと考えられます．（こう単純じゃないんかな・・・ orz）

次に歩は盤面に配置しない方がいいと考えました．盤上に配置してしまうと駒を打つ場所が１つ減ってしまいます．したがって，持ち駒の種類の数分たぶん合法手は減ります．一方，歩に関する合法手の数は最大で2です．よって，持ち駒の種類が3以上であれば歩を配置することによって最大分岐数は増加しないと考えられます．また，先に述べたように持ち駒の種類の数が多いほど種類が少ないときの場合と比べて合法手の数は減ることはないと考えられます．このことから，歩は駒台の上にあったほうがよいと考えられます．

相手は玉1枚のみが最大分岐する局面が得られやすいと考えました．これは相手の玉を配置しないで（もはや将棋じゃないけど）考えたときと配置した場合との最大分岐数が同じであれば簡単に示せそうです．なぜなら，そのような状況で相手の玉以外の駒を配置した場合に最大分岐数が増加することはおそらくないと考えられるからです．

以上の考え（仮定？）をもとにプログラムを作成し，合法手が最大となる局面を求めてみました．結果として以下の10局面2局面*が得られました．この局面はすべて合法手がたぶん138あります．（打ち歩詰めがわからない・・・）

今回，歩は自分の駒台に固定しました．また，相手に1枚渡した場合，駒台に置く以外に盤面上にも配置できることから，分岐数が138の局面は20以上あると考えられます・・・．
相手の玉を配置しない場合でも得られた最大分岐数は138でした．

また，歩（またはと）を盤面（または駒台）に配置する条件を追加した場合も同様に最大分岐数は138で，そのとき敵玉を配置しない場合でも最大分岐数は138でした．以下の図は上記で示した局面以外に得られた局面で，上の図の金がとに変わっています．これから，各駒をそれぞれ1枚ずつ任意の盤面のマスに配置（または駒台に配置）した場合における最大分岐数は138であることがわかりました．また各種類の駒を2つ盤面に配置した場合，最大分岐数は増加しないことから，たぶん5五将棋の最大分岐数は138なのではないかと思います．

寝てないこともたぶんあって，文章がスゴイヤバいですが，数学と将棋はわからない自分が求められた5五将棋の最大分岐数は138でした．

*10局面の内8局面は自玉が相手の敵玉の利きにつっこむものが含まれていました．これは反則手だそうです．将棋って奥が深い(・∀・；)　math26さんにご指摘頂きました．ありがとうございます．また，金はとに代えてもいいと助言を頂きました．(2012年12月4日修正)

In 箱根

先週はGPW2012のアルバイトをさせて頂きました．
冷房の中始まったGPW2012（￣□￣；）！！
(不手際で申し訳ございませんでした．orz  いつ暖房から冷房に変わったのか・・・)

あらかた自分は受付にいたので発表はあまり聞けなかったのですが，
モンテカルロ将棋のセッションがあるなど，
昨年とはちょっと違った傾向にあったと思いました．

GPWが終わった後，ちょっと周りを散策．
天気があんまし良くなかったんですが，
紅葉がめっちゃ綺麗でした．(*´ω｀*)

お久にAOJでショートコーディング

久しぶりにAOJでショートコーディングしました．
問題は2000と2408で，比較的簡単な問題・・・．
まだショートコーダーの標的になっていないこともあり，
この記事を書いている時点では一番短いみたい．
頑張ればまだまだ短くなりそう．( ・∀・)ﾉ

bashでスタック領域を解除？する方法

/etc/profile.dにroot権限でulimit.shを作成し

ulimit -s unlimited

と編集し再度ログイン．
ulimit -aで解除できているか確認できる．
もしかしたらchmod +xが必要かも．
cshでは

unlimit stacksize

らしい．
そしてこれはあんまりいい事ではなさそう・・・．

どうでもいいこと

[Desktop Entry]
Name=GoGui
Comment=GoGui
Exec=goguiのパス %f
Terminal=0
Type=Application
Categories=Application

を~/.local/share/applications/gogui.desktopに書いて保存
なんでコマンド指定できないんだっけか・・・

C++を勉強中・・・ orz

std::shared_ptr使っているときにthisポインタを扱いたいときは
std::enable_shared_from_this<クラス名>を継承して，
shared_from_this()を使用して取得する・・・であっているのかな・・・．

#include <iostream>
#include <memory>

class Student : public std::enable_shared_from_this<Student>
{
public:
    Student(std::string name, int first_score, int second_score)
        : name_(name), first_score_(first_score),
          second_score_(second_score) {}
    ~Student() { std::cout << "delete " << name_ << std::endl; }

    void printScore() {
        std::shared_ptr<Student> ptr = shared_from_this();
        std::cout << name_ << " : "
                  << first_score_ + second_score_ << std::endl;
    }
    std::shared_ptr<Student> getSharedPointer() {
        // これだとやばい・・・
        // return  std::shared_ptr<Student>(this);
        return  shared_from_this();
    }
private:
    std::string name_;
    int first_score_, second_score_;
};

int main()
{
    auto student = std::make_shared<Student>("Miyanaga", 5200, 24000);
    auto it = student->getSharedPointer();

    it->printScore();
    sleep(1);

    return 0;
}

Bonanzaが・・・

今週は電通大で第22回世界コンピュータ将棋選手権が開催されてます。
昨日は二次予選がありましたが、なんとBonanzaが敗退となってしまったようです・・・。
一発勝負は厳しいですね・・・。

開発者のインタビューでは学習の対象に探索する深さを入れてるとか
って話があり、そんなのもあるんだと思いました。無知ゴメン

強化学習で深さを考慮したのは知ってるけど、
それと似たようなものなのかな・・・？
(アピール文章見ればいいやないか orz 全然違った・・・へー・・・)

今日は決勝。
どんな棋譜が残るんでしょうか・・・。

棋士対Zen

先日電通大で，棋士と囲碁プログラムZenの対局が行われました．
19路では武宮九段がZenと置き石を5つと4つで
それぞれ対局し，両方共Zenが勝利しました．
置き石4つの19路で棋士相手に勝利するのはおそらく世界初だと思われます．Σ(´∀｀；)すげー

置き石がなくなるのはあっちゅう間かもしれません．
そしたらどうしようかなー．
そんなことを考えさせてくれる対局でした．

棋士とZenの一番の違いとして感じたのは
時間の使いかたでした．
あと印象に残ったのは武宮九段が言われてた
「気持ち悪い」です．
確かに相手が見えないのは気持ち悪いかもしれません．
あと，棋風というかなんと言うか,なかなか人間には見られない
打ち方だったと思います.

それにしても凄かった、そんな一日でした．

２３区踏破してみて

昨日は研究室の先輩の検証実験に参加しました。
実験内容は23区踏破するというもので、
その道のりは研究結果で得られた最短なものだそうです。

初めっから迷惑掛けっけぱなしだったんですが、
なんとか踏破できました。
歩いた距離は大体50kmぐらいで、
たぶん人生の中で一番歩いた一日だったと思います。
使う筋肉がランニングより結構限られている感じがしました。
サイクリングとはそういう点では似てるんですが、
使う筋肉が若干違ったように感じました。

と、とにかく踏破できて良かったです。ヽ(*ﾟдﾟ)ノ

う〜ん 解き方 orz だ<-

を求める・・・

未定係数を用いて

 

とおく．右辺を通分すると右辺の分子は1と等しくなることから，

であるから，これより

が得られる．これを解くと

よって

これを用いると

与式 

ここで

とおくと

であるから

与式

あってないかも<-

ってかこんなに数式って汚くなるもんなのか・・・<-
等号ってこの環境だとどうやって合わすんだろう・・・
あと積分記号もなんか・・・？

らららMeCab

MeCabをC++で使ってみました。
ちょっと品詞のところは強引です<-
なんか任意のIDが割り当てられるみたいなんで、
それを利用すれば少しは強引じゃなくなるのかな・・・<-

下記のソースコードは形態素の品詞が
名詞か動詞であれば出力するようにしてるはず・・・<-
まだ仕様とか確認してない<-

// g++ mecab_test.cc -std=gnu++0x -lmecab

#include <iostream>
#include <string>
#include <memory>
#include <cstring>
#include <mecab.h>

int main(int argc, char **argv) {
  std::string text = "まずはそのふざけた幻想をぶち殺す";
  std::shared_ptr<MeCab::Tagger> tagger(MeCab::createTagger(argc, argv));
  const MeCab::Node *node = tagger->parseToNode(text.c_str());

  std::cout << text << std::endl;

  for (; node; node = node->next) {
    if (strstr(node->feature, "名詞,")  != NULL
        || strstr(node->feature, "動詞,")  != NULL) {
      std::cout << std::string(node->surface, node->length);
    }
  }

  std::cout << std::endl;

  return 0;
}

出力：

まずはそのふざけた幻想をぶち殺す
ふざけた幻想殺す

// 2012年1月14日にちょっと修正<-

今更ですが・・・

大晦日はここにいました．
参加された皆様，お疲れさまでした．

自分は初めてこの場所で
高専時代のクラスメイトと会ったりと
有意義な時間を過ごさせて頂きました．

楽しかったなー・・・ヽ(*ﾟдﾟ)ノ

うがー

全然関係ないんだけど，
かっこ良くないよね・・・これ・・・　orz

Qtで絶賛ちょっとずつ改良中の5五将棋のGUI

どうすればもっとかっこ良くなるんだろうか<-
探索の様子とか表示できるようにしたほうがいいかな・・・( ´Д｀)

QtいいねQt

ってことで，
前に作成した奴がひどかったので，
ちょっと修正してみました．
前よりか若干ましになったかな・・・ヽ(*ﾟдﾟ)ノ<-

Qtで作った5五将棋GUI