Google Coe Jam 2008 World Finals
なんかここのところの週末は他にやりたいことがあって、
文章を書きかけですっかり忘れていたら、
完全に時期を逃した感がありますが、
今更ながら参加記を記しておきます。
GCJテンプレート
前回日記を書いたときから一回も練習をしていないことに気づいた。
もうすぐそこに迫ってきているというのに。
テキサスに行ったときは
メダルを持ち帰ってきます、などと臆面もなく言っていたが、
今回はとてもじゃないが何も期待できない。
こんなに何もせずに勝てるわけないじゃない。
それはそれとして。
Round2のときにデュアルコアが使えてれば後一問通ったのに、と思って
Round3のときに準備したテンプレートでも公開してみることにする。
Round3が終わったときには、やっぱりプログラムはオーダーだ、
とか思って東京Local大会には持っていかなかったのだが、
計算機の気まぐれで通るという綱渡りになってしまったので、
Finalにはやっぱり持っていこうと思う。
あまり大きなテンプレートはバグが入っていたら怖いから、
できれば避けたかった所なのだが致し方あるまい。
#include <iostream> #include <sstream> #include <iomanip> #include <string> #include <vector> #include <map> #include <set> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <cctype> #include <pthread.h> using namespace std; //----- template <class T> class parallel_scheduler{ public: parallel_scheduler(int cpu_num):cpu_num(cpu_num){ T::init(); init(); } void go(){ string line;getline(cin,line); int cases=atoi(line.c_str()); for (int i=1;i<=cases;i++){ T *t=new T(); t->read(); while (running>=cpu_num) usleep(10*1000); schedule(i,t); } while(running>0) usleep(10*1000); } private: void init(){ running=0; next=1; pthread_mutex_init(&run_m,NULL); pthread_mutex_init(&ans_m,NULL); } void schedule(int cn,T *t){ pthread_mutex_lock(&run_m); running++; pthread_mutex_unlock(&run_m); pthread_t tid; pair<int,pair<T*,parallel_scheduler*> > *p= new pair<int,pair<T*,parallel_scheduler*> >(cn,make_pair(t,this)); pthread_create(&tid,NULL,start,p); pthread_detach(tid); } static void *start(void *arg){ pair<int,pair<T*,parallel_scheduler*> > *p= (pair<int,pair<T*,parallel_scheduler*> >*)arg; int cn=p->first; T *t=p->second.first; parallel_scheduler *ps=p->second.second; delete p; ostringstream oss; t->solve(oss); delete t; ps->register_ans(cn,oss.str()); ps->end(); return NULL; } void end(){ pthread_mutex_lock(&run_m); running--; pthread_mutex_unlock(&run_m); } void register_ans(int cn,const string &ans){ pthread_mutex_lock(&ans_m); anss.insert(make_pair(cn,ans)); while(anss.count(next)!=0){ cout<<"Case #"<<next<<": "<<anss[next]<<endl; anss.erase(next); next++; } pthread_mutex_unlock(&ans_m); } int cpu_num; int running; map<int,string> anss; int next; pthread_mutex_t run_m; pthread_mutex_t ans_m; }; template <class T> class sequential_scheduler{ public: sequential_scheduler(){ T::init(); } void go(){ string line;getline(cin,line); int cases=atoi(line.c_str()); for (int i=1;i<=cases;i++){ T *t=new T(); t->read(); ostringstream oss; t->solve(oss); delete t; cout<<"Case #"<<i<<": "<<oss.str()<<endl; } } }; //----- class solver; #define PARALLEL int main(int argc,char *argv[]) { #ifdef PARALLEL int cpu_num=2; if (argc==2) cpu_num=atoi(argv[1]); cerr<<"PAR: "<<cpu_num<<endl; parallel_scheduler<solver>(cpu_num).go(); #else cerr<<"SEQ:"<<endl; sequential_scheduler<solver>().go(); #endif return 0; } //----- class solver{ public: solver(){ // テストケースごとの初期化処理 } ~solver(){ // テストケースごとの終了処理 } static void init(){ // 全体の初期化処理 } void read(){ // テストケースをcinから読み込む } void solve(ostream &cout){ // 解く。出力は引数のcoutに。 } };
スレッド数の指定と、万一の時のための自明なコードによる逐次版を用意。
テストケースを読み込みながら、CPUが埋まっていなければそのテストケースをスケジュールする。
埋まってたらどれかが空くまで待機。
出力はバッファして、先頭から順に確定し次第出力。
例外のこととか何も考えられていないな。だがそれがいい。
さて、ライブラリを作る作業をせねば…。
安楽椅子探偵
二週間ぐらい前に出題編があったので、土日と代休を使って廃人のように推理をしておりました。
二年半ぶりぐらいです。まさにその時の記録が残っていてそれをすぐに見つけられるだなんて、
いやあ、ブログというものは素晴らしいですね。
http://d.hatena.ne.jp/tanakh/20060315#p4
(以下ネタばれを含みます)
今回は一応十分に考える時間があったので、
犯人も犯人を特定する方法も正解しました。
コアとなるロジックは、押し入れの中に死体がある→なんで手前のソファーじゃないのか→ストーブを取りに行くのを知ってたから、
というのと、携帯電話の電源Off→携帯電話の着信音がうるさいのを知っていたから、の二つだと思うのですが、
おそらく私が50万円がもらえなかったのは、圧倒的文章力のしょぼさと、
余計な事を書いてしまったからだと思います。
「思い出せ」カードにたいして余計な推論をしてしまいました。
まあ、これを含めても、たとえば携帯電話の音なんかも匙加減だとは思うのですが、
これはあれだけあざとく入れられてたら、きっと入れられている意味があるのだろうとか、
メタなレベルでバランスのよさそうな解答を目指しました。
とはいえ、解答編を見るまでは全然合っている自身がなくて、今回はだめだと思っていました。
前回結構大じかけなものだったので、
今回自分の答えが合っていたらあまりにも地味すぎると思ったのですが、
結局年号を錯覚させようとしていると見せかけて実は全然そんなことは無かった、
というのがその大じかけに相当するものだったのでしょうか。
「今回はとても難しい」という作者のトークが一番のミスディレクションだったわけです。
さて、これで戦績は2勝1敗。次回も楽しみにしております。
待つのが辛いのでぜひとももう少し短いスパンでやっていただけると嬉しいです。
SRM 422
Code Jam Finalの練習のために8ヶ月ぶりぐらいに参加してみました。
http://www.topcoder.com/stat?c=round_overview&er=5&rd=13513
最近は日本の参加者が増えたためか、プラグイン導入を説明した日本語のブログがいくつかあって、とても参考になりました。
250点問題→19^3のDPを適当に組んだ。250点でDPとはすごい時代になったものだなと思ったけど、よく考えたらそんなことしなくても解ける問題であった。そんなことよりも、問題文を3分で読めるようになっていた自分の英語力の成長ぶりに感動。
500点問題→一転して英語が難しい。解読に15分ぐらいかかってしまった。英語力云々は思い過ごしだったようだ。問題自体はいたってシンプル。こんなに英語長くする必要ないではないか。普通にダイクストラ。そして、普通にTLE。もう、だからSRMやりたくないんだよ。なんなんだよ制限時間2秒って。際どすぎるんじゃ。手元のしょぼいCPUのノートで最悪っぽいケースが3秒ぐらいだったからいけると思ったのに。
1000点問題→急に不安になったので、250点と500点問題を見直してからOpen。見た感じ最大流だと思ったが、手ぶらで参加したので何もできず。一見さんはお断りですか。次からはちゃんと準備させてもらいます。残り20分ぐらいヤキモキしながら終了。
チャレンジ→とてもレートが低い人が終了間際に1000点出してて、案の定それが赤い人に落とされたりしているのを見守っていました。
感想→250点難しくなってないか？1000点は普通。今回だけかもしれないが。いずれにせよ自分のコーディング速度が全然足りない。どうしたら速くなるかな。
GCJ Onsite Locals
ということなので、ちょっと休暇を戴いて渋谷のGoogleオフィスまで行ってきました。前行ったときには1フロアだったような気がするのですが、順調に4フロアに増えていました。
参加者の大半は知ってる人で、あるいはそうでなくともほとんどはハンドル名を目にしたことのある人でしたが、久しぶりに会う人も多くて楽しかったです。Google社員の方々にも見知った顔が結構いて、なんというか、世間は狭いなとか思いました。
コンテスト自体は今までとさして変わることはなく、2時間4問で大小の入力があるような形式でした。英語キーボードだったら苦しいので、一応家からRealForceというキーボードを持って行っていましたが、用意されていたのが日本語キーボードだったので、深く考えずそれを使うことにしました。しかしなんだか微妙に幅が狭くて、カーソルキーに手を伸ばすとテンキーの1とか0とか辺りを押してしまうだとか、表面がざらざらしていて左手小指が擦り切れて痛かったりとか、あまり良いことがなかったので、やはり持って行ったものを使うべきでした。
マシン環境は比較的自由で、30分の準備時間が与えられて、好きなソフトをダウンロードしてインストールしてよいとか、USBからあらかじめファイルをコピーしてよいだとかで、かなり好きなようにできました。とりあえず電卓としてGHCを入れておきました。そのほかは自宅マシンの.emacsを持って行ってFlymakeの設定をしたりだとか、キーマップ変えたりだとか、ソースのテンプレート作ったりだとか、まああまり自由でも大してやりたいことはないのですけども。
そんな感じで、コンテストが始まったのですけど、今回は私個人的には非常に劇的な結末でした。そのおかげで随分と精神的に疲れました。たった2時間でこんなに疲れたことは未だかつてなかったです。問題などは、
http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtchALEghjb250ZXN0cxihuBQM
こちらから見れるようです。深く考えずにAに手をつけたら、入力の制約に誤植があってIncorrectを喰らって、そのまま1時間放置してしまったりとか、どう見ても簡単なDのSmallをおいしくいただこうと思ったらバグを入れまくったりだとかで、開始1時間近くまで0点だった時には今回はもう駄目かなと思ったのですが、Cで2^2mなアルゴリズムを実装して、最悪なケース1個当たり1分ぐらいかかってこれは間に合わないかなと思いながらもほかに高速化も思いつかなくて、残り8分を切ったので、とりあえずファイルをダウンロードしてプログラムに突っ込んでみたら、思ったより速くて、これはもしかしたら間に合うか、と思いつつビクビクしながら待っていると残り時間10秒ぐらいになったときに実行完了して、なんとか残り8秒でサブミットが間に合うという強運ぶりを発揮しました。これが効いて、Aのlargeを落としたにもかかわらず、なんとか上位20%には入れたようです。CPUがあと1グレード低かったら通ってなかったかと思うともう心臓に悪いです。
私がICPCをやってた頃には戦えなかった若い人たちとオンサイトで戦えて、今回は非常に新鮮な感じがしました。とても楽しかったです。しかしながら私はもう随分と昔取った杵柄だけで勝負しているような感じなので、次は（もしあれば）十分準備して望みたいと思います。
