Google日本語入力 in Ubuntu10.04
anthyの変換はバカだし，skkは送り仮名をよく間違えてしまうので，Google日本語入力mozcを導入しました．
実は，先週オープンソース版が出た日に学振の書類を書きながら一度導入をしましたが，
そのときはまだ句読点などの設定法が分からなかったので見送りました．
しかし，今週になってguiの設定ツールが公開したそうなのでまた入れ直しました．
さすがは，オープンソース．
sudo -s
wget -q http://download.opensuse.org/repositories/home:/sawaa/xUbuntu_$(lsb_release -s -r)/Release.key -O- | apt-key add -
echo "deb http://download.opensuse.org/repositories/home:/sawaa/xUbuntu_$(lsb_release -s -r) ./" > /etc/apt/sources.list.d/ikoinoba.list
apt-get update
exit
ibus-mozcをインストール
sudo apt-get install ibus-mozc
ibusを使うことにします
sudo update-alternatives --config xinput-ja_JP
で，ibusを選んで再起動．
システム->設定->IBusの設定でインプットメソッドとしてをMozcを追加し，一番上へ．
これで，mozcを利用できるようになりました．
Google Code Jam 2010 Qualification Round
参加しました．
先に言い訳をしておくと，酔った頭で寝起きに解いた上に，
久しぶりのプログラミングだったのでぼろぼろでした．
Google Code Jam
Code Jam Statistics (2016)
ちゃんと問題を読まずに10^8だから32bit-intでいけるギリギリなんだなと思ってたら，
思いっきりあふれて答えがマイナスになり，あせって直しましたが一ヶ所直し忘れwrong answerになりました．
というわけで，76点．
とりあえず解答をみやすく整形したものを載せておく．
本番提出したものは，昔作った入出力用のテンプレートを作ったので読みにくいです．
実行時に標準入出力先を指定しなくて済むので楽なだけ．
6号館自転車探索問題
自転車をどこにとめたか毎回忘れてしまう人がいたので定式化してみた．
簡単のため，1次元で考えることにする．
6号館の玄関は[-1,1]の位置を占めていて，自転車を停めることができるのは[-M,-1]∪[1,M]であるとする．
このとき，t君は原点から出発して移動をし，
自転車の存在する位置x∈[-M,-1]∪[1,M]に到達すれば自転車を発見することができる．
t君が自転車をみつけるまでに移動した道程をL(x)とする．
t君は忘れっぽいので，自転車を停めた位置xについての情報は何ももっていないものとする．
このとき，
ρ=sup_{x∈[-M,-1]∪[1,M]} L(x)/|x|
を最小化するようなアルゴリズム（移動経路）を考えたい．
例えば，0->M->-Mと移動するアルゴリズムの場合，
x=-1のとき最大値ρ=2M+1となる．
Mが小さいときはこれが最適であるが，大きい場合は別のアルゴリズムが最適となる．
どのようなアルゴリズム最適となるか？
ρはMによらない定数でおさえられるはず．
randomizedにすればρの値はさらに小さくできる．
乱数について
プログラムの出力で01の文字列をつくってきたが，
頭に"0."をつけて[0,1]の実数の2進展開と対応付けることを考える．
例えば"10101"は"0.10101"となる．
”1”と”01111111…”は同じ値と対応付けられることが気になるかもしれないが，特に問題はない．
さて，このときプログラムの出力できる数とはどのようなものであるかを考える．
（多倍長精度でメモリが不安になるかもしれないが，任意有限に使えるものとします．）
- 代数的数であれば同様に方程式を解けば出力できる．
- 円周率やオイラー数のようなものでも計算できるので出力できる．
では出力できない数とはどんな数であろうか？
誰か例を示して下さい．
まとまな手段じゃ無理だけど．．．
乱数に対する対角線論法
また，対角線論法で混乱してしまったので復習のためのメモ．
コルモゴロフ複雑は人伝にしか聞いたことがないので，用語などは適当．
適当な0,1の文字列を出力するプログラムを考える．
言語はCでもJavaでもよい．
ただし，Turing-completeで逐次的な出力ができないとまずそう．
（Turing completeが出力に関してどうなっているかよく分からない．純LISPって出力がないけどどうするんだろう．．．）
ただし，プログラムの長さは有限長とする．
このとき，次のようにプログラムは無限長の文字列も出力できることに注意する．
while(true) print "0";
このとき，0,1からなる文字列全体からなる集合を
書くことにし（無限長も含む），
プログラムの出力できる文字列の集合をSと書くことにする．
すると，Sは任意有限長の0,1文字列を含む．
なぜならば，"01100101"を出力したければ，
print "01100101";
とすればよいからである．
0,1文字列のうち，Sに含まれないものを乱数と呼ぶことにする．
任意の有限長文字列はSに含まれるので，乱数は無限の長さをもつ文字列だけからなる集合である．
Rが空集合ではない，すなわち乱数となるものが存在することは次のように言える．
の濃度は連続体濃度であり，
Sの濃度は加算無限であるので，
の濃度のほうが大きいことからRは空ではない．
さらに，このことから，Rの濃度は連続体濃度であり，殆ど全ての文字列は乱数であることがわかる．
また，Rが空でないことは対角線論法からも言うことができる．
プログラムの集合を順番に並べる．すなわち，
を全てのプログラムを並べた列とする．
並べることができることは，全てのプログラムをビット列としてみなし，辞書式順でもいれればいいので明らか．
このとき，プログラムpが出力する文字列をf(p)とし，
文字列sに対し，i番目の文字をと書くことにする．
ただし，sがi未満の長さのときはとする．
さらに，とする．
さて，
なる文字列dについて考える．
このdはどのとも異るので，Sには含まれない．
よって，であるということである．
ここまでが準備．ずいぶん長くなってしまった．
dを出力するプログラムについて考える．
これは，を順に計算していくプログラムをつくればよい．
ところが，dは乱数であるので，これを出力できるプログラムは存在しない．
どこの議論で間違えたのだろうか？
そんなに難しくはないが，混乱して時間をかけてしまった．
プリンターで日本語が出力できない問題
貸与PCでの，研究室のプリンターからの印刷がうまくできなかったのでその修正法のメモ．
設定時には英語の論文を試しに印刷しただけだったので，気づかなかった．
2台設定したのだが，1台はギリシャ文字などの記号だけが出力されず，もう1台は記号は出力されるが漢字やひらがなが出力されない状態であった．
フォントに問題があるのではないかと思い，pdffontsで調べたところ，adobe-japan1へのリンクがないと怒らた．
acroreadではうまく表示できていたのだが，
evinceで開いてみたところ，漢字やひらがなの出力されないプリンターと同じものが表示されたので，とりあえずその表示を直すことに．
調べてみたところ
/usr/share/poppler
にadobe-japan1のフォントへのリンクを貼れば直るとのことだったが，
sudo apt-get install poppler-data
で解決した．
evinceでの表示が直ったので，印刷を試してみると，こちらも直っていた．
2台で挙動が違った理由は不明．印刷時のフォントは誰が管理しているのかよく分からない．
ついでに，貸与PC 設定メモ - yamblogに今回の内容を追加した．
順序統計量
研究中に思いついた問題
[0,1]一様乱数からn個とってきたとき，小さい方からk番目の値はどうなるか？
であるが，答えがあった．
結論としてはベータ分布：Beta(k,n-k+1)になるらしい．
期待値は予想通りk/(n+1)．全ての値が等間隔にならぶ．
どこから出てきた問題かというと，各辺のコストが[0,1]一様乱数であるような完全グラフでMSTを作ったところ，頂点数に依らずコストが1より少し大きい程度の値だったことから．
辺数 n(n-1)/2で下位(n-1)個のコストを足したとすると期待値は(n^2-n)/(n^2-n+1)なので，MSTのコストの期待値はこれ以上．
n->∞で1に収束するのではないかとにらんでいるが，詳細は不明．
