ついでにF-12Cのドライバ周りの問題
実は自分のデスクトップでは比較的容易にF-12Cを認識したが、ノートでは全然認識しなかった。
原因不明、意味不明だったのだが、今日ふと検索したところすばらしい記事が出て来た。
それがこれ。
本来なら、USBを刺したらFujitsu HSUSB Deviceが検出されるはずなのだが、どうも環境によってはMass Storage扱いしてくれるらしい。
なんてはた迷惑な。MSが悪いのかFujitsuが悪いのかしらないけど。
HSUSB Deviceが認識されたら普通にFujitsuからダウンロードしたファイルを読ませればいいのだけれど、Mass Storage扱いするともう手に負えない！
が、先ほどの記事の説明によって復活！！
（ここでは解説しない。元情報が詳しいのでそちらを参照すること。）
それによってUSBテザリングが現実味を帯びたわけである。
よかった〜。
F-12CのUSBテザリング
なんだ、F-12CはUSBテザリングは無効化されてなかったのか。*1
というわけで、「PCに刺したままならテザリング可能」ということが今日わかった。
今の回線がまさにそれ。
まだ有効化の完全な内容にはなっていないけれど、とりあえずrootなしでもAuto USB TetheringっていうソフトでUSBテザリングが有効化できる。
（若干不便なところもある。ケーブルを挿したときしか有効化できないし、抜かないと無効化できない。）
使い方は簡単。
USBドライバを認識させて、ケーブルさして、Auto USB Tetheringが有効化するか聞いてくるので有効化して、デバッグモードを切るとWindows側がネットワーク端子だと思ってくれる。
もう通信可能。ほら簡単。
というわけで、今度はそのうちにUSBテザリングそのものを有効にする設定を探したい。
実は以前見つけてた、なんてことはない・・・よな？
*1:こんなこと書いてたら今度のアップデートでつぶされそうだけど。もうアップデートする気ないし。
GCJに参加しているなう その2
Round 1Aについて。
今度はA,B,Cの三問。
前回と同じく、最後だけ解けなかった。
解けた問題だけとりあえず解説。
A
パスワード入力画面で、すでに何文字か打ったが、ある時点で間違ってしまったかもしれない。
これから何文字か削除して再開するか、それとも自分を信じて続けるか、あきらめて最初から打ち直すか、と3つの方法が考えられる。
キーを打ち込む期待値がもっとも少ない場合の期待値を出せ、というもの。
ちなみに、問題ではパスワードの長さ、打ち込んでしまった文字数、打ち込んでしまった各文字で間違えた確率、が与えられ、これ以降はすべて正しいパスワードを打つ仮定となっている。
相変わらずそんなに難しくなく、それぞれの場合で期待値を計算して、最小となるような場合の期待値を出せばいい。
何文字か削除する、というのが若干面倒ではあるけれど、5文字打ち込んで3文字削除する場合は、1,2文字目が正しい場合（削除した場所から再開したらパスワードが通る）とそうでない場合（再開したらパスワードが通らないので再度打ち直し）でそれぞれの確率を元に期待値を出せばいい。
あわてて書いたので（ある文字まで正しいとする）確率表を作ってしまったが、書いた後でいらないことに気づいた。
前から順にやっていけばぜんぜん問題ない。やれやれ。
でもメモリ消費量はたかが知れてるし、計算量も何も変わらないので、そのまま通した。
B
なんかゲームの問題。
いくつかの課題があって、それはある程度以上スターを持っていないと解けないものになっている。
課題はそれぞれ二つのステージがあって、いきなり二つ目からはじめてもいい。
一つ目のステージを初めてクリアするとスターが一つもらえ、二つ目のステージを初めてクリアするとスターが二つもらえる。
一つ目のステージをクリアしてから二つ目のステージをクリアすると、一つずつスターがもらえる。（逆にやっても無駄、一つの課題では二つまでしかスターがもらえない）
それぞれの課題、ステージでクリアに必要なスターの数が決まっているとすると、すべての課題の二つ目のステージをクリアするのに必要な回数は最低何回か、という問題。
ちなみに、どうしてもできない場合は無理、と出す。
冷静に考えるとそんなに難しくなく、次の順に考えればいい。
- 二つ目のステージのうち、クリアできるものがあればクリアする。その課題の一つ目のステージをクリアしていたらスター一つ追加、試行回数一つ追加。そうでなければスター二つ追加。
- 上がなかったら一つ目のステージのうち、クリアできるものを調べて（ただし二つ目のステージをクリアしたりすでに終わった課題をのぞく）、そのどれかをクリアする。ここが一番問題だが、「現時点で一つ目のステージはクリアでき、二つ目のステージがクリアできるのに必要なスターが一番多い」ものを選ぶとよい。
- 一つ目のステージすらクリアできなかったら、どうあがいても無理。
- スターの数が課題数×2になったら試行終了。
二番目がどう考えても面倒くさいが、要するに、「ほかのステージをクリアすればひょっとすると二つ目のステージをいきなりクリアできるかもしれない」という可能性を残すのが目的。
優先的に二つ目のステージをクリアするのは、一つ目のステージを飛ばすため、というものと、どうせいつかクリアしないといけないんだからクリアできるうちにしておく、という二つの戦略に基づく。
ちなみに、largeは多量の「無理」が出て結構あせった。
結果的には正しかったようだが・・・
Cは無理だった。いじればいじるほどSampleどおりにならないという鬼みたいな感じだったが、もう途中であきらめた。
まあ、結果的には600位を切る程度の順位だったのでよしとしよう。
シャツは遠い。
GCJに参加しているなう
GCJ = Google Code Jam。Googleがやってるプログラミングコンテスト。
アカウントはちょこちょこいろんなプログラミングコンテストに登録しているのだが、まともにやったのは今回が始めて。
Qualification roundとRound 1aが終わって、とりあえずRound 2には出られるらしいことが決まった（id: chiguri）。
今のところの問題を少し見直す。
今回はQualification roundについて。
問題はA,B,C,Dの四つだが、Dは解けなかった。
A
Googlereseとかいう謎の言語がGoogleで使われている・・・のかな？（問題文をあんまりまともに読んでない）
簡単に言うと、英文を単純にアルファベット置き換えした言語。
置き換えは1to1、変換逆変換が常に可能。
問題はGooglereseの文章を元の文章に戻せ、というもの。
で、このGooglereseとかいう言語の文字変換表は常に同じらしいのだが、「常に」のさす範囲がいまいちぴんとこなくて悩んでた。
何せ、「与えられる文章は正しい英語ではないかもしれない」とか書かれてるから。
復元する方法ないじゃん！！*1
いや、実はこの問題、Sampleがあり、すべての問題で同じ変換表を使うので、このSampleから表を作ればいいだけなのだ。
で、作ってみたらGooglereseのzに相当する文字だけSampleになかったので、それを探すプログラムを書いて変換表完成。
あとはinputを逐次変換して出力して終了。
さすが予選の予選の最初の問題、簡単だ。
B
Google社員はダンスコンテストがあるのか・・・？
3人の採点者が出場者を0点から10点までで採点するのだが、傾向が似てるから3人の評価は大きくても2点までしか開かない。
最終的な採点結果は3人のうち一番よかった点数。
なお、3人の評価が2点開いたら、それをsurprising scoreと呼ぶ。
で、問題は基準点、出場者全員の3人の評価の合計値、出場者の中でsurprising scoreである人数が与えられて、基準点以上になる人数は最大何人かを出す。
なんで合計値だけ出されるのか、とか気になるけれど、まあよしとしよう。
難しく考えると出場者の採点結果を復元するように探索しないといけないが、もう少し考えると「surprising scoreをとらなくても基準点を超える人」「surprising scoreじゃないと基準点にならない人」「どうしようが無駄な人」の三種類に分けられることがわかる。
合計が3点じゃどんながんばっても基準点3にはとどかない。surprising scoreで0 1 2、そうでなければ1 1 1しかないから。
まあ、こんな風に分類すれば、あとは最初の人たちと、真ん中の人たちのうちsurprising scoreにできる人たちの人数を加えればいい。
後者はmin(真ん中の人数, surprising scoreの人数)なので別に難しくもなんともない。
なお、この問題のSampleにはscoreが0になる例があって、これが適当にやってると間違う部分だったりする。
こんな例出すんだなあ、親切だなあ、と思ってしまった。
C
なんかテレビを使いまわしてるのを見るとむかつくよね？というよくわからない話から始まる問題。
ちなみに問題とその序文はほとんど関係ない。
数字をある桁で二つに分けて、その前後を入れ替えることでできる数字と元の数字をrecycled pairという。
与えられた値A,Bに対してA≦n＜m≦Bとなる(n,m)のうちrecycled pairとなる組の数を出せ、という問題。
で、まあいろいろあるのだが、nとmを全列挙して、nとmがrecycled pairになるかを調べてもいいのだが（smallならそれで通る）、もっと単純に、nを元にmとなる候補を作ればいい。
具体的には、nを桁でrotateしてnより大きくB以下となる値を列挙していけばいい。
多少rotateが遅くてもlargeがこれで余裕。
このとき注意するのは、rotateが周期的になる場合。
特に1212を桁の数だけrotateすると、2121,1212,2121となる。
対応は簡単。周期的なので「自分と同じ値になるまでrotateしてその回数を数える」ので十分。
同じ値が何回でるとか考えなくてもこれで通る。
ちなみに、上の例もSampleに出てくる。
やっぱり親切。
とりあえずQualification roundはこんなもの。
Dは他人のコードを読んで解法を知ったが、解説しづらいので今回はやめておこう。
*1:正しい英語なら、出現頻度などからEの文字を復元したりできるのだが、それにしたってちょっと難しすぎるだろう。
MinGW（MSYS）でmanが見たい
LinuxやMacを使っている人は、C言語のプログラムを書くとき、時々manで関数の内容を調べたりするだろう（引数の順序とか細かい仕様とか）。
私はWindowsユーザーだが、これはほしい。
Cygwinなら入るけどそもそも極力Cygwin入れたくない。
というわけで調べてみる。
MSYSにmsys-manがあるじゃないですか。
mingw-get install msys-manで簡単インストール。
manが使えるようになった！
で終わるならblogに書かない。
試しにfgets*1のmanを引いてみよう。
まず、コマンドラインを起動して、manを実行。
> man fgets
落ちた。特に何も言わずに、Windows側が「cmd.exeが止まったよ」と教えてくれた。
ヲイヲイ、不安定だな。
仕方ないのでbashを経由。
> bash $ man fgets No manual entry for fgets
今度はないって・・・
man pagesは%mingw-folder%\share\manと%msys-folder%\share\manにある。
%mingw-folder%はMinGWをインストールしたフォルダ、%msys-folder%はMSYSをインストールしたフォルダとする。（多くの場合%msys-folder%は%mingw-folder%\msys\1.0である）
それぞれの中身を見ると、これがまたほとんどない。
これがないとmanが使えない。
特にman3。これがCのライブラリ関数なので、ここだけは埋めたい。
仕方ないので（またか）Linuxのman pagesをとってくる。
ちなみにsiteはここ。
ファイルだけならdownloading ..., look hereの部分をクリックして、You can download the latest man-pages tarball hereのhereをクリックすればファイルの一覧が出てくる。
ここから最新のやつをとってくる。
形式はいくつかあるけど、.tar.gzあたりなら多くのファイル展開ソフトが対応しているのでそのあたりがオススメ。
あとは展開して、できたフォルダにあるman3の中身を全部ガッと%mingw-folder%\share\man\man3にコピーする。
後は普通にmanを使えば見える。
本当はコマンド用のman pagesもほしいのだが、なんか入ってないので（仮にあったとしてもオプションが対応しているかあやしいので）入れないことにした。
まあ、これで十分だろう。
*1:私の中で、よく使う割に引数の順序が覚えられない代表。
