Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2006年09月07日(木) Google Code Jam

[]Google Code Jam 2006 Qualification Round Google Code Jam 2006 Qualification Roundを含むブックマーク Google Code Jam 2006 Qualification Roundのブックマークコメント

昨晩 Google Code Jam に参加しました。

去年はRound 2の低得点問題を落として

Championship Round にいけなかったのですが、今年はいかに。

http://fxp.hp.infoseek.co.jp/img/gcj_2006_qr.png

Qualification Round で落ちるわけにはいかないので、

かなり緊張していたのですが、

ここで200位に入っていれば次にいけるのでしょうか。

ひとまずはシステムテストに落ちなくてほっとしています。


今年はC++,Java,C#,VBに加えてPythonが使えるようになったのですが、

Phythonは全く使い慣れていないので、今年もC++で行くことにしました。

C++,Java,C#,VBと、はっきり言って何も変わらない言語ばかり

(JavaC#なんて本当に何も変わらないし…)

ムダに4つもあったところから考えると

Pythonの追加は非常に画期的で、

一つだけ明らかに記述力が高いという状況になってしまっていますが、

そこはGoogleなので、ワザとやっているとしか思えません。

そんな言語を使えないのは残念ではあるのですが、

私はPythonを常用していないしする気もないので、

致し方ないところ。Googleとは相容れません。


というわけで問題ですが、

私はSet 3に割り当てられておりました。

問題は250点のと750点のとの2問で、時間は一時間です。


250点問題はサッカーの審判のカードの出し間違いを検出するという問題。

審判は同じ選手にイエローカード二枚目を出したら、

即座に同じ選手にレッドカードを出さないといけないらしいのですが、

その出し忘れがあれば、その一番早い時刻を求めろというもの。

この問題の一番の難点は、英語が長いということ。

あまりにも長い…。

途中で心が折れそうになりましたが、

なんとか8分ぐらいかかって問題を理解することが出来ました。

まぁ、作業問題なので、コードは書くだけなのですが、

条件の見落としが無いかとっても不安。

書きあがってテストをしようと思ったら、なんと、接続が切れました。

この一刻を争う時になんで…と思いながらもなんとか冷静を保って、

一旦問題を閉じて安静にしていると2分後ぐらいに復帰しました。

それからテストをして、全部通っていることを確認して、

さらに自分でいくつかテストケースを作って、

問題ないことを確認してからサブミット。

ここで開始15分ぐらいでした。


750点問題は正方行列Aに対して、

(A[1][p[1] ]*A[2][p[2] ]*...*A[n][p[n] ]) (pは[1,..,n]の並べ替え全て)

の下四桁を求めるというもの。

行列のサイズは16×16まで。

この問題は英文が短くて非常に助かりました。

問題は2分ぐらいで読めて、解き方も5分ぐらい考えていたら分かりました。

16!*16は時間的に無理ですが、

普通再帰的に解くと考えても、

再帰中の状態数が、16*2^16ほどにしかならないので、

キャッシュしてやれば計算は一瞬で終わります。

TopCoderに何度か参加したことがありますが、

2^Xでキャッシュすれば解けるというのは

ここでは結構頻出ですね。

コードはそんなに時間もかからず完成したのですが、

またもここで接続が切れてしまいました。

なんじゃこりゃー?と思いつつも再度一旦問題を閉じてじっとしていると

何分かして復帰。

テストをすると見事にバグっていて、これがなかなかとれない。

coutデバッグをしばらくしてようやくバグを発見。

十分にテストをして提出。

残り18分ぐらいでした。


提出したコードを貼っておきます。

http://fxp.hp.infoseek.co.jp/oth/gcj_2006_qr_250.cpp

http://fxp.hp.infoseek.co.jp/oth/gcj_2006_qr_750.cpp


しかしまぁ、なんといいますか、これはちょっと不本意な感じですね。

二問目に時間がかかりすぎました。

こんな単純なコードバグを入れるなんて、

私も耄碌したものですね。

このままでは次の次とか次の次の次とかに進むのが

厳しいかもしれないので、もう少し何とかしたいところです。

[]TCCC06 Qualification Round 1 TCCC06 Qualification Round 1を含むブックマーク TCCC06 Qualification Round 1のブックマークコメント

TopCoderから送られてくるメールが出ろ出ろとうるさいので、

2006 TopCoder Collegiate Challengeなるものにも出てみました。

なんだかルール記述がやたらに長いのであんまり読めてなくて

参加資格があるのかどうかも良く分かっていませんが…。

レートが高い人はQualification Round免除、

他の人はいずれかのQualification Roundで勝ち抜ければ良い、でOKなのでしょうか。

なんだか、Qualification Roundはまだ2回あって、

参加登録もまだ受け付けているみたいなので、興味のある方はどうぞ。

私はレートが低いのでQualification Roundから参加しました。


http://fxp.hp.infoseek.co.jp/img/tccc_2006_qr1.png

普通のTopCoderのルールと同じで、3問75分、チャレンジありでした。

上位450位が次に進出なのに、参加者が700人弱しかいなかった…。


250点問題

http://www.topcoder.com/stat?c=problem_statement&pm=6698&rd=10093

よく考えると、ソートして、前半を加算、後半を減算すれば良いだけ。

サイズが非常に小さいので、ナイーブに再帰的にとか書いても良いけど、

ナイーブに書かないほうが楽なんではないでしょうか。


500点問題

http://www.topcoder.com/stat?c=problem_statement&pm=6505&rd=10093

男女交互に身長順に並べよ、解が複数あるならレキシコ順、という問題か。

男女それぞれ分離してソートして、インターリーブして(高々二通りの方法で)、

それが条件を満たしているか調べるだけのような感じ。

レキシコグラフィカルというのが、辞書順なのか、アスキー順でいいのか

良く分からなかったので、びくびくしつつも面倒なのでアスキー順で提出。


1000点問題

http://www.topcoder.com/stat?c=problem_statement&pm=6667&rd=10093

15パズルの円筒版のような問題ですが、

有効なヒューリスティック関数がわからないので、IDA*で解くのは厳しそう。

そもそもIDA*は計算量の上限が見積もりづらいですが…。

イラストに反してサイズが3*4までなので、

幅優先で解いてしまってよいと思うのですが

(状態数が40万ぐらいにしかならないので)

あとでいろいろ試したのですが、この問題はそれでも厳しいです。

最後のサンプルが手元で6秒ぐらいで解けるのが精一杯というところ。

本番中はなんか勘違いして単にキャッシュつき深さ優先探索をしてしまって、

どう考えてもスタックがあふれるような状態で提出してしまい、

当然のごとく一瞬でチャレンジされてしまいました。

いずれにせよ、これはかなり難しい問題では無いでしょうか。

高レートの人が参加していないとはいえ、一人も正解者がいませんでした。


出したコード

http://www.topcoder.com/stat?c=problem_solution&rm=249604&rd=10093&pm=6698&cr=22627322

http://www.topcoder.com/stat?c=problem_solution&rm=249604&rd=10093&pm=6505&cr=22627322

この辺から見られるようです。

こっちも出来るだけ進めるように頑張ってみますか…。

トラックバック - http://d.hatena.ne.jp/tanakh/20060907