Google Code Jam 2006

「世界のトッププログラマ達に勝てる自信があるかい?
　これが、その力を証明するための絶好の機会だ。」

http://www.google.com/codejam/

Google 主催の世界的なプログラミングコンテスト。
上位 100 人は Google New York Office で行われる決勝に行ける。
優勝賞金は 1 万ドル。Google 社員になるチャンスもあり。

■ 競技内容

問題がいくつか与えられ、それを解くプログラムを一定時間内に書く。
問題ごとに配点があり、速く解くほど高い点がもらえる。各問題の合計点を競う。
ただしプログラムにバグがあったり、遅すぎたりするとその問題に関しては 0 点。
使用可能言語は Java, C++, C#, VB.NET, Python。

■ 参加資格

2006 年 9 月 5 日現在で 13 歳以上ならオンラインのコンテストに参加可能。
2006 年 9 月 5 日現在で 18 歳以上なら決勝まで参加可能で、賞金ももらえる。
ただし Google 社員・今夏のインターン参加者・その他関係者は参加できない。

■ スケジュール (日本時間)

2006-08-14 (月) 22:00 参加登録開始
2006-09-05 (火) 22:00 参加登録締切
2006-09-06 (水) 01:00 Qualification Round 開始
2006-09-07 (木) 01:00 Qualification Round 終了
2006-09-14 (木) 23:00 Round 1 (上位 1000 人参加) 開始
2006-09-19 (火) 23:00 Round 2 (上位 500 人参加) 開始
2006-10-27 (金) [時間未定] 決勝 (上位 100 人参加)

■ 参考リンク

TopCoder
http://www.topcoder.com/tc
　Google Code Jam で使われているシステム。毎週コンテストが開かれている。
　練習はここがオススメ。上位の参加者のレベルも分かる。

GoogleCodeJam2005
http://www.icefree.org/~vvp/96.html
　昨年度のコンテストに関する、日本人参加者による Wiki。

4TopCoder
http://4topcoder.blogspot.com/
　TopCoder で練習している人のブログ。
　ふいんき (何故か変換できない)・問題の傾向・必要な能力が分かる。

Google Code Jamに挑戦してGoogle本社に行くスレ
http://pc8.2ch.net/test/read.cgi/prog/1123937236/
　昨年度のスレ。DAT 落ち。

お、今年もｷﾀ─ｗｗﾍ√ﾚｖｖ〜(ﾟ∀ﾟ)─ｗｗﾍ√ﾚｖｖ〜─ !!

宣伝age

去年チャレンジしようと思ったが、周りの人間のレベルの高さと、
英語力不足であえなく断念。TOEIC700ごときじゃ太刀打ちできなかったよorz

>>7
レベルの高い奴がいるのは確かだけど (それも「非常に」高い)、
英語力は十分足りてると思うよー。Google のエンジニアの
応募条件で求められてる英語力も「TOEIC 700 程度が目安」だし。

>>8
テストステージみたいなやつ？やってたんだけど、読んでる間に回答あがってたから。

>>9
Round 1 以降のことかな？
速い奴は本当に速いからねぇ…。

回答時間３分とかあり得なくね？

上には上がいるとさとったな、この大会で
俺もうだめぽ

なでしこでやらせろよ

　 　∩＿＿＿∩　　 　　　　　　｜
　　 | ノ＼　　　　 ヽ　 　　　　　　|
　　/　　●゛　　● |　　　　 　　　|
　 |　∪　　( _●_)　ミ　 　　　　　j
　彡､　　　|∪|　　 |　　　 　　　 Ｊ
/　　　　 ∩ノ ⊃　 ヽ
(　 ＼　／ ＿ノ　|　 |
.＼　“　　／＿＿|　 |
　　＼ ／＿＿＿ ／

Practice Roomの問題が難しい件についてｗｗｗ

>>11
問題文を全部読んでないだけだろう
慣れればどこを読み飛ばせるかとかわかってくる
それでも3分は無理だな、俺は

>>16
論理が破綻してますよ。

>>17
それに気づけない俺は日本語を勉強したほうがいい？

俺も日本語勉強しなきゃ

ああ、、全然わからん・・駄目だこりゃ

そんなに練習問題が難しいのか…

>>21
いや、多分俺が馬鹿なだけだよ

しかし去年はPractice Roomに去問がたくさん入ってた気がするんだが。
今年は3問だけか。

s/去問/過去問/

スコア1600ってすげー

初めて参加してみる。




おお、
なんか起動した。

問題最初簡単に見えたけど
なかなか難しいな。

練習部屋にあるのは
Google Code Jam Europe 2006 Round 1
の問題セットらしい。

Qualification Round の問題よりは当然難しいわけね。

>>28
安心










ﾃﾞｷﾙﾊｽﾞﾈｪﾀﾞﾛ！！！ｗｗｗ

練習問題の500点問題のExamples (2 の答えが４に思えてしまう俺は負け組みか…

aaaabbbaxxx
↓
aaaa
abbba
xxx

だお　（ ＾ω＾）

ああ、全部別々にやるのかと思ってたｗ

>>31のおかげで解ける気がしてきた thx
でもQualification Roundのときは１人じゃん orz

>>32
英語読めてないな
You will be given a String[] str.
Concatenate the elements of str to form one long string,
and return the number of maximal palindrome substrings contained in that string.
と書いてあるぞ

500はできたけど250が何言ってるのかわかんね('A`)
誰か教えてくれ・・

'B'同士のマンハッタン距離のうち、最も長いものを返せ。

>>34
俺TOEIC780だけど、それ読めないわ orz
1個でも類推付加な単語があると致命的だな

>>36
？？？
それSalesRoutingじゃなくね？

>>38==35？
どの問題なのかはっきり教えてくれ。250や500じゃ時間がたつとどれやら分からなくなる。

250ってTSPの変形問題じゃないの？

>>39
このスレの文脈で「250」というと
Google Code Jam 2006 の Practice Room (1 - 10 共通) の
250 点問題 (SalesRouting) 以外ないような気がするんだけど…
（俺は他に練習問題があるのを見落としてるんだろーか？）

俺がわからんって言ったのは
SalesRoutingです

スコアってマイナスになるのかｗ

ミスを突かれたんだろう

他の人のC++のコード見てたら
<?=
って出てくるんだがなんだこれｗ

>>37
まさかconcatenateかpalindromeが解らないのではあるまいな。

>>46
類推付加が分からないおれはどうしたらいいですか

他人のコードからテクニックを盗め！

俺はまず英語がわからん。そこで思いついた
英語を日本語に直すプログラム作ってもっていけばいいじゃんｗ

試しにやってみるから誰か手頃な問題を翻訳して。
それでムリだと思えば、英語勉強しなくてもいいし

>>49
俺Excite翻訳利用して翻訳するソフト作ったｗ

>>51
ちょｗｗｗｗｗｗｗｗおまｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ天才ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

ぬルポ？

>>45
GCC 拡張。
a <? b は min(a, b)
a >? b は max(a, b)
a <?= b は a = min(a, b);
a >?= b は a = max(a, b);
に相当する。ただし今後のバージョン (gcc 5?) では使えなくなるらしい。

俺が参加したら余裕で優勝
ただ英語が読めないだけ
ぬるぽ

>>53
>>55
ガッ

>>46
なぜ「まさか」になるのかわからんが、palindromeの意味が分からないのでお手上げ。
もちろん辞書引きゃわかるけど、そんなことやってたら絶対に勝ちあがれない。

ちなみに、類推不可な。

>>57
アメリカ人だって意味のわからない単語がでてきて英英辞典使うというのに
日本人が全く辞書を使わずに勝ち残ろうってのか？

まぁ150word/minくらいのスピードで読めないと苦しいだろうね。

>>58
参加してみてからほざけ

>>58
あのレベルの英文を読むのに、辞書が必要なレベルだとしたら、勝ち残るのは無理。

つうかpalindromeは前の文で説明されてる

どこまで行くことが前提なんだろうｗ
Round 1なら辞書使いながらでも行けると思うけどね

辞書引いてる間に回答がポコポコ上がっても、自己嫌悪にならない奴なら可。

単語10個ぐらいALCとかで調べてもたかが数分っしょ…
アルゴリズム分かってちゃんとコード書ければ十分勝ちあがれるよ。

>>65
無理

単語3個くらいなら
問題読んですぐコード書ける人なら突破できるかもね

http://4topcoder.blogspot.com/2006/08/google-code-jam-2006-practice1.html
(SalesRouting)

Registrationですでに辞書使ってるのですがorz

Institution name ってなに？
現在B3だけど，Highest degree completedはassociatesでいいのかな

>>69
英語圏の人も混乱してるくらいだから気にする必要ないよ。
http://forums.topcoder.com/?module=Thread&threadID=512577&start=0

運営側の回答によると
Institution name は "Highest degree completed" を授けられた学校。
Higest degree completed は、あなたの場合 Secondary school じゃないかな?
(短大行って短期大学士をとったなら Associates だろうけど)

本当に凄い人は解いてないのね・・

TopCoders1位の人って賞金で生活してるのかね…

TopCodersが閉鎖したら終わりか

>>72
マジレスすると、奨学金だろう。
http://www.cs.purdue.edu/homes/czajkat/czajka.html
でもコンテスト関係で2000万円くらいは稼いでるっぽいね。

>>74
ｽｺﾞｽ
こういう人は大抵、ただ手が速いだけでなく学術的・創造的な分野でも
才能を発揮させたりするから、まったく神は不公平だ。

才能なんてのは他人に嫉妬する人間の口癖だと俺は思うよ
何かの分野で力を発揮したければ努力すればいい。それだけだ

才能は、口癖だ。
？？？？？

どこかで才能の差はでるかもしれないが、大抵の奴はその差がでる前に負けている

QualificationRoundって1時間以内でできるだけ沢山問題を解けってこと？
それとも一問１時間？

1時間で2問。

>>80
thx

QualificationRoundまであと１週間か

TopCoder で練習しているんだけど、
Qualification Round の練習ってどの問題でやればいいんだろう？

>>83
Qualification Roundは問題を解くだけだからどれでもいいんじゃね？
難易度は部屋によって変わるわけだし

>>83
大体
　QR の 250 は TopCoder SRM Division 2 の 250〜500 くらい
　QR の 750 は TopCoder SRM Division 2 の 1000 くらい
だと思う。

翻訳するのだけで、３０分はかかるのだが
日本語で問題だしてくれないかな？

（；＾ω＾）

既に16000人ほど参加登録してるそうな。
http://googleblog.blogspot.com/2006/08/dont-miss-this-chance-to-prove.html

参加登録は今日 22:00 (JST) までですよー age

明日の夜１時からが本番だよね？

>>90
だね。(もちろん明日1時ぴったりに始める必要はないけど)
Good luck!

gl All!
予選が終わったらまた集合しよう!

あと２時間ぐらいで開始か

眠いから、明日起きてから少し経ったくらいに始めるよ。

みんなgl!

おれは開始と同時に始めるよ。
明日もふつーに会社あるので、なるべく朝までにやっつけたい。

もうやってる奴やってるんだろうな。
俺は明日にしよう。

ロシアの殺し屋おそろしや

え？　もう始まってるの？

>>98
ま　だ　慌　て　る　よ　う　な　時　間　じ　ゃ　な　い

今から 22.5 時間以内に解き始めれば OK。

それでも（ｒｙ

一応時間内に2問とも解けた
さてエロ画像でも見て寝るか

標準CとVB6しか使ったことない旧世代の俺もチャレンジしてみた。
スタートしてから50分くらいSTLなるものの勉強に費やした。オワタ、、、
250点問題をsubmit押す直前に時間切れ、、、コードは間に合ったのに、、、

来年に向けて勉強しなおします

カードを並べ替える250点の問題
どうしてもマシンに掛ける回数が一回合わない。
ExamplesのReturnだと一回少ないように思うのだけれど．．．
英語が読めていないのか？

だいたいあってるなら、条件とか読み落としてるのかもしれない

>>103
俺と同じ勘違いしてない？
最初にシャッフルに書ける入力は[1,2,3,,,m]。
シャッフルの入出力のリストと、シャッフル順序のリストは完全に別扱い。
シャッフル順序は最初から最後まで固定。

■■■■■■■■■■■■■■■■■■■■■■■■■■■■
9/7 1:00 までは問題の内容に関する議論をここでしてはまずい
■■■■■■■■■■■■■■■■■■■■■■■■■■■■

age

dame

active contest
quolification set ?
を選べばいんだよね
Emploee Competition
とかいうのは関係ないよね？

you are not assinged って表示されるけど
順番待ちってこと？

オレには２５０点問題一つで精一杯だ・・・
他の奴らがんばってくれ

>>110
important messageを嫁

>>110
chatで、/room [自分のID]ってやって、自分にassignされた部屋に入れ。
俺はもうダメだが、みんなガンガレ！

今までと同じシステムだったはずなのに不具合がでてくるとはな
同じシステムを使ってる他のコンテストでは問題なさそうなのに…

>>114
まあシステムも時折更新されてるみたいだから、
バグ入れちゃったのかも。予選ラウンド中は
システム再起動するわけにもいかないだろうし。

皆おつかれー。
去年と比べると大分難しくなってるね…。

とりあえず各 Set でどの問題が出たのか気になる。
Set 4 は 250 が SquareCounting, 750 が PermanentComputation だったんだけど。

あ、もう他の参加者のコード・問題が閲覧できるのか。

Set 1は既にシステムテストが終わってるな

Bishop解説キボンヌ

>>Bishop
8クイーンみたいなやつ。クイーンではなくk個のビショップを配置する。
ボートは vector<string> で与えられる正方形。ただし'#'の場所には配置できない。
んで、配置可能なパターン数の「下４桁」を返す。

>>119
DP or メモ化再帰で全部数える。

Bishop の利く方向は二種類 (傾き 45 度, 135 度)。
各方向について、盤面を貫通する線は高々 8*2 - 1 = 15 本。
そこで、45 度の線のうちどれが既に埋まっているか (2^15 通り) を覚えていきながら、
135 度の線を順に辿って Bishop を配置していく。

…という説明で伝わるかなあ。
Set 2 トップの kalinov のソースとかが分かりやすいかも。

あと、チェス盤の黒マスと白マスは絶対に干渉しないので、
別個にカウントして積をとるというのもアリ。

解説サンクス

この得点ってどういう基準で減点されてくんだ？

お前ら System Test 終わりましたよ。
ﾃﾗｱｶｽ

>>124
計算式がある。
　得点 = 配点 * (0.3 + (0.7 * 制限時間^2) / (10 * 解答時間^2 + 制限時間^2))
　http://www.topcoder.com/tc?module=Static&d1=help&d2=ratedEvent#score

可視化するとわかると思うけど、正規分布の半分みたいな形のグラフになる関数。

なるほど。サンクス

両方赤

がっくし

Country: Japan で、暫定 200 位以内の人

Set 1: Iris, nakajima, shakaimo, Vizetha, ysn, yuichi
Set 2: nya, phoenixstarhiro, toshitoshi
Set 3: bakina, haskell-master
Set 4: ihi, inazz, Otaku, xhl_kogitsune, ymatsu, yuizumi, yuu
Set 5: gentoo, kik

ちょｗｗｗｗ東大勢多すぎｗｗｗｗ

>>129
全員開いて調べたのか？お前の暇さに乾杯（完敗）

>>131
八つ当たりか（ ´_ゝ｀）ﾌﾟ

>>131
各SetにRegistrants一覧表があってCountryでソートできるんで、
Division Summaryと照らし合わせてチェックしました。
10分くらいでできたお（ ＾ω＾）
まあ、暇なのは否定しないけどｗ

今回は日本からの参加者多かったね。数えてみたら150人くらい居た。

結局ICPC方面で強い人ばっかりが残った印象があるな。

確かに。まあ普通にソフトウェア書いてるだけだと
DPなんて使わないしなあ。

DPくらい常識だろ

TopCoder Collegiate Challenge
http://www.topcoder.com/tc?module=Static&d1=tournaments&d2=tccc06&d3=alg_description

DPって何？

dynamic programming

日本語だと動的計画法

ああ、なるほど、ありがとう

動的計画法？？分かりやすくガンダムに例えてくれ

>>143
偉い人にはわからんのです

一度、問題を読んだ後、違う問題にかえられるかなと思って部屋から出て
もう一度入るのに手間どって２０分ぐらいロスしてしまった。
悲しすぎ

TopCoderスレの方が良かっただろうか？
来る人が減りそうだがw

>>146
TopCoderスレってどこ？

>>147
ない、Google Code Jam単発のスレよりもTopCoderスレを立てた方が良かったのかなーと思った

個人的にはTopCoderスレがあるとうれしいけど、
TopCoderと2ch両方やってる人ってかなり少ない気もするからなぁ…

STLのiteratorを使ったコードが
VCではコンパイル通るのにGoogle Code Jamでは通らなかった

どんなコード？？

void fun(std::string::iterator &it)
{}

std::string input;
fun(input[3])

こんなかんじ

string::operator[] の戻り値の型はイテレータではない
コンパイル通らなくて当然

というかVCでコンパイル通るのが信じられない
string::iterator はどういう定義になってるんだ？

Round 1 の問題って TopCoder のどの辺？

Qualification Round の難易度が既に去年と大分違うから何とも分からないけど、
たぶん SRM Division 1 と同じくらいじゃないかな。それ以上難しくすると
100 人を精度よく選抜できなくなる気がする。

そういや Round 1 って時間どれだけかかるの？
Rules 見てもよく分からないんだが

確かに Rules には書かれてない気がする…
コーディング 75 分、休憩 5 分、撃墜 15 分、のはずだが。

あ、Instructions に 75 分って書いてあるね

さー今日だぜー

うほ

　　∧＿∧ 　+
　（0゜・∀・）　　　ﾜｸﾜｸﾃｶﾃｶ
　（0゜∪ ∪ +
　と＿_）__）　+

　　　　　　☆ ﾁﾝ　　　　　ﾏﾁｸﾀﾋﾞﾚﾀ〜
　　　　　　　　　　　　　　　　　　　　　　　　ﾏﾁｸﾀﾋﾞﾚﾀ〜
　　 　 　 ☆　ﾁﾝ　　〃　 ∧＿∧　　　／￣￣￣￣￣￣￣￣￣￣￣￣￣
　 　 　 　　ヽ　＿＿_＼（＼・∀・）　＜　System Test まだ〜？
　 　 　 　 　 　 ＼＿／⊂　⊂＿ )　　 ＼＿＿＿＿＿＿＿＿＿＿＿＿＿
　 　 　 　 　 ／￣￣￣￣￣￣ ／|
　　　　　　　|￣￣￣￣￣￣￣|　 |
　　　　　　　|　　CodeJam　　 |／

乙

彼

日本勢暫定500位まで

023 ihi
024 xhl_kogitsune
090 kik
197 yuichi
205 nya
252 inazz
323 toshitoshi
344 yuizumi
403 phoenixstarhiro
471 yuu
482 nakajima

知り合いが２人居る。。

どう見てもICPCな人たちです。

知り合いがn人居る。。

そしてそのｎは全員、日本人内ランキングと同じになりました。

ソースを見てみたいんだけど、
これユーザ登録しないとダウソできないの？

そう

さてさて、誰かニューヨークに行けるんだろうか。

行きたい！

orz

約一名おめ

おめ！！！！！！！！１１１１
ネ申

　 _ 　∩
(　ﾟ∀ﾟ)彡　nyaおめ！　nyaおめ！
　⊂彡

import java.util.*;

public class FirstError {
public int firstBad(String frac){
for(int i=1;i<=frac.length();i++)if(!check(frac.substring(0, i)))return(i-1);
if(frac.matches("^[0-9]+/[1-9][0-9]*$"))return(-1);
return(frac.length());
}

boolean check(String sub){
if(!sub.matches("^0$") &&
!sub.matches("^0/$") &&
!sub.matches("^0/[1-9][0-9]*$") &&
!sub.matches("^[1-9][0-9]*$") &&
!sub.matches("^[1-9][0-9]*/$") &&
!sub.matches("^[1-9][0-9]*/[1-9][0-9]*$"))return(false);
Scanner s=new Scanner(sub);
s.useDelimiter("/");
while(s.hasNextLong())if(s.nextLong() >= (1L << 31))return(false);
return(true);
}
}

あ、送信してしまった。
250 正規表現使えばちょーよゆーorz

ついでに 1000 も最初 MST のアルゴリズムで解こうとしてたし、
もうアフォかと、さて辛い日常に戻るか…。

これすげーな。

long howMany(int k) {
　long a = 1, b = 0;
　for (int i = 0; i < 32; i++) {
　　if ((i & (1 << i)) != 0)
　　　a += b;
　　else
　　　b += a;
　}
　return a;
}

>>180
最適化されると定数を返すだけの関数になりますけど何か。
仮引き数を使用していませんが何か。

写し間違ってた。

long howMany(int k) {
　long a = 1, b = 0;
　for (int i = 0; i < 32; i++) {
　　if ((k & (1 << i)) != 0)
　　　a += b;
　　else
　　　b += a;
　}
　return a;
}

nyaがニューヨークでのチャンピオンシップに行けるの確定？？？

まだ正式な通知は来てないかもしれんけど、行けない理由がない。

おめ

>>178
つ［123456789012345678901234567890/1］

>>186
？？？ それで失敗する？

>>182
そのコードは教科書に載ってるだろ。俺も知ってる。

・・・というのは僕の勘違いでした。吊ってきます。

そもそも何をするコードなのだ？>>182

>>182
別になにもすごくない。

>>190
Round 1 の 500 点問題 (BadBinary) を解くコード。
内容は <http://www.kmonos.net/wlog/65.html#_0036060915> など参照。

>>191
あの問題からこのアルゴリズムを短時間で思いついたら結構すごいと思うんだけど…

>>192
f(2n+1) = f(n)
f(2n) = f(n) + f(n-1)
てすぐ分かるじゃん。
あとはフィボナッチみたくやればいい。

他人の解説を見ればそりゃ即答できなければまずい問題ではあると思う。
問題文を見たときにすぐ気づけるかは知らん

スレ主がいるかどうかは知らないが
このスレはファイナル終わったら過疎って DAT 落ちの運命なのか？

どうせなら TopCoder のコンテスト総合にでもしちゃわないかとふと思った

>>195
>>146-149

Single Round Matchまで手をだしている人が数名いるのは確かだな

最近 Code Jam の影響で TopCoder 人口が増えた希ガス。

僅かに増えたな

で、誰が勝ったん？
Petr? tomek?

>200

http://googleblog.blogspot.com/2006/10/this-years-codejam.html

Petr

Tシャツｷﾀｺﾚ

ま　た　P　e　t　r　か

コンテストではよくあること

風の息づかいを感じていれば，nya にもチャンスはあったはずだ。