検索

Google
Web www.icefree.org

RSS of recent changes

  
Top / ソフトウェア / プログラミング / GoogleCodeJam2005

GoogleCodeJam2005

2017-06-20 (火) 23:23:54 (2991d)

　今年もやってきたGoogle Code Jamです。
　決勝ラウンドの定員が、去年の50人から100人に増えました。今年は、日本からの参加者で決勝に行ける人も出てくるでしょう。

　私は時間的にQualificationRound?しか参加できないかも。
でも、少なくともTシャツは貰えるように頑張ります。
　ちなみに今年もハンドルは"hakojima"で参加します。
でも、見かけてもそっとしておいてください;-)

(8/25)
　玉砕しました。

　参考：去年の記事

コメント †

  • nirvash 2005-08-22 (月) 17:29:13
    初めての参加なのでいろいろ参考になります。
    TCO の Qualification に参加してみましたけど、自分のアサインされたルーム内での順位は200位でした。(ボーダラインは150位)。GCJ は100位がボーダラインだし、参加者も多かったりするとさらにきついなぁ、と思いつつＴシャツゲットするため頑張ります。
  • vvp 2005-08-22 (月) 21:39:59
    コメントありがとうございます。
    TCOのQualificationは帰省中で気が付いたときには終わっていました・・・。
    GCJは今日(8/22)の深夜25:00（日本時間）からスタートです。私は忘れないように寝る前に終わらせてしまおうと思ってます。
    でも、今ログインしてみたら、Roomが15個もあります！去年は10個だったと記憶していますし、今回（2005）のルール説明にも10ルームだと書いてあるので、予想以上に参加者が集まったということでしょうか。思っていたよりも大変な戦いになりそうです。
    ケアレスミスに気をつけて何とか通過できるようにがんばってみたいと思います。
  • AC 2005-08-23 (火) 07:32:45
    GCJ に限らず、TopCoder? も最近は 2 秒でタイムアウトしますよ。(TopCoder? 内でマシンの update があって、「マシンが 4 倍以上速くなったからこれからは 2 秒でタイムアウトさせるね」ということになりました。)
  • vvp 2005-08-23 (火) 15:47:04
    　ご指摘ありがとうございます。
    　確かに、２秒と書いてありました。
    Competing in a TopCoder? Rated Event(http://www.topcoder.com/tc?module=Static&d1=help&d2=ratedEvent )
    6.3 The System-Testing Phase
    　コーディングウインドウの説明は８秒のままで、こちらを見て８秒だと思い込んでいました。多分、ユーザ環境まで４倍速くなったわけではないので、ユーザサイドの時間であるこちらは８秒のままなのでしょう。
    The Coding Window(http://www.topcoder.com/tc?module=Static&d1=help&d2=codingWindow )
    3 Creating a Solution
    5 User Testing
  • nya 2005-08-23 (火) 20:53:29
    「概要」の賞金の額ですが、正しくは51~100位の賞金は$750のようです。
  • vvp 2005-08-23 (火) 21:22:10
    間違いばかりで申し訳ありません。修正しました。
  • AC 2005-08-23 (火) 23:01:19

    コーディングウインドウの説明は８秒のまま

あ、本当ですね。
さきほど TopCoder? のスタッフに連絡をしたので、今は２秒に修正されました。

  • duvetica ace 2013-11-16 (土) 15:08:32
    duvetica ダウン メンズ
    duvetica ace http://www.sundns-mall.com/メンズファッション-アウタ?-lb3y-1_2.html
  • ダウン ブランド 2013-11-16 (土) 15:08:37
    レディ?スショッピング
    ダウン ブランド http://www.rusenamega.com/アウタ?-ダウンジャケット-pgnc-1_2_3.html
  • プラダ 2014-01-15 (水) 18:19:54
    プラダ ?下|プラダ 仟恬|プラダ|||www.mmtc.or.jp/cgi-bin/blog/archives/prada-c1.html|||プラダ ?下|プラダ 仟恬|プラダ
    プラダ http://www.mmtc.or.jp/cgi-bin/blog/archives/prada-c1.html

↑

概要 †

　公式ページ

↑

参加資格 †

　8月22日時点で18歳以上。
　また、日本からの参加でも賞金が出ます。

↑

スケジュール †

　日本時間への変換はもしかしたら間違っているかもしれません。

  • 登録開始 7/25(Mo) 9:00AM EDT
    　7/25(Mo) 10:00PM JST
  • 登録締切 8/19(Fr) 5:00PM EDT
    　8/20(Sa) 6:00AM JST
  • 予選ラウンド開始 8/22(Mo) 12:00PM EDT
    　8/23(Tu) 1:00AM JST
  • 予選ラウンド終了 8/23(Tu) 12:00PM EDT
    　8/24(We) 1:00AM JST
    　予選ラウンドは上位500名が通過できます。
  • ラウンド1 8/29(Mo) 9:00PM EDT
    　8/30(Tu) 10:00AM JST
    　ラウンド1は上位250名が通過できます。
  • ラウンド2 9/1(Th) 9:00PM EDT
    　9/2(Fr) 10:00AM JST
    　ラウンド2は上位100名が通過できます。
  • 決勝ラウンド 9/23(Fr) EDT

　予選〜ラウンド２はオンラインでのコンテストで、決勝ラウンドはカリフォルニアでのコンテストです。

↑

賞金 †

　決勝ラウンド出場者（実際に現地に行くことが条件）には賞金が出ます。
　また、予選通過者にはTシャツが贈られます。

　総額は$155,000（1705万円）です。
　（1ドル110円で計算しています）

　優勝　$10,000（110万円）
　2〜10位　$5,000（55万円）
　11〜25位　$2,500（28万円）
　26〜50位　$1,000（11万円）
　51〜100位　$750（8万円）

　賞金だけなら同様に８月に開催される2005 TopCoder? Open(TCO)の方が獲得できる可能性は高いと思われます。そっちは、Round1からルーム毎の高得点者に賞金が出ます。
　というか、TopCoder?的にはTCOの方が大きなイベントです。

↑

予想される決勝レベル †

Google Code Jam 2004 Predictions
http://www.jshowalter.com/topcoder/gcj2004/

を参考にすると、50位までだった去年の決勝に必要なレーティングは約2300です。
　去年のボーダーが100位までだったとすると、約2000で通過できることになります。

　もうちょっと敷居が下がるのかなと思ったのですが、結構高いですね。

↑

アドバイス †

　初めて参加する人には、知らないと損をすることがいろいろあるので、まとめてみました。こうやって手口を公開してしまうのは私にとって不利になることではあるのですが、日本からの参加者は少ないので日本語で提供しても大した問題にはならないということと、もうちょっと日本勢に頑張ってもらって日本からの参加者がいるんだということをアピールしたいという理由から公開してしまいます。

↑

低得点問題 †

　低い点数の問題は、問題自体は簡単です。
　Round2までは、低得点問題が確実にそこそこの速度で解ければ辿りつけると思います。それ故に高レーティングの人以外は、ここが肝要です。高レーティングの人には、私が何か言うようなことはありません。むしろ教えて欲しいです。

　日本人にとって解くべき問題は２つあります。

  • 如何に速く問題を理解するか
  • 如何に速くコーディングするか

　私は英語がかなり不自由なのですが、そんな人でも慣れると意外となんとかなるものです。一番のコツは、多少分からなくても「気にしない」ということです。問題は文章ですが、音声だと思ってガーっと読みます。なんとなく問題の大筋がわかったら後は例題で補完します。簡単な問題だとこれで理解できます。英語がとてもダメだという人は、最初からコピペで英和翻訳して、例題で補完という手も使えるかもしれません。例題を見ても理解しきれなかった時は、問題をマジメに読み直します。
　大抵はこの方法で上手くいくのですが、小さな誤解が大きな違いになることがあって、玉砕することもあります。30分くらいかけても問題を理解できなくてコードも書き始めることが出来ていないなら、その問題は諦めてしまった方がいいかもしれません。

　問題が理解できたら、あとはコーディングです。
　例題から自動的にテストコードを書いたり、テンプレートに要求されたクラス・メソッド名を書き込んでくれるようなプラグインが通常のTopCoder?のCompetitionには用意されているのですが、GoogleCodeJam?ではプラグインは使用できません。そのため、あらかじめテンプレートやテストするための汎用的なコードを用意しておくと役に立つと思います。また、トークン分割などのライブラリを事前に用意して置くのも役に立つかもしれません。ただし、使っていないコードが多すぎると規約違反になりますので、使う分だけ選択しなければいけません。
　低得点問題のコーディングのコツを１つ挙げるなら、「とにかくベタに書け」です。メモリ使用量の上限や実行時間の制限はありますが、低得点問題ではベタな解き方をしても問題とならないことが多いです。場合の数が100万あったとして、それをfor文で回してチェックしても良いのです。また、別の例では、work[100][100]を元にして新しく同じサイズの配列を作る作業が20回必要だとします。2世代前以前のデータは要らないとしても、work[20][100][100]で確保してしまえば良いのです。その方が安全確実に速く解けるならそれで良いのです。
　また、C++の場合は、STLの多用が常套手段です。特にvector型が好まれます。STLの使い方は挙げると長くなるので、ここでは多くを書きませんが、余力があれば別のページにまとめたいと思っています。ここでは例を1つだけ挙げたいと思います。
　引数vector<int> argで渡された中で一番大きい数と小さい数を１つずつ除いた合計を返せ(TopCoder?からの出題ではなく、今適当に作った問題です)。

#include <vector>
#include <algorithm>
using namespace std;
int func(vector<int> arg) {
 sort(arg.begin(), arg.end());
 int sum = 0;
 for (int i = 1; i < arg.size() - 1; i++)
   sum += arg[i];
 return sum;
}
引数の制約を決めていないので適当です
単純にSTLを駆使して短く書くなら
return accumulate(arg.begin(),arg.end(),0)
- *max_element(arg.begin(), arg.end()) - *min_element(arg.begin(), arg.end());
の１行。accumulateなんて使ったことないし、むしろ面倒だけど。

　長くなりそうなので、STL関連はこの程度でやめておきます。

　あと、マクロ(#define)も使いこなせればタイプ量が減らせて良いと思うのですが、慣れていないと咄嗟に出てこないので、むしろ普通にタイプしたほうが快適だったりします。そのため、私はマクロを使っていません。

↑

高得点問題 †

　今回の問題がどうなるかわかりませんが、TopCoder?の出題の傾向として、1000点問題は動的計画法などの最適化が必要なことが多くなっています。
　これは結果が出るまでの制限時間があって、それを越えるコードは無効になるからです。この制限時間というのは、アプレットでのTESTを実行したときの時間（ユーザの環境での実行時間）ではなくTopCoder?のテスト環境での実行時間です。ちなみに、通常のTopCoder?の規約では8秒の制限時間ですが、GoogleCodeJam2005は2秒だそうです。（訂正2005/8/23 通常のTopCoder?でも２秒でした）

↑

ケアレスミスを防ぐ †

　どの問題にも言えますが、引数の範囲については注意が必要です。場合によっては、内部の計算が32bitでは足りないこともありますし、最も時間のかかるケースで制限に引っかかることもあります。

　doubleは「正解値*(1±1E-9)」の誤差があるとダメです。つまり、EPSILONは1E-9です。NaN/±Infinityは一致しないとダメですが、そういう問題はまず出題されません。

↑

QualificationRound? †

↑

参加方法等 †

　（去年と同じという前提で書いています。）

　あらかじめ登録期間中に登録しておく必要があります。

　コンテストのシステムはTopCoder?のものが使われます。事前にTopCoder?のPracticeで練習しておくと良いでしょう。

　予選は、他のラウンドと異なり、期間が１日間設けられています。
　コンテストは最初の問題を開くと開始されます。問題を解くことができる時間は１時間（ラウンド自体が終了しないなら）です。
　また、予選ラウンドは、チャレンジフェーズという他人のバグを見つけるフェーズがありません。

　問題は５セット用意されます。異なるセットは一部重複もありますが、異なる問題となります。各セットの上位100名（合計500名）が予選通過となります。

↑

本番 †

　QualificationRound?は開催期間が24時間と長く、いつ始めても良いのですが、翌日では参加できない可能性もあるので、オープンと同時に始めました。ちなみに日本時間では夜中の１時からです。

　オープンの３時間前くらいにログインしたのですが、既に100人以上の人がログインしています。さらに、アクティブコンテストを見てみると、ルームが15個もあります！去年は10個だったと記憶していますし、今回（2005）のルール説明にも10ルームだと書いてあるので、予想以上に参加者が集まったということでしょうか。思っていたよりも大変な戦いになりそうです。

　Roundがオープンして、指定されたルームに入ると、250点問題と750点問題が用意されていました。
　とりあえず順当に250点問題、750点問題と解いていきました。ラウンドが進むごとに問題のレベルも上がっていくらしく、QualificationRound?はTopCoder?の通常のSRMでいうとDIV-IIレベルという感じがします。このレベルだと最適化の必要がない比較的簡単な問題が出題されます。最適化は正直言って得意でないので助かります。

　とりあえず２問とも出来たけど、あとは結果待ちです。
　テストが通れば大丈夫だとは思うんだけど、案外バグ持ちだったりするんだよなぁ・・・。

（２４時間経過）

　なんとルームが２０まで増えてます。参加者数を数えてみたら4696人でした。競争率9.4倍です。
　さらに、システムテスト前の段階でSet内177位です。通過は100位以内なので、ちょっとダメそうです。

　参加者が多いので、システムテストには５時間以上かかったようです。
　システムテスト後で160位です。この後、不正者の削除がありますが、60人も削除されることは無いので、今回はQualificationを通過できない見込みです。無念。
　去年の人数だったら大丈夫だったと思うんですけどねぇ・・・。

↑

反省 †

　今回は特にミスはしていませんが通過できませんでした。要するに実力が足りなかったということです。
　250点問題を15分、750点を23分くらいで提出しています。問題の難易度からすると、750点問題も15分くらいで解きたかったところです。
　何がいけなかったか？

１．問題の読解
　今回はスムーズに読めたつもりなので、多分3〜5分くらいだと思います。これを短縮するには問題を斜め読みするしかないと思うのですが、それで上手く理解できるケースは少ないのではないかと思います。もしかしたら、問題の読み方のコツみたいなものがあるのかもしれませんが、とりあえずこの点については、今の私のレベルでは突き詰めていくことではないと考えています。
　そういうわけで、問題の読解については特に問題はなかったと思います。

２．コーディング
　低得点問題なのでアルゴリズムらしいアルゴリズムを考えるまでもなくノータイムでベタに書いていけました。
　しかし、コンパイルしてエラーがたくさん出て、それを修正するという作業を行っています。これが結構影響しているのではないかと思います。
　STLの使い方にあまり慣れていなく、引数の指定を間違ったりしました。具体的を挙げると、

vector<string> v1, v2;
...
v1.insert(v2);

と最初、書いてしまいました。
　エラーが出て、「あ、イテレータで指定か」と気づいて

v1.insert(v2.begin(), v2.end());

と直しました。実はこれもエラーです。本当はさらに挿入位置が必要です。

v1.insert(v1.end(), v2.begin(), v2.end());

と直して正しくコンパイルできました。
　こんなことは単なる時間の浪費でしかありません。

　また、時間のロスには繋がっていないと思いますが、sstreamを使い慣れていないので、sscanf()やsprintf()を使ってしまったのは、少し恥ずかしいことです。C++(STL)使いならば、ストリームも使いこなさないといけないところです。

　また、750点問題に23分もかかっていますが、感覚としては250点問題と同じくらいの時間で解いたつもりでした。しかし、実際には約7分の時間差があります。この時間差の大部分はデバグ時間の差によるものです。

　今後の課題を一言でいうと、「コンパイルが一発で通るコードを最初から書く」。
　STLの習熟度を上げるなどの自助努力が第一ですが、コーディング環境の改善でもだいぶ変わるのではないかと思います。
　単純なテキストエディタを使わずに統合環境を使えば、入力の補完をしてくれるので、引数を間違えるミスは軽減されます。私はいまだにEmacs＋シェルという環境でコーディングしているのですが、もうそういう環境は捨てたほうが良いということかもしれません。
　750点問題のデバグに時間がかかっている問題も、統合環境でデバグができれば時間の短縮になったと思います。

３．テスト
　今回はTopCoder?で普段使えるプラグインが使えないので、標準で提供されるAppletのテストをそのまま使いました。しかも、コードに自信が無いので、用意されているテストケースを全部丁寧にチェックしています。これも１分１秒を争うコンテストでは見逃しがたい時間のロスになっています。
　来年は事前に仕組みを作っておきたいと思いますが、普段のTopCoder?ではプラグインが自動でテストケースを作ってくれるので、この問題はしばらく（１年くらい）は放置します。

今後の課題
　・環境をもっとリッチにする
　・STLの習熟度を上げる

↑

Round1 †

　とりあえず問題を拾ってきました。
　ざっと見た感じでは、

↑

250点　文字列操作 †

　指定座標に点を打って、打たれた点を含む最小の四角形（傾かない）の範囲だけを返す問題。

↑

500点　グラフ †

　与えられたグラフで辺の数がk以上の頂点を返す問題。
　最初はｋ頂点以上の完全グラフを探す問題かと思いましたが、よく見たら、そんなに制約は厳しくありませんでした。

↑

1000点　最適化 †

　シーソーがあり、そこに座らせる子供の重量と座らせるシート位置が与えられる。片側の同じ位置には一人しか座れない。出来る限り座らせる。その時の重量差（テコの原理あり）を最小にしろという問題。
　総当りだと多分間に合わないので、動的計画法で解きます。

という出題です。

↑

使用言語 †

　Qualificationでは使用言語を調べてなかったので、Round1で見てみました。
　C++が60%、Javaが31%、C#が7.4%、VBが1%でした。50位ごとの割合にすると以下のグラフのようになっていました。

round1_lang.gif

　なかなか面白い結果がでました。
　上位はC++が多く、下位ほどJavaの割合が高くなっています。また、C#は人数は少ないですがまんべんなく居ます。
　ちなみに、下位といってもQualificationは通っている人たちですから、十分に凄い人たちです。
　VBはとにかく人数が少ないです。

↑

Round2 †

　ラウンドが終了すると、そのラウンドの問題はPracticeRoom?に追加されるので、ラウンド通過者でなくとも問題自体には挑戦することができます。
　暇なので今回はPracticeRoom?で遊んでみました。

　ちなみに、このラウンドを通過するとオンサイトの決勝です。どうやら、日本からの参加者でも、かなり上位の方で通過されている人がおられるようです。TopCoder?でも素晴らしい戦績を収めていて、優勝も狙えそうな人です。インターネットの片隅からひっそりと応援しています。

↑

300点問題 BruteForce?（総当り） †

　迷路の中を動き回ってゴールまでの最短ステップ数を求める問題。

　矩形とは限らない迷路がvector<string>与えられます。壁が'X'で、歩けるところが'.'、プレイヤは'P'で、ゴールは'G'です。
　１ステップでは、全てのプレイヤが同じ方向に動きます。誰かが、壁にぶつかったり、迷路の外に出るようなステップは無効です。
　誰かがゴールに辿りつくまでのステップ数を返します。

　問題自体は簡単なのですが、条件を読む落とすと失敗します。最初、壁の条件を間違えて解いてしまいました。
　また、比較的書かなくてはいけないコード量が多いので、時間がかかります。

　問題の条件が厳しいので、簡単なアルゴリズムで解くことができます。でも、こういう問題が英語力の低い人にとっては一番辛いです。

↑

500点問題 最適化 †

　与えられたハッシュ関数のシノニムの最頻値を求める問題。

　ビット列 Xiに対して、

key = 0
X_0 = 0
for (i = 1 to lengthof(bits)-1)
 key = (key * mults[X_{i-1}*2+X_i] + adds[X_{i-1}*2+X_i]) % size

でハッシュのキーが与えられる。
　１ビットから指定ビット長(int bits)までの全パターンで、同じキーとなるパターンの最頻値を求める。

　動的計画法で解きます。
　ビット数分のテーブルを確保しようとするとメモリが足りなくなるので、２ビット分だけ確保して使いまわします。
　あと、衝突回数の格納にlong longが必要なので要注意。

　教科書的な問題でヒントも多いので、比較的簡単でした。

↑

1000点問題 数学 †

　P_1,...,P_n > 1 (1 ≦ n ≦ 10) が与えられたときに、全てのP_iに対してK_i^{P_i} ≡ 0 (mod N) を満たす最小のNを求める。ただし、K_i > 1, K_i ≠ K_j (i≠j)。

　この問題は、私が見たことのある問題の中で最短のものです。1000点問題でこの短さは、何ともいえない不穏な雰囲気を醸し出しています。

　まず最初に想像できるのは、Nを最初に確定して、それが当てはまるかどうかを確かめる方法は取れないということです。long longを返す時点で、総当りが効きそうにないですし、因数分解は処理が重すぎます。
　また、整数での処理なので、対数は使い物になりません（人間がアルゴリズムを考える際には役立ちます）。

　ということは、Kを計算していくことになります。法則を見ていくと、Pを逆順にソートして順に小さい値を割り当てていくと良さそうです。その際に素数の存在が重要そうです。
　どのように割り当てるかですが、基本的には2のべき乗を割り当てていけば最小になります。しかし、実際にはそう簡単にはいきません。特に、P_iに重複があったときが問題です（それ以外でもダメなケースは多い）。
　たとえば以下のようになります。
　P={2}が与えられた場合、K={2}で、答えは2^2の4です。
　P={2,2}のときは、K={2,2^2}で、答えは2^4の16です。
　P={2,2,2}のときは、K={2,3,2*3}で、答えは2^2*3^2で36です。
　P={2,2,2,2}のときは、K={2,3,2^2,2*3}で、答えは、2^4*3^2で144です。
　P_iを順に確定させていくような処理が出来ない（と思う）ので、総当りで対処しないといけないと思われます。

　素数は最大で10個用意しておけば十分です。その素数の組み合わせ（Π Prim_i ^ Pow_i）を総当りで調べます。問題中には明確な上限は示されていませんが、long longの最大値が2^63-1なので、0≦Pow_i≦63まであれば十分です。総数は、63^17でかなりの数になってしまうので、枝刈りで減らす必要があります。

　これを時間内に解けというのはかなり厳しいです。前回のSRM261(TopCoder?の普段のコンペティション Single Round Match）もそうですが、数学問題が出るとほとんどの人が解けません。でも、手を動かし続けなければ勝てないようなコーディング勝負よりも、手を止めて頭をフル回転させなければいけないような勝負の方が楽しそうです。まぁ、私は解けませんが・・・。

↑

ChampionShipRound? †

　問題は確保済みですが、中身はまだ見ていません。

　最終順位が確定しているかどうかわかりませんが、どうやら今回はポーランドの学生が優勝したようです。

　とりあえず速報でした。

↑

リンク †

↑

参加者 †

　参加表明している人たちです。
　並び順は私が見つけた順です。

↑

関連記事 †

Counter: 7466, today: 2, yesterday: 3