2012年05月03日

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の文字を復元したりできるのだが、それにしたってちょっと難しすぎるだろう。

posted by chiguri at 20:59| Comment(0) | TrackBack(0) | PC

2012年04月26日

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:私の中で、よく使う割に引数の順序が覚えられない代表。

posted by chiguri at 16:58| Comment(0) | TrackBack(0) | PC

2012年04月09日

SML#を使ってみ・・・ようとした。

いや、最終的にはつかえたけれども。


つい先日1.0が出たSML#なるものを私も使ってみようと思ったわけである。

なんとご丁寧なことに、Windows用にはMinGWを使った実装がバイナリで公開されている。

いやはやありがたいことですよ。


で、動かしてみたら・・・

ld.exe : cannot find -lgmp

なんて言って落ちる。

評価してるのは、ただの1。


そもそもldなんてなんで動くのやら?と思い調べてみると、ここに「コンパイラが頑張ってるんだよー」と書いてある。

なるほど、動的にライブラリ作って貼り付けてるわけだ。


で、-lはライブラリの指定として、gmpとはなんぞや・・・と思っていたら、GNU MPだった。

演算用ライブラリ。

mingwのパッケージにももちろんある*1

mingw-getで調べてみると、出てくる出てくる・・・

ここで注意、libgmpはMSYS用とMinGW用がある。

ここで入れないといけないのはMinGW用であって、MSYS用ではない。

前者を入れると、

SML# version 1.0.0 (2012-04-06 17:51:49 JST) for x86-mingw
# 1; (* ここが入力 *)
Creating library file: \sk34./000.lib
val it = 1 : int

とまあ、なんかファイルを作っているところまでばっちり見えて、動きました、とさ。

少しいじりたいけど、SMLはあんまりよく知らないし、SML#独自の機能なんてなおさら・・・

*1:気付かないでソース持ってきてビルドしてたけど。後輩の指摘でようやく気付いた。感謝。

posted by chiguri at 12:13| Comment(0) | TrackBack(0) | PC

2011年12月10日

F-12Cのアップデート・・・

今b-mobileのSIMで使っていて、パケットを使いたくなかったのでDoCoMoショップに行ってみた。

聞いてみたところ、アップデートさせてくれるということで、SIMを持ってきてくれて、相手の目の前でアップデート。

無事できた。よかった。


と思ってたよ今日までは。

なんとb-mobileではテザリング不可に!*1

なぜにそんな修正を?

富士通さん?DoCoMoさん?

一体なにがしたくてそんな制限をかけたんだい?

納得のいく説明をしてくれないかな?

*1:sp-modeのアクセスポイント以外不可。

posted by chiguri at 21:28| Comment(0) | TrackBack(0) | PC

2011年10月31日

F-12CをWin7につなごう

Androidアプリの開発をしたくなったり、ちょっと変なことをしたくなると、ひとまず手元のPCにつなぐ必要が出る。

が、F-12Cの接続は面倒な面倒な・・・

そんな道のりがまっている。


手順は大体こんなところ。

  1. android-SDKをインストールする。
  2. F-12Cのドライバをインストールする。
  3. ベンダーIDを保存する。

1は出来ているものとする。

2はここで、3はここで書いてあるのをWindows7用に直したものである。


ドライバは(先ほどのリンク先でも紹介されているが)富士通のサイトからダウンロードできる。

適当なところへダウンロード、zipなので展開。

そして、おもむろにF-12CをUSBで接続。

すると、何かよくわからないドライバを使い始める。

コンピューターを右クリックし、管理を開く。

左の一覧にデバイスマネージャーがあるのでクリックし、目立つ表示になっているものを探す。

FUJITSUなんとかかんとか、という表示があったらそれを右クリックし、ドライバーソフトウェアの更新。

コンピューター内から探すようにして、さきほどzipを展開したフォルダを指定。

これでドライバーが読み込まれたはず。

読み込まれなかったら・・・運がないのかもしれない。

この説明が致命的にわかりにくい、ということは自覚しているが、面倒なのでフォローはしない。


次に、自分のユーザーのフォルダを開く。たとえばスタートメニューから。

ここに.androidというフォルダができているはずなので開く。

できていなければ一度android-SDKを使ってみる。

この中にadb_usb.iniがある。

開くとなにやら「編集するな、更新するにはandroid update adbを使え」と書いてあるが、使っても動かなかったので無視する。

このファイルの末尾に0x04c5と入力し、保存する。

あとはadbを再起動する。

EclipseだろうがDDMSだろうが、adbをリフレッシュする、というコマンドがあるのでそれを使えばよい。

すると先ほどまで出なかったF-12Cが出るはず。

出なかったら運が(ry

まあ、運の前にF-12C側でデバッグモードが作動してるか確認すること。

設定、アプリケーション、開発、USBデバッグ、とたどればいい。


なんというか、ちょこちょこと面倒だなあ・・・

posted by chiguri at 02:33| Comment(0) | TrackBack(0) | PC