Close Menu Navigation
Open Categories Menu プログラミングコンテストの勉強をしないとまずい
- 22 5月, 2011 -
- Google Code Jam, プログラミング -
- Tags :
- 0 Comments
Code Jam 2011が始まったが、Round 1敗退しそう。
Code Jamへの参加は3回目だけど、気づいたらまた翌年のコンテストが来てあたふたすることの繰り返しになっている。一度きっちりプログラミングコンテストの練習をしないと勝てない。
Code Jamの上位ってどのくらい意味があるのだろうか？
プログラミングをする人は多くいるけど、5歳の子供とか90歳の人は職業的にライバルにはなりにくいので、15歳〜65歳くらいまでの50年分を考える。Code Jamに参加する人はたぶん若年層が中心で10年分くらいの幅があるとするのなら、ライバルの1/5が参加していることになる。
Code Jamに参加しそうな年代でもコンテストなんかやらんという人も多くいるだろうから、さらに5倍見積もっておく。日本の下請けSEのようなプログラミングがそもそも趣味とは言えない人はここでは除外しておく。プログラミングに携わる人を全部集めたらもっと多いだろうから。
Round 1を通過する人は3,000人である。これが上位3,000位だとして、その5 x 5倍の75,000人くらいの位置にいるとしていいんじゃないか。世界で上位75,000人と言ったら結構自慢できそうだ。
ただ、にわかには信じがたい数値でもある。世界にこれだけ人口がいて75,000番目までに入るとしたら相当のこと。ただ、潜在的に才能があってもプログラミングに携わらない／携わることのできない人も世界には多いし、上述のようにプログラミングの仕事をしていても入社するまでプログラミングなんてろくにしませんでしたという人よりはモチベーションが高いのは確かである。
Code Jamは英語ゲー
毎度のことなんだけどプログラミングコンテストは英語力勝負のところがある。今年は特に顕著だった。Round 1BのProblem A. RPIの問題を一部抜き出すと
The NCAA tournament committee uses a formula called the RPI (Ratings Percentage Index) to help rank teams. Traditionally, it has been defined as follows:
RPI = 0.25 * WP + 0.50 * OWP + 0.25 * OOWP
WP, OWP, and OOWP are defined for each team as follows:
- WP (Winning Percentage) is the fraction of your games that you have won. In the example schedule, team A has WP = 1, team B has WP = 0, team C has WP = 2/3, and team D has WP = 0.5.
- OWP (Opponents’ Winning Percentage) is the average WP of all your opponents, after first throwing out the games they played against you. For example, if you throw out games played against team D, then team B has WP = 0 and team C has WP = 0.5. Therefore team D has OWP = 0.5 * (0 + 0.5) = 0.25. Similarly, team A has OWP = 0.5, team B has OWP = 0.5, and team C has OWP = 2/3.
- OOWP (Opponents’ Opponents’ Winning Percentage) is the average OWP of all your opponents. OWP is exactly the number computed in the previous step. For example, team A has OOWP = 0.5 * (0.5 + 2/3) = 7/12.
Putting it all together, we see team A has RPI = (0.25 * 1) + (0.5 * 0.5) + (0.25 * 7 / 12) = 0.6458333…
直前で「CのWPは2/3」だと言っているのに、次のOWPを計算する段階では「CのWPは0.5だから」としている。わけがわからない。ちなみに解説では後者のWPはWP’として別のものとして説明されている。なお、前者のWPは勝率で、後者のWPは自分との対戦を除いた勝率である。
英語力が堪能ならきっとすぐに分かるのだろうし、そもそもアメリカ人だったらバスケットのランキングを決める式くらい説明を読まなくても知っているのかも知れない。この問題は簡単な問題で、単に言われた通りに計算するだけである。計算量も問題ないし、問題を読んだ瞬間に理解できる人なら10分程度で終わるだろう。しかし、英語が苦手な人はTwitterを見てもOWPの計算がわからないと1時間以上悩んでいる人は多かった。
こんなコンテストであるから、プログラミングの実力以外のものもかなり影響してきそうである。でも日本人のrng_58氏（りんごさん）はぶっちぎりの1位で通過しているし英語ゲーというのは言い訳かも知れない。
翻訳メモリという考え方
自然言語処理の有用な記事が多い生駒日記の「Microsoft Office IME 2010 はガチ」というエントリに
そういえば、Windows 7 をインストールしていて気がついたのだが、MS の Windows 7 のインストラクションのページは恐らく機械翻訳の結果である。たとえば、Windows Vista から Windows 7 へのアップグレードのチュートリアルを見てもらえれば、ところどころ変なところがあることに気がつくだろう。それがルールベースのものなのか、Microsoft Research で研究されている統計ベースのものなのかは分からないが、以前あった「自動で翻訳された結果なので、間違っている可能性があります」という但し書きが取れる程度にはかなり読める日本語になっている。というか、ほとんどの人は機械翻訳の結果だと思わないんじゃなかろうか。あの規模で機械翻訳を実用化している企業として、Microsoft はもっと評価されて然るべきだと思う。
もっとも、Microsoft ほど、自社内で他言語に翻訳してきた、そして今後も翻訳したいリソース(マニュアルとかヘルプとか)がある企業もそんなにたくさんあるわけではないだろうし、こういうデータ、そして欲求のある分野・企業を見つけて自然言語処理の技術で解決していけるというのは、研究者冥利に尽きるなぁ。
という興味深い記事がある。これをそのまま信じるのなら、Microsoft Researchで研究されている統計ベースの機械翻訳は技術系文書の日本語訳に限っては実用の域に達しているということである。
そういうわけでMicrosoft® Translatorを使ってみたが、まだまだ役に立つレベルではなかった。
自動翻訳がダメでも翻訳支援というのがある。翻訳支援はプロの翻訳家も積極的に利用するほど実用の域に達しているという。つまり、例文をガシガシしていって、一度翻訳したことのあるフレーズだと直ちに翻訳され、似ているフレーズは過去に記録したフレーズと比較しながら翻訳できるというもの。また辞書もついていていちいち辞書を引かなくてもいま薬草としているセンテンスの中にあらわれる単語は自動的に辞書引きされる。
そういうわけで、OmegaTというオープンソースのものを使ってみたが、確かになかなかいいかも知れない。しかしJavaで書かれていてインタフェースがかなり汚いのがやる気をなくす。
統合翻訳環境Bentenというのもある。これはまだ試していないが、マイコミの記事が興味深い。
ともあれ技術系の文章は文学作品のように叙情的に書いていないので、比較的パターンで訳せると思われる。もちろん英語が堪能な人の中にも下手くそな文章を書く人はいるので苦労することはあるのだけど。
IDEの工夫
プログラミングコンテストは時間制限があるのでできるだけ短い時間でコードを書きたい。コードを書いていると頻出するものもある。
for( vector::iterator it = hoge.begin(); it != hoge.end(); it++ ){ }
これを毎回手で書いていると手間がかかる。コンテストに出ている人の多くはこれをマクロで解決する。
#define PB push_back #define MP make_pair #define SZ(v) ((int)(v).size()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define FORE(i,a,b) for(int i=(a);i<=(b);++i) #define REPE(i,n) FORE(i,0,n) #define FORSZ(i,a,v) FOR(i,a,SZ(v)) #define REPSZ(i,v) REP(i,SZ(v)) typedef long long ll;
大抵こんな感じのマクロを事前に用意してあってそれで短くわけだ。マクロというのは自動的にコードの記述を置き換えてくれるもの。
個人的にはこれは好きではなくて、なぜならコードが読みにくくなる。自分のマクロは慣れているからいいんだけど、他人が読んだときによくわからない。for_eachとか定番のものはまだいいんだけど、人によってはいちいちマクロの定義を確認しないとコードが読めないほど簡略化されていることもある。
そういうわけで、できることならIDEとかエディタの補完（スニペット）で面倒臭い記述を一発でやってしまいたい。
いまどきのIDEで有力なのはVisual Studio, Eclipseなどであろうか。おいらはMacを使っているのでXcodeがあるんだけど、Visual Studioのほうが何となくよさそうな気がする。そうすると、VMwareに比較的軽いWindows XPを入れてその上でVisual Studioを使うことになるのか。ちょっと面倒臭い。
EclipseはJavaを使う限りはかなり優れた開発環境だと思う。C++だとちょっといまいちの感じだけど、最近はどうなんだろう？e4とかEclipse 4.0が出てきているらしい。
どうやって勉強しようか
やっぱり受験勉強の数学みたいにひたすら問題演習をやっていくことかな。
おいらはC++を昔から使っていて楽なのでこれを使っている。しかしJavaやC#の仕事も多く、それらにもなじんでいかないとなーって思っている。JavaはEclipseがあるからいい。C#はmonoかVisual Studioだろう。C#使うなら頑張ってVMwareかなあ。
コードは最初のうちは面倒臭いけど、何度も書いているうちに手が覚えるので、演習問題をC++, Java, C#の三種類の言語で書いていればそのうち覚えそう。C#は昔からハーバードシルトの本は好きなのと、ちょうど最近新版が出たので買ってみた。
- 著者／訳者：ハーバート・シルト
- 出版社：翔泳社( 2010-12-03 )
- 大型本：704 ページ
- ISBN-10 : 4798122203
- ISBN-13 : 9784798122205
- 定価：￥ 3,990
内容はいかにも教科書という感じの本。あとプログラミングコンテスト向けの本は少ないので蟻本は外せない。
- 著者／訳者：秋葉 拓哉 岩田 陽一 北川 宜稔
- 出版社：毎日コミュニケーションズ( 2010-09-11 )
- 単行本（ソフトカバー）：316 ページ
- ISBN-10 : 4839931992
- ISBN-13 : 9784839931995
- 定価：￥ 3,444
アルゴリズムとかデータ構造の本って多いのだけど、この本のようにコンテスト向けに計算量とか意識したコードがたくさん載っている本ってあまりないような気がする。アルゴリズムの本はもっとアルゴリズムばっかりだし。
最近語学ばっかりやっているけど、将来はソフトウェアエンジニアとして身を立てたいと思っているので、Code Jam Round 2くらいまではあっさり行けるくらいの実力は持っておきたい。そうこう言っている間にRound 1Cまで1時間ほどである。
- 著者／訳者：ティモシー フェリス
- 出版社：青志社( 2007-09-21 )
- 単行本：255 ページ
- ISBN-10 : 490385311X
- ISBN-13 : 9784903853116
- 定価：￥ 1,470
- 著者／訳者：ティモシー・フェリス
- 出版社：青志社( 2011-02-03 )
- 単行本：640 ページ
- ISBN-10 : 4905042097
- ISBN-13 : 9784905042099
- 定価：￥ 1,995
- 著者／訳者：篠山 半太
- 出版社：PHP研究所( 2012-06-16 )
- 文庫：340 ページ
- ISBN-10 : 4569678467
- ISBN-13 : 9784569678467
- 定価：￥ 720
