GoogleCodeJam2008

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

随時更新中です。 (2008/6/21-)

去年は開催されなかったGoogleCodeJam?ですが、2008は復活しました。
システムはだいぶ様変わりしたようですが、これはこれで楽しそうです。

Round2は旅行中なので、一応ノートPCは持ってくけど、参加できないかも（宿泊先で電波が入らなければアウト）。
このページの更新は確実に遅れます。

Round2終了。結局、出発を遅らせて、自宅で参加しました。
更新環境を持っていかないので(EMONEくらいならあるけど)、
水曜日まで更新しません。

出題内容と解説は別ページにしました。
./問題

過去の開催分 †

GoogleCodeJam2004
GoogleCodeJam2005
GoogleCodeJam2006（2006年分はかなり適当）

年々、成績が悪くなってます。
コンテストが有名になって優秀な参加者が集まるようになってるのに、自分は成長してないってことか・・・。

コメント †

• ロレックス ミルガウス 2013-10-09 (水) 20:15:45
  ロレックス オイスタ?
  ロレックス ミルガウス http://www.cu70.com/
• ロレックス ヨットマスタ? 2013-10-09 (水) 20:15:50
  オメガ 俐尖
  ロレックス ヨットマスタ? http://www.cu71.com/
• ugg boots on sale 2013-11-04 (月) 22:38:27
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  ugg boots on sale http://imbibetechnologies.com/uggs-for-billig-Norway/uggs-for-kvinner-c-6.html
• UGG st?vler forskydning 2013-11-04 (月) 22:38:52
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  UGG st?vler forskydning http://savemytiger.com/Uggs-for-kids-Denmark/billige-uggs-c-192.html
• Cardy classique uggs 2013-11-04 (月) 22:39:34
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  Cardy classique uggs http://www.ewavecorporation.com/ugg-boots-France/ugg-sortie-p-196.html
• longchamp outlet 2013-11-06 (水) 05:03:04
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  longchamp outlet http://www.astoriashishkebobhouse.com/longchamp-sale/longchamp-outlet.html
• longchamp outlet 2013-11-06 (水) 05:03:35
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  longchamp outlet http://www.drsushi.com/longchamp-mini/longchamp-outlet-houston.html
• purple bailey button uggs 2013-11-25 (月) 05:20:03
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  purple bailey button uggs http://www.europeanhri.com/Official-Ugg-Outlet/purple-bailey-button-uggs.html
• nike free run womens black and turquoise 2013-12-08 (日) 17:48:57
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  nike free run womens black and turquoise http://www.thehamlet.ie/html/store.asp?module=tags&brand=nike-free&tags=nike-free-run-red-and-white-mens
• http://www.beffroisteakhouse.com/store.php?module=list&brand=cheap-nike-free&page=1 2013-12-11 (水) 01:30:20
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  http://www.beffroisteakhouse.com/store.php?module=list&brand=cheap-nike-free&page=1 http://www.beffroisteakhouse.com/store.php?module=list&brand=cheap-nike-free&page=1
• http://www.hardingsfurniture.co.nz/store.asp?module=list&brand=cheap-ugg-boots&page=1 2013-12-11 (水) 01:31:17
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  http://www.hardingsfurniture.co.nz/store.asp?module=list&brand=cheap-ugg-boots&page=1 http://www.hardingsfurniture.co.nz/store.asp?module=list&brand=cheap-ugg-boots&page=1
• http://santaclaritalanes.com/html/index.asp?module=list&brand=cheap-ugg-boots&page=1 2013-12-11 (水) 01:31:44
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  http://santaclaritalanes.com/html/index.asp?module=list&brand=cheap-ugg-boots&page=1 http://santaclaritalanes.com/html/index.asp?module=list&brand=cheap-ugg-boots&page=1
• http://www.boxingnz.org.nz/store.asp?module=list&brand=cheap-nike-free&page=1 2013-12-11 (水) 01:31:46
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  http://www.boxingnz.org.nz/store.asp?module=list&brand=cheap-nike-free&page=1 http://www.boxingnz.org.nz/store.asp?module=list&brand=cheap-nike-free&page=1
• http://www.naccu.org/images/2013/store.asp?module=list&brand=cheap-nike-free&page=1 2013-12-11 (水) 01:31:58
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  http://www.naccu.org/images/2013/store.asp?module=list&brand=cheap-nike-free&page=1 http://www.naccu.org/images/2013/store.asp?module=list&brand=cheap-nike-free&page=1
• http://www.asdeporte.com/ws/store.asp?module=list&brand=cheap-nike-free&page=1 2013-12-11 (水) 01:32:10
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  http://www.asdeporte.com/ws/store.asp?module=list&brand=cheap-nike-free&page=1 http://www.asdeporte.com/ws/store.asp?module=list&brand=cheap-nike-free&page=1
• lancel outlet 2013-12-28 (土) 08:44:39
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  lancel outlet http://www.focusglobalreporter.com/lancel-bags-sale/lancel-outlet.html
• lancel shop 2014-01-08 (水) 02:50:20
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  lancel shop http://goo.gl/NTepkE
• roxanne mulberry bag 2014-01-20 (月) 09:55:06
  ソフトウェア/プログラミング/GoogleCodeJam2008 - vvphome
  roxanne mulberry bag http://www.pinnacledsd.com/handbag-outlet/roxanne-mulberry-bag.html

お名前:

リンク †

公式サイト
http://code.google.com/codejam/

Googleグループ †

• Google Code Jam Announcements
  http://groups.google.co.jp/group/codejam-announce
• google-codejam
  http://groups.google.co.jp/group/google-code

日本で参加表明している人たち †

順番はアルファベット順です。
http://blog.deadbeaf.org/
http://slashdot.jp/~line/
http://d.hatena.ne.jp/caligue/
http://d.hatena.ne.jp/EmK/
http://d.hatena.ne.jp/henschel/
http://d.hatena.ne.jp/isobe/
http://d.hatena.ne.jp/jonigata/
http://d.hatena.ne.jp/mahata/
http://d.hatena.ne.jp/matsuza/
http://d.hatena.ne.jp/mickey24/
http://d.hatena.ne.jp/mokehehe/
http://d.hatena.ne.jp/morchin/
http://d.hatena.ne.jp/nishiohirokazu/
http://d.hatena.ne.jp/nyaasan/
http://d.hatena.ne.jp/runfor/
http://d.hatena.ne.jp/smly/
http://d.hatena.ne.jp/suztomo/
http://d.hatena.ne.jp/s-yata/
http://d.hatena.ne.jp/tanakh/
http://d.hatena.ne.jp/tanigon/
http://d.hatena.ne.jp/tkaneko/
http://d.hatena.ne.jp/tomerun/
http://d.hatena.ne.jp/tsubosaka/
http://d.hatena.ne.jp/tsukuno/
http://d.hatena.ne.jp/YasuyukiMiura/
http://d.hatena.ne.jp/wata_orz/
http://rsujskf.blog32.fc2.com/
http://slashdot.jp/~Yak!/
http://sns.atfb.jp/list_diary/1.html
http://tsenda.jp/ideaclip/
http://www.binzume.net/
http://www.f13g.com/
http://www.kmonos.net/
http://www.lesit.com/Joomla/index.php
http://www.y5i.org/

皆さん、はてな好きですね。

ちなみに、日本からの参加者(≠国籍)は、
QualificationRound?通過：184人
Round1通過：93人
Round2通過：36人
です。

紹介記事 †

インターネット上のGoogleCodeJam2008を紹介している記事です。

http://journal.mycom.co.jp/news/2008/06/18/007/index.html

スケジュール †

　Qualificationラウンドは24時間です。出題される３問のうち、小さいセット１つと大きいセット１つに正解(25ポイント獲得)すれば、このラウンドは通過となります。人数制限はありません。
　大きいセットのみで40ポイント以上取っても通過とはならないようです（google-codejamグループより）。ただし、今回は40ポイントや60ポイントの人は居ませんでした。

　ラウンド１は時間帯の公正を期すために複数のサブラウンドがあります。時間帯の選択は参加者が希望でき、２つのサブラウンドに参加できるようです。希望は、登録時（しばらくは変更可能）に２つ選択しておきます。ここで出てくる時間のすべてでサブコンテストが行われるわけではなく、（要望の多い？）３つのサブラウンドのみが行われるようです。各サブラウンドの上位840人、全体で2520人が次のラウンドに進めます。(2007/7/19修正)

　ラウンド２は２時間のようです。
　1000人が次のラウンドに進めます。

　ラウンド３では、各地域（日本であればAsia pacific）で最低50人、全体で500人が次のラウンドに進めます。１地域１会場ではありません。

　Onsite Localsでは、各地域で最低10人で、合計100人が通過できます。

参加資格 †

• 登録時点で13才以上。
• オンサイトラウンドは、2008/9/18時点で18才以上。
• グーグル関係者と、アメリカと仲が悪い国の人には制限があります。

登録 †

とりあえず登録してみましょう。
Googleのアカウントが使えます。

登録すると、練習問題が見られるようになります。
前回とは違うシステムなので慣れておいた方がいいでしょう。
そして、ちょこっとスクリプトでも書いておけば少しの時間稼ぎができます。

Round One timeslots というのは、前述のラウンド１の時間帯のことです。

賞金等 †

ラウンド3での500位以内は、

• Tシャツを貰えます
• 地元のオンサイトのコンテストに進出できます
  • 旅費・宿泊費はGoogle持ちです

ローカルオンサイトの100位以内は、

• マウンテンビューのオンサイトのコンテストに進出できます
  • 旅費・宿泊費はGoogle持ちです
  • 以下の賞金が出ます
    1st Place $10,000 + １０ランチ
    2nd Place $5000
    3rd Place $2500
    4th – 10th Place $1500
    11th – 30th Place $1000
    31st – 50th Place $750
    51st – 75th Place $500
    76th – 100th Place $250

競技ルール †

今年は従来とは違うシステムのようです。
ちなみに去年は開催されていません。

まず、効率的な手順（手動の場合）を考えてみましたので、
それを元に解説していきます。

・問題を見る
・問題・サンプルを元にプログラムを作り実行可能な状態にしておく
・inputをダウンロードする
・プログラムを実行し、outputを得る
・outputとソースコードを提出する

各コンテストでは、３〜６問のアルゴリズム問題が出ます。

問題には、１つ以上のサンプルケースと、小さいinput/outputセット、大きなinput/outputセットが含まれています。

input（入力データ群）をダウンロードして、それを解いたoutput（出力データ群）と使ったコードを提出します。outputにより正否が判断されるようです。答えが正しければ、セットと共に提示されているポイントが加算されます。

小さいセットと大きいセットで、若干ルールが異なります。

小さいセットの場合
ダウンロードから４分以内にoutput（とコード）を提出します。
結果はすぐに出ます。時間が超過するか、間違った答えを提出してしまった場合は、新しいセットをダウンロードして再び回答します。

大きいセットの場合
提出期限はダウンロードから８分間です。時間内であれば、１つの問題に複数回答えられます。最後に提出したものが回答として使われます。
正しいかどうかはコンテスト後に判断されます。

セットには得点が付けられていて、正解したセットの得点が得られます。
同点の場合はペナルティタイムの少ない者の勝ちとなります。

ペナルティタイムは、コンテスト開始から最後の（小さいセットの）サブミットまでの時間に、小さいセットを間違えた回数＊４分を加算したものです。
大きいセットの間違いはカウントされません。

Round2からの変更点

紆余曲折の末、ペナルティタイムの計算方法が変わりました。

時間のカウントが、小セットのみから、大セットを含む最後に正解した問題のサブミット時間に変わりました。

その辺の経緯は Googleグループ google-codejam: The current rule for calculating Penalty Time is not good あたりにあります。

このしくみで注意する点は、ダウンロードは考え始める地点ではないということです。問題を解ける状態になってから、ダウンロード、解答、提出をしなければ時間とポイントを無駄にします。つまり、ダウンロードは解答の提出の段階だということです（手で解くような凄い人は別として）。

また、ペナルティタイムには大きいセットの方は関係しないので、大きいセットは放っておいて小さいセットを順に片付けるのが良いようです。

注：Round2から変更になりました。

アップロードの制限について
アップロードできるサイズ上限　１００ｋB
複数ファイルのアップロードが可能
ZIPファイルのアップロードの場合は、内容が１MB以内

解き方
特に制限はありません。
手で解いた場合は、それがわかるテキストファイルを提出します。

解き方はなんでもアリな感じですが、
他人（コンテスト参加者以外も含めて）と協力してはいけません。
分担等だけでなく議論もダメです。

†

Freenode の #gcj チャンネルで他の参加者とチャットができます。

Qualification Roundの開始５分後から、spectorリンクから観戦することができます。もちろん参加者としてダウンロードやサブミットすることはできません。

練習 †

登録すると、本番に近い環境で
・Practice Problems
・GCJ Beta 2008
が試せます。

ただし、ファイルのアップロードまわりは本番と違うようです。
ZIPファイルと、ソースコードの提出ができません。

Qualificationラウンド †

参加者と通過レベル †

参加者（１問でも投稿した人）は1万人を超えるくらいだったようです。
正確には分かりませんが、10473人から16120人の間で、おそらく下限付近です。

１問（各セット）以上正解した人は7154人で、
通過基準の25ポイント(小セット、大セット各１問以上に正解)は6773人です。
定員はありませんが、結果的に1.5倍以上の競争率があったことになります。

Round1の通過レベルを予想すると、Round1は2520人が通過なので
３問中２問正解（小セット、大セット両方とも正解）がボーダーライン上で
ペナルティタイム勝負です。

今回はDPでしか解けない問題は無かったので、
そのような出題があると若干変わってくるかもしれません。
前回(2006)の感覚だと、次のRound1がQuarificationRound?相当です。

Saving the Universe
5pt 6760/10473 users correct (65%)
20pt 6258/7836 users correct (80%)

Train Timetable
5pt 5076/6516 users correct (78%)
20pt 4408/5491 users correct (80%)

Fly Swatter
5pt 1007/1536 users correct (66%)
20pt 652/1274 users correct (51%)

Round1 †

QualificationRound?は人数制限も時間の制限もほとんどなく、最低限の参加レベルの確認という感じなので、ここからが本番（Roundのカウントも1）です。

人が多すぎるので、３つのサブラウンドに分けられます。それぞれのサブラウンドで840人が通過できます。
各人が２つのサブラウンドに参加でき、１つめのサブラウンドを通過できた人は、残りのサブラウンドには参加できません。

割り当て人数は、1A < 1B < 1C の順で多くなっているらしいです。

各サブラウンドともに15ptがボーダーになっていました。
ただし、ボーダー上の場合はかなり速く解いてないとダメなようです。

小セットは、規模が小さいのでとにかく速く書いたもの勝ちな感じです。
大セットは後回しにして、小セットを渡り歩いて、３問終わってから、
高速化したプログラムで大セットに挑むのが良いようです。

あと、なぜだか知りませんが、問題にストーリーが増えたような気がします。
ストーリーを読むのでも結構時間がかかるので、読み終わったあとに
大して意味が無いことに気がついてがっかりすることもしばしば。

Round1A †

参加者は2567人以上で、
スコアのある人は2394人でした。

通過ボーダーは15pt, 10:31。

Minimum Scalar Product
5pt　2352/2567 users correct (92%)
10pt 1048/2336 users correct (45%)

Milkshakes
10pt 655/1042 users correct (63%)
25pt 312/432 users correct (72%)

Numbers
15pt 577/1925 users correct (30%)
35pt 96/364 users correct (26%)

Round1B †

参加者は2197人以上で、
スコアのある人は1715人でした。

通過ボーダーは15pt, 1:39:09。

Crop Triangles
5pt 1445/2197 users correct (66%)
10pt 457/1287 users correct (36%)

Number Sets
10pt 777/1351 users correct (58%)
25pt 100/448 users correct (22%)

Mousetrap
15pt 610/862 users correct (71%)
35pt 95/387 users correct (25%)

Round1C †

参加者は2255人以上で、
スコアのある人は2240人でした。

通過ボーダーは15pt, 26:27。

5pt 2204/2255 users correct (98%)
10pt 1402/2194 users correct (64%)

Ugly Numbers
10pt 554/1040 users correct (53%)
25pt 82/318 users correct (26%)

Increasing Speed Limits
15pt 398/716 users correct (56%)
35pt 49/312 users correct (16%)

Round2 †

ボーダー予想。
通過人数は1000人なので、Round1のサブラウンドに換算すると333位以内です。

Round1A: 40pt 1:24:00
Round1B: 30pt 1:51:28
Round1C: 30pt 1:49:30

です。これだと、small setを３つこなすのは必須です。

今回は、４問ありました。
ボーダーラインは、20ポイント 1:37:36でした。
A問題を大小共に解けるのが必須で、それに加えてほかの小セットで20ポイントになります。やっぱり、このくらいのラウンドになると、A問題程度は総当りなどせずに最初から大セットが解けるように書いてくるみたいです。

今回は、配点がちょっと特殊で、

となっていました。正答者数からみると、割と妥当な配点（難易度と一致している）だったようです。

C問題を解いているひとが少ないので、敬遠して問題を見もしなかったのだけど、
あとで見てみたら案外簡単でした。
ペナルティタイムのルールが変更になりましたが、大セットも含めて全部解けるような人じゃない限りは、今までと同じく小セットから解いてまわったほうがいいのかも。

Round3 †

オンラインでの最終です。ここで玉砕予定...
４問あるらしいので、運がすごく良ければなんとかなるかな？？

予想通り玉砕しました。
A問題をひたすらコーディングしてたのですが、時間内に動くようにはできませんでした。ちなみに、終了後＋１時間弱で実装できて、それだとlargeも通りましたが、コーディングがあまりにも遅すぎます。

　 †

コメント欄はこのページの上の方にあります。
上の方に行く