Google Code Jam 2011 - Qualification Round

昨年に続き、２回目の参加でごわす。25点以上取れればRound1に進めます。だいぶ時間かかったけど、今年はなんとかScore:100(Rank:1269)で通過できました(^_^)v。問題等はこちら。

• http://code.google.com/codejam/contest/dashboard?c=975485#

A. Bot Trust

正しくシミュレートするだけ。オーダーの罠とかもなし。スイッチは指定の順番通りに押さなきゃいけないので、片方のロボットは必要であれば待機しておく必要がある。相方が頑張ってる時の時間を蓄積しておいて、自分の番になったら、そこからできるだけ時間を引き出す、みたいな感じの実装にした。

B. Magicka

バグでドハマリした。文字列処理は苦手でごわす。問題自体はやるだけ。この手の問題は英語を正しく理解できるかのほうが不安。。。

C. Candy Splitting

ヒドイ兄と馬鹿な弟の問題。弟の計算法はまさにXOR。要するに、「両者のキャンディー値のXOR和（便宜上そう呼ぶ）が一致」するという条件のもとで、「兄のキャンディー値の総和が最大」となるときのその最大値を答える問題。先の条件が一切成り立たない場合は弟号泣。
最初は「Largeサイズは素直に解けないけど・・・」と思いつつ探索かなーと突撃。途中でもっと賢い方法に路線変更。XORの性質を把握することがポイントかな。例えば、をXOR演算子として、兄のキャンディー値をa,b、弟のキャンディー値をc,dとすると、上記条件は と表せる。で、XORの性質をよく考えてみると、任意の変数は別に符号反転的なものもなしに移項でき、その条件も当然成り立ったまま。なので、上記条件が満たされるかどうかは、実はキャンディー値が与えられた段階で既に決まっているわけである。んでんで、兄のを最大にしたいわけだから、究極的には なわけだけど極悪非道すぎるので（うそっ。サンプルケースが通らないのでｗ）、弟に一番安いキャンディをあげときゃいい、ということになる。
ちょっとした洞察力が求められる面白い問題でした。XORの性質を深く考えるキッカケになったかな。

D. GoroSort

オレ的ベストプロブレム。最初、間違いを送信したけどなんとか挽回できた。
確率論の観点から平均打回数を求めよ、っていう感じの問題。最初そこまで深く考えておらず、「2個交換なら2打（1/2）、3個交換なら3!=6打（1/6）必要だから、実は2個交換を繰り返すのがベストなんじゃないか〜」ってな具合に想像して、そして鮮やかに Incorrect くらいました。だってサンプル通ったんだもん。。。
結局状態遷移の確率はもっと正しく求める必要があることを知り、小さなパターンから帰納的に類推。対象が0個なら0打（交換必要なし）。対象が1個のケースは問題の性質上存在しない。2個なら問題文にあるように2打。3個なら3!=6パターンすべてを列挙して求める。具体的には、3つ全部が整列する確率（1/6）、2つが整列する確率（0/6）、1つが整列する確率（3/6）、全く整列しない確率（2/6）を求める。n個の整列に必要な平均打回数をとすると

と書ける。を使ってを解くと。同じように4個の場合もやってみると・・・あれれ？？・・・になっちゃったよ？？。ってことで、もしかしてなんじゃないかと半信半疑ながらコーディング再開。初期位置が正しい位置でない数をカウントするだけなので、当然超簡単。で、見事Correct!。独立試行でないと面白いふるまいするのねぇ。

むすび

無事に全問正解できたので、２週間後のRound1、頑張ります（昨年はRound2で敗退）。もうちょっと速く解けるようにならんと。。。

非VisualStudio環境でC++/CLIが動かない問題の解決策

まータイトル通りなんですが、同様の現象で困っている方も多いと思いますので、ここにまとめておきます。

TeXで最も美しい転置記号

備忘録です。個人的に最も美しいと思っていた行列やベクトルの転置記号が「\top」と書くと出力されることが分かりました。金谷先生の本とかでも使われていて一目惚れ状態だったんですが、それ以来ずーっと出力の仕方が謎で、ネットでも分かりやすい情報がなく困ってたのですが、今回スッキリしました。よかった。
ちなみにマクロではこういう感じに使ってます。興味ある人は是非お試しあれ♪。

\global\long\def\T#1{#1^{\top}}

使うときは

\T{x}x=1

といった具合に使います。
これまで、“T”という字をサンセリフ体で表示して似せるのを頑張ってたんですが、今回ちゃんとした答えが見つかってよかったです。めでたしめでたし。

Google 英文ライティング

Google 英文ライティング: 英語がどんどん書けるようになる本

一昨日のエントリ【id:wosugi:20110207】で紹介した『英語「なるほど！」ライティング』と同じ著者の本です。病床で読んだ本パート３。（病気のくせにオレ本読み過ぎや・・・）
この本のテーマは「Google検索を駆使してネイティブチェックもどきしながら英文を書こう！」です。Googleのワイルドカード検索を使って（多数決の理論で）正しい前置詞やコロケーションを見つけたり、検索で得られた実例文からその前後に来やすい句を学ぶ、といったテクが実例を用いて説明されています。一般の方々にはあまり馴染みがないと思われるワイルドカード検索も、手順が丁寧に説明されていて親切です。所望の結果を得るためのキーワード入力のコツなどにも結構な紙面を割いています。本の後半は、一昨日紹介した本の内容と似たような事が簡単に書いてあります。
以前からこの手のテクは自分なりに工夫してやってたので、読んだ時の衝撃は「なるほどライティング」に比べると劣りますが、それでもまだ名著です。特に検索サイトが文脈辞書として使えると知らなかった人には目からウロコの本だと思います。また意外と知らなかったテクもあったりして、個人的に良い落ち穂拾いになりました。「なるほどライティング」でもそうだったのですが、この著者の本は文章構造からページの見た目まで、とにかく読みやすいですね。ライティングに関する本が読み辛いとか正直こっちが恥ずかしくなりますが、この著者に関してはそういうことは皆無です。理系・文系の双方から好まれるスタイルではないでしょうか。図も多いのでコンピュータに詳しくない人でも読みやすいと思います。
ところで、この手のウェブ検索による英文チェックのサービスは最近見かけますね。例えば↓とか。

• 英文校正サイト [NativeChecker]

とは言いつつ、自分は結局アルクのサイトしか使ってないですけど。なんか肌に合わないというか。わざと“concentrate into”で検索したときに、候補に“on”が出なかったのがどうにも納得がいかず（笑）。中で何やってるか怖いから、これだったらアルクの実例集から探すほうが安心っていう感じで。

PREP法って所詮はデザインパターンの一つ

プレゼンや小論文ライティングなどの基礎テクニックとして『PREP法』というのがあります。例えば何かの説明の際に、まず自身の主張について述べ、そう主張する理由を述べ、その根拠を事例を用いて示し、最後にもう一度主張を繰り返す、というテクニックのことです。これらの英語「Point（主張）」「Reason（理由）」「Example（事例）」「Point（主張の確認）」の頭文字をとって『PREP法』と呼ばれます。欧米では基本的にこの様式での議論が常識であり英文ライティングのテクとして出てくるほか、日本でも分かりやすい説明手法の代名詞的に扱われてます。昨日のエントリ【id:wosugi:20110207】の本でも、後半はPREP法による段落構成について述べられています。
ただ個人的に、PREP法だけではとてもじゃないが論文（当方工学系です）なんて書けないよなーと思ったりしてます。以前、昨日挙げた本を読んだあと、ひたすらPREP法にこだわって論文を書いたことがありました。すると、とにかく書きづらい。主張→理由→事例→主張（再）の順番で話を展開し続けることがそもそも容易ではない上に、仮にそれで文章を作り上げても全く読み易くなかったのです。それで、自身の主張の設定の仕方が悪いのかと思い、別の角度からの主張に変えてみたり試行錯誤したわけですが、どうもどれも味気ない感じになってしっくり来ず。・・・結局、自分の主張の角度を無理矢理変えないと成り立たない構造はそもそも何かがオカシイはず！と思い、PREPにこだわるのをやめました。
で、この前、『理科系の作文技術』という本を読んでたらですね、ちょうどこのPREP法の話が出てきまして（これも近いうち書評を書きたい）、著者曰く「PREP法は分かりやすいけど、こればかりだと文が単調になりやすい」的なことが書いてあって、いと共感したものです。よくある小論文なんかは「PREP法で答えてね♪」っていうのが大前提のものなので基本的にPREP無双ですが、実際の文構造というのはもっと複雑です。単純に「PREP」の繰り返しで主張をつなげれれば楽なのですが、実際には主張・理由・事例のそれぞれの中にミニ主張・ミニ理由・ミニ事例があったり複雑な再帰構造しているのが一般的なように感じます。これをうまいことPREPヒトカタマリで段落に区切るのは結構な至難の業です。
プログラムの世界でも、効率良くオブジェクト指向プログラミングするためのテンプレ構造としてデザインパターンというのがあります。まだ自分が高校生だった頃、デザインパターンを駆使してプログラミングをしようとして、プログラムの構造が複雑になってしまい可読性が落ちまくったことがありましたが、なんとなくそのときの経験に似ていました。要するに、PREPも文構造のデザインパターンの一つに過ぎないわけですから、それがしっくりハマるときだけ使うべき！ということなんでしょうね。「これは万能な型なんだ！」と信じこんで、現実のものを無理矢理に理想型にハメるのはよくないですね。絶対コケます。
そんなわけで、最近はPREPがスッポリ当てはまる事柄には優先的にPREPを用いて段落を構築し、それでしっくりこないときは全く別の形で書いてます。あ、もちろん、PREP法が基本中の基本の構造であることに異論はないです。

英語「なるほど！」ライティング

英語「なるほど!」ライティング―通じる英文への15ステップ

神書です。実はだいぶ前に読んだ本なのですが、良書にもかかわらず書評を書き忘れていたので、再度読みなおして書評を書きました。以前読んだあとも多くの人に宣伝しましたが、今回読み返してみて・・・やっぱり未だにオススメしたい本ですね。Amazonの高評価は伊達じゃありません。
このライティング本の流れは、まず「良き英文とはどういうものか？」を定義して、「その条件を達成するためのテクニック」を述べる、ひたすらコレに尽きます。その良き英文の定義とやらはとても明瞭で「より少ない語数でより多くの内容を伝える文（語数が同じならより具体性のある情報量の多い文）」としています。そしてこの判断基準をクリアするためのテクとして、例えば「積極的に能動表現を使う（安易に受動表現を使わない）」「できる限り肯定形を使う（notを使わない）」などを挙げています。この説明だけでも、著者らの言いたいことの７割はカバーしてると個人的には思います。終始一貫して「どうすれば文がより引き締まるか？」を追求してるだけです。ひたすらこのスタイルです。間違っても実用表現がズラズラ〜っていう類の本ではありません（そういう部分もややありますが、それはこの本の真髄ではないハズ）。
自分は仕事柄、英語で論文を書くことが多々あるわけですが、この本を読む以前は書いては消し書いては消しを繰り返していました。理由は単純で「こっちの文とこっちの文のどっちがベターなのか分からない」から。暗闇で右往左往する迷える子羊状態だったわけです。なので推敲といえば「あーこの表現使っちゃったから今度はこっち使おう♪」とかいうレベルで、それでも同じような接続詞（的な副詞）が何度も表れ、何度遂行しても自身で満足できるレベルに達せず。。。しかし、これを読んでからは変わりました（なんかTVショッピングみたいになってきたなｗ）。どちらの英文がよりベターなのか判断できるようになったので、推敲は機能するようになり、接続詞（副詞）の乱用が減り、論文はよりタイトになり、執筆時間も短くなり、なんといっても自信を持って英文を書くようになりました。
一点だけ、本の後半のPREP法のところだけ個人的に思うところがあるのですが、これはまた別のエントリで述べることにします。PREP法そのものはエッセイライティング手法の基礎中の基礎ですので、知っておいて損はないです。TOEFLなんかもPREP法前提で出題してるはずですし。
研究室にコレが一冊あるだけで英語論文執筆で救われる理系大学院生は多いはずです。先生の小言や添削も減るかと思います。ぜひあなたの研究室にも一冊！（笑）。

これなら分かる最適化数学 基礎原理から計算手法まで

これなら分かる最適化数学―基礎原理から計算手法まで

コンピュータービジョン分野で理論屋の最高峰の一人である（と個人的に崇拝している）金谷先生が書かれた本です。金谷先生といえば英語巧者としても有名ですが、それに加えて実は中国語もお上手です*1。
この本のテーマは「最適解（or局所解）を求める手法を体系的に学ぶ」こと。曲線の極値の話から最小二乗法や最尤推定に発展し、線形計画法や動的計画法までカバーしています。本全体にピラミッドを積んでいくような一貫性があり、初学者にとっても非常に読みやすいと思います。金谷先生の本は数式を用いて明快に理由を述べるという特徴がありますが、そのおかげでイマイチ違いが分からない手法の差が明確になってます。ニュートン法や共役勾配法などの反復計算の方針の違いについて、こんなに明快な説明は今まで見たことがないです。これだけでも必読レベル。
逆にちょっと分かりづらかった点といえば、線形計画法と動的計画法でしょうか。これらの手法は、似たようなことの繰り返しで、手順がどうしても煩雑になりがちですが、それをTeX主体で書かれるとどうにも見づらいです。特に動的計画法は、導入時には数式を排除した説明のほうが理解しやすい印象があります。「部分問題の解を組み合わせて、より大きな部分問題の解を得られるときに使える方法」というところからスタートしたほうが分かりやすい気がしました。
本のレベル的には「学部生ならこれくらい分かってよね？」と言いたいところですが、現実にこのレベルの数学をちゃんと理解している学部生がどの程度いるだろうか・・・という感じで、いやむしろ修士学生でも怪しげな人も多々。。。まぁともかく、学部のうちにこれを理解しよう！と思って手にするのがいいんじゃないかと思います。高専専攻科にもピッタリのレベルです。
というわけで、病床で読んだ本の書評その２でした。ゼミのテキストとして超オススメ。

*1:数年前のPRMUでいきなり中国語で質疑した始めたのが衝撃的で、未だに忘れません。・・・まぁ思い出話はいっか(^^;)。