2ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

Google Code Jam 2010でオファーをゲットするおっお

1 :就職戦線異状名無しさん:2010/04/23(金) 14:30:58
Google新卒採用スレはあるけど、Code Jam 2009スレと比較すると雰囲気が違うようなので
あちらを荒らすと悪いと考えて別スレを建てることにします。

Googleの主催するプログラミングコンテスト、Code Jam 2010が開催されます。
これはただのコンテストではなく、Participateしてみるとわかりますが採用活動の一環でもあります。

流れ
1.Participateする
2."I want to be contacted about opportunities at Google:"にYes(あるいはSomewhat)と答える
3."Preferred Google office to work at"に好きなオフィス(東京でもMountain Viewでも)を入れる
4.ACRushとか強豪を蹴散らして上位に入賞する
5.Googleから面接に呼ばれる
6.正式オファー

という流れになります。

5/8 08:00 予選ラウンド(24時間だからゆっくり解けばいい、英文読解が遅くてもOK)

5/22 10:00 Google Code Jam 2010 Round1A(A, B, C好きなのに参加、全部受けてもいい)
5/23 01:00 Google Code Jam 2010 Round1B(A, B, C好きなのに参加、全部受けてもいい)
5/23 18:00 Google Code Jam 2010 Round1C(A, B, C好きなのに参加、全部受けてもいい)
続く(32行越えたから割愛)

Google Code Jam 2010 is in Dublin!
http://code.google.com/codejam

関連スレ
Google Code Jam 2009でオファーをゲットするおっお(過去ログ倉庫)
http://namidame.2ch.net/test/read.cgi/recruit/1250571869/

Google新卒採用2011
http://namidame.2ch.net/test/read.cgi/recruit/1266413726/

2 :就職戦線異状名無しさん:2010/04/23(金) 14:39:36
Association Aiming to be ACRush
http://wikis.jp/aaacrush/

「ACRushを目指す会」は、Google Code Jam 2009での敗北経験をばねに、
ACRushになることまたはACRushを生成することを本気で目指す人の集まりです。

http://code.google.com/codejam/contest/scoreboard?c=311101

3 :就職戦線異状名無しさん:2010/04/23(金) 14:43:37
ACRushは2008, 2009と連覇している、あいつ何連覇だよ?
しかも清華大学の学生

4 :就職戦線異状名無しさん:2010/04/23(金) 23:28:50
とりあえずwata倒そうぜ

5 :就職戦線異状名無しさん:2010/04/24(土) 00:42:01
wataは東大生か

6 :就職戦線異状名無しさん:2010/04/24(土) 17:24:42
過去ログ読んでいたら、chokudaiっぽいやつも来ていたな

7 :就職戦線異状名無しさん:2010/04/26(月) 00:16:30
Google SE祈られたからこっちに参戦します

8 :就職戦線異状名無しさん:2010/04/27(火) 23:04:29
建てるのが早すぎる

9 :就職戦線異状名無しさん:2010/04/29(木) 10:56:08
保守

10 :就職戦線異状名無しさん:2010/05/01(土) 17:58:46
ほす

11 :就職戦線異状名無しさん:2010/05/02(日) 01:59:17
今年もたったか。今年こそTシャツ欲しいなぁ。

12 :就職戦線異状名無しさん:2010/05/07(金) 13:25:44
いよいよ明日だ

13 :就職戦線異状名無しさん:2010/05/08(土) 07:57:10
はじまるage

14 :sage:2010/05/08(土) 07:57:54
いよいよ今日だ

15 :sage:2010/05/08(土) 08:01:40
答えあわせって反則かな?

16 :就職戦線異状名無しさん:2010/05/08(土) 09:38:35
B-large、smallが通ったから余裕だろと思ってたらexpireした。

これ、Largeが1発勝負ってのは厳しいなぁ。凡ミスの取り返しが効かない。
まぁみんな同じ条件だといえばそれまでだけどさ。

17 :就職戦線異状名無しさん:2010/05/08(土) 09:39:51
BlじゃなかったClだった

18 :就職戦線異状名無しさん:2010/05/08(土) 10:08:59
>>15
露骨な解答そのものを晒すとかじゃなければいいんじゃないか?

19 :15:2010/05/08(土) 10:18:40
あ、でも各人でinputがまちまち、なのか?

20 :就職戦線異状名無しさん:2010/05/08(土) 10:23:53
相変わらず英語げーだな、Snappersが何であるか知っている人と、知らない人ではコーディング時間全然違うだろう

21 :就職戦線異状名無しさん:2010/05/08(土) 10:42:57
問題を読んだが、ものすごく単純なシーンしか思いつかない
これで本当にいいのか悩む

22 :就職戦線異状名無しさん:2010/05/08(土) 11:41:31
おれはA問題は実質一行でかけたからいいんでね?

23 :就職戦線異状名無しさん:2010/05/08(土) 12:01:15
scoreboard見てそこそこ日本人いて安心した。

24 :就職戦線異状名無しさん:2010/05/08(土) 12:02:35
終わった。予選だとこんなもんか。
google blogにあったチャートのやつとか想定してたお…

25 :就職戦線異状名無しさん:2010/05/08(土) 12:05:49
何問とければいいお?

26 :就職戦線異状名無しさん:2010/05/08(土) 12:14:59
>>22
やっぱ実質1行(IOとか別にして)で書けるよね?

27 :就職戦線異状名無しさん:2010/05/08(土) 12:15:06
33ptだよ

28 :就職戦線異状名無しさん:2010/05/08(土) 12:16:05
>>25
33点以上で通過だと思う
つまり、smallのみ全問正解だと30点で通過できない
small + large1つで33点だから、1つできていればOK

29 :就職戦線異状名無しさん:2010/05/08(土) 12:18:02
Question
Has the statement for Snapper Chain changed?

Answer
Yes.

確かに変わってる

30 :25:2010/05/08(土) 12:22:43
>>27,28
サンクス

large提出前に誰かと答え合わせしたくなるお
こわいお

31 :就職戦線異状名無しさん:2010/05/08(土) 12:30:37
さっきからサーバーエラーがおきまくるのは俺だけ?

32 :就職戦線異状名無しさん:2010/05/08(土) 12:31:50
何かサーバ重くない?
code.google.comを待機していますのまま固まって全然動かない
時間だけどんどん過ぎるのに

33 :就職戦線異状名無しさん:2010/05/08(土) 12:33:24
Error communicating with the server. Make sure you're logged in and refresh the page.

だって、ひどいお

34 :就職戦線異状名無しさん:2010/05/08(土) 12:35:31
ふっかつしたか?

35 :就職戦線異状名無しさん:2010/05/08(土) 12:39:23
TwitterにSnapper Chainの問題の意味がわかりにくいというつぶやきが多い

36 :31:2010/05/08(土) 12:41:01
ふっかつしたお

37 :就職戦線異状名無しさん:2010/05/08(土) 12:43:56
去年も予選中サーバがおかしくなった時間帯あったよな…

38 :就職戦線異状名無しさん:2010/05/08(土) 13:48:58
>>29
Snapper Chainの意味がわからなかったけど、書き換える前の方を読んだらわかった
なんで重要な情報を隠蔽するのかな

39 :就職戦線異状名無しさん:2010/05/08(土) 15:13:39
Fair Warningだけ解答率が低いな

40 :就職戦線異状名無しさん:2010/05/08(土) 15:50:32
>>39
俺には意味わかんない

26000, 11000 and 6000の最大公約数(the largest possible integer factor T)って1000だろ、
T=5000ってどっから出るの?

41 :就職戦線異状名無しさん:2010/05/08(土) 15:58:02
y=4000で
26000+4000 (30000)
11000+4000 (15000)
6000+4000 (10000)
したときに,T=5000 てこと


42 :就職戦線異状名無しさん:2010/05/08(土) 16:11:36
>>41
ありがとう
ということは、4000(答え)を求めないとT=5000はわからないのか

43 :就職戦線異状名無しさん:2010/05/08(土) 16:20:16
だれかA問題を訳して・・・

44 :就職戦線異状名無しさん:2010/05/08(土) 16:39:16
スイッチつきテーブルタップをたくさん繋げる(通電確認機能あり)
最後に電球を付ける
スイッチは全部切っておく

通電しているスイッチのON/OFFを切り替える、を繰り返す

電球はついていますか?

45 :就職戦線異状名無しさん:2010/05/08(土) 16:41:53
>>42
ヒントとしては,実際は T をまず計算しないと y が計算できない,はず.
違うやりかたもあるかもしれないが.


46 :就職戦線異状名無しさん:2010/05/08(土) 16:46:46
俺バカだ、C-Large適当にやったら時間足りなかった

47 :就職戦線異状名無しさん:2010/05/08(土) 16:53:36
指パッチン(ってわかるかな?)すると,自動的にON/OFFが切り替わる,連結可能な延長コードというイメージ.

ひとつひとつは,通電してるときじゃないとON/OFFが切り替わらない,というところをどう考えるかがポイント


48 :就職戦線異状名無しさん:2010/05/08(土) 16:54:09
>>45
ありがとう、その方針でコードを書いています

49 :就職戦線異状名無しさん:2010/05/08(土) 16:56:51
>>46
おれもw

あとBの解き方がわからん。

50 :就職戦線異状名無しさん:2010/05/08(土) 17:09:55
B-Largeも時間足りないかも

51 :就職戦線異状名無しさん:2010/05/08(土) 17:11:32
かも、じゃなくて絶対に足りないorz

52 :就職戦線異状名無しさん:2010/05/08(土) 17:33:50
>>26
chokudai乙

53 :就職戦線異状名無しさん:2010/05/08(土) 17:48:24
>>52
みょんみょん

54 :就職戦線異状名無しさん:2010/05/08(土) 17:50:45
>>44,47
サンクス

55 :就職戦線異状名無しさん:2010/05/08(土) 19:08:57
C-largeにだまされた

56 :就職戦線異状名無しさん:2010/05/08(土) 19:19:44
Cは問題簡単すぎるし、Largeはきな臭いと思った

57 :就職戦線異状名無しさん:2010/05/08(土) 23:05:50
なんでファイル読み込みだけでループするんだろと思ったら
inputをBとC間違えて指定してた
largeだったから気づいたときには終わった

58 :就職戦線異状名無しさん:2010/05/09(日) 04:18:39
AのON/OFFって一回で一個しかかわんないの?
なんか深く考えすぎて何もわかんなくなった。。。

59 :就職戦線異状名無しさん:2010/05/09(日) 04:58:04
When you snap your fingers -- making a clicking sound -- any Snapper receiving power at the time of the snap toggles between the ON and OFF states.

とかいてあるが?

60 :就職戦線異状名無しさん:2010/05/09(日) 05:53:08
>>58
通電しているのが一斉に切り替わる
つまり,対象のSnapper S(i)(1<=i<=N)より電源に近いほうの S(j) (j<i) に1つでもOFFのものがあれば S(i) まで通電しないので,その S(i) の ON/OFF は切り替わらない


61 :就職戦線異状名無しさん:2010/05/09(日) 06:02:14
>>59,60

あんがと。
気分転換にCやったら処理中にPCおちて送信できなかったよ。。。

62 :就職戦線異状名無しさん:2010/05/09(日) 06:46:38
>>58
問題文書き換えているけど、書き換える前は

When the Snapper is in the ON state and is receiving power from the input socket, then the connected device is receiving power as well.
When you snap your fingers, the Snapper toggles between the ON and OFF states.

Of course, snapping your fingers only has an effect if the Snapper is plugged in and is receiving power from the socket.

と書いてあって、これで意味がやっとわかった

63 :就職戦線異状名無しさん:2010/05/09(日) 08:05:17
C-large落としたけど、えらそうに解説してみる。

64 :就職戦線異状名無しさん:2010/05/09(日) 08:07:28
解説してくれ
前の計算結果を利用して、全部計算しなければOK?

65 :就職戦線異状名無しさん:2010/05/09(日) 08:10:31
まずA。

[考え方]
ONのsnapperを1、OFFのsnapperを0として、左端をコンセント、右端をライトとしてみる。
例えばsnapperの状態が下記のとき、「*」の範囲まで電気が通じている。
(左端から見て、OFFである最初のsnapperまで電気が通じる。)
全部通電するとき、すなわち111111111111111のときはライトがオンになる。

111111001010011
*******

ここでsnappingすると、通電している範囲のon/offが切り替わるので
000000101010011となる。

ここで、この0/1を左右反転してみると、このsnapperの動きは
単なる2進数のインクリメントであることに気づくかどうかが鍵。

コレに気づけば、Kの2進数表記の下位N桁が全部1であるかどうかチェックするだけ。
以下の判定分で終わり。>>22,26は俺じゃないけど、1行とは多分下記の判定文のこと。
( K & ((1<<N)-1) ) == ((1<<N)-1)



66 :就職戦線異状名無しさん:2010/05/09(日) 08:11:41
ああ、ごめん、メインはA・Bの解説だ。Cも一応書いてみるけど、自信ない。


67 :就職戦線異状名無しさん:2010/05/09(日) 08:15:37
なるほど

68 :就職戦線異状名無しさん:2010/05/09(日) 08:17:52
Bに期待

69 :就職戦線異状名無しさん:2010/05/09(日) 08:19:02
次にB。

[考え方]
yより先にTを求めることが出来る。
なので、このスレで>>42の書き込みがあったとき、これにつられる人
出ないかな…とちょっと心配してた。

t1+y, t2+y, t3+y が最大公約数Tを持つとすると、ユークリッドの互助方法を思い出すと
(t2+y)-(t1+y) = t2-t1も同じTを最大公約数を持つ。同様に、t3-t1、t3-t2も同じ。
よって、t2-t1とt3-t1の最大公約数を求めれば実はTが求まる。
(t3-t2は、(t3-t1)-(t2-t1)=t3-t2なので、t2-t1とt3-t1の最大公約数と同じ公約数を持つ。よって計算不要)

もっと数が多い場合も、例えばt1が一番小さいとして
t2-t1、t3-t1、t4-t1、t5-t1…の最大公約数を求めればよい。
あとはt1+yがTになるようy = T - (t1%T) を求めればよい。
(t1がTの倍数の時上の式はy=Tになるけど、その場合はy=0にする)


70 :就職戦線異状名無しさん:2010/05/09(日) 08:19:48
26000000 11000000 6000000なら、
26000000-6000000=20000000と11000000-6000000=5000000の
最大公約数5000000がT。


71 :就職戦線異状名無しさん:2010/05/09(日) 08:22:21
感想だけど、この問題は値域がちょっとひどいと思う。
明らかに32bit/64bitに収まらないんだよね。

過去の問題でも、値域が10^50なんて問題もあったけど、
去年のnext_permutationの様に数字を文字列として扱えるものだった。
だけど今回は明らかに剰余計算など多倍長整数の演算を用いる。
これ、多倍長整数サポートのない言語だと、多倍長の処理にてこずるので悪問だと思う。
俺はBだけ多倍長整数が仕える言語でやったり、その言語を探す時間の方が
コード書くより速かった。

「多倍長ぐらい自前で書け」「そんなライブラリ事前に用意しとけ」
といわれればそれまでだけどさ。


72 :就職戦線異状名無しさん:2010/05/09(日) 08:22:53
3つやっちまった

ABS(11 - 0), ABS(10-0), ABS(11-10)の最大公約数

73 :就職戦線異状名無しさん:2010/05/09(日) 08:24:19
>>71
そういう言語を使えばOK
JavaとかRubyとか

通過した今回初参加の人に向けて言うと、次は時間が短いからライブラリはできるだけ揃えておき使い方を一通り確認しておくべき

74 :就職戦線異状名無しさん:2010/05/09(日) 08:24:55
次にC。

[考え方]

smallは題意に従って書くだけ。
ただ、largeではRが10^8とかとんでもない値になっているので、
smallで通ったと言ってそのままlargeを通すと時間切れになる。

俺もこのパターンで時間切れやらかしたorz


そもそもジェットコースターを動かすとか言う題材でありながら、
最大が1日1億回とかふざけてるだろ…orz


75 :就職戦線異状名無しさん:2010/05/09(日) 08:27:24
>>71
>多倍長の処理にてこずるので悪問だと思う。

64ビットじゃ足りないと問題に書いてあるからそれがポイントだと思うよ
前回のnext_permutationと同じタイプの問題で、手抜きできる能力を見る問題

76 :就職戦線異状名無しさん:2010/05/09(日) 08:29:30
>>69
ところでTがわかった先、どうやってyもとめんの?

77 :就職戦線異状名無しさん:2010/05/09(日) 08:29:39
で、largeを通すには何らかの高速化が必要。
一番簡単なのは、列をたどらなくても、1回で何グループ・何人が
コースターに乗るか最初に調べておくことかな。

例題にあったR=6、[2,1,1,4]の例だと、
[2,1,1,4] → 3グループ,4人
[1,1,4,2] → 3グループ,6人
[1,4,2,1] → 2グループ,5人
[4,2,1,1] → 2グループ,6人

後は上に従ってR回ループをまわすだけ。
これでも最近のCPUなら十分8分で終わるようだ。


もう少し賢くやるなら、例えば
「コースター10回でグループが3周するから、R=1005だとしたらグループ300周分と
コースター5回分」みたいにすることかね。
これだとR回のループが要らない。


78 :就職戦線異状名無しさん:2010/05/09(日) 08:31:05
>>75
まぁそうではあるんだけど、今回の本題は
「差の公約数を取ればいいことに気づけば、Tが求まる」
という部分かなと思ったので、それと外れる部分で変な苦労するのは
どうなんだろうな、と。

79 :就職戦線異状名無しさん:2010/05/09(日) 08:34:45
「Cは、Small通った、Largeいける!」

時間切れ死亡

の人が多く出た感じだね。smallに比べ、largeの正答率が低い。
Bはsmallでてこずった人が多いけど、smallさえ解ければ、あとは多倍長さえ
どうにかなればlargeも解けるのでlargeの正答率が高い。


80 :就職戦線異状名無しさん:2010/05/09(日) 08:35:02
>>78
そっか

アルゴリズムが洗練されていればスクリプトでも問題ないからPythonとか使うといいと思った
力押しでC++と高速CPUで結果を出す戦略もありだと思うけど

81 :就職戦線異状名無しさん:2010/05/09(日) 08:37:23
俺連投してるけど、多倍長を上位陣がどうしてるか見てみた。
1位 - C++で多倍長classを組み込み
2位 - Cで多倍長処理を組み込み
3位 - C++でライブラリ(gmpxx)利用
4位・5位 - JavaでBigInteger利用

1位と2位はあの速度で多倍長実装したとは思えないから、
既にコードを用意して、コピペして使うという感じかな?
TopCoder上位常連みたいだし、そのぐらいしてそうだ。

82 :就職戦線異状名無しさん:2010/05/09(日) 08:40:10
GoogleのContest Analysis出たな。
確かにBは多倍長ない言語は大変かもね〜と書いてある。

83 :就職戦線異状名無しさん:2010/05/09(日) 08:44:11
これ99点でRound2いけたのか。
ちゃんとやっときゃよかった。

84 :就職戦線異状名無しさん:2010/05/09(日) 09:04:10
>>83
ソースは?

85 :就職戦線異状名無しさん:2010/05/09(日) 09:06:15
「上位3000人がRound2」→B-largeも取れば3000位、と勘違いしてないか?

86 :就職戦線異状名無しさん:2010/05/09(日) 09:10:09
ああ、来てたメール読み間違ってた。

Fully solve one problem (Small and
Large) to advance to Round 2.

87 :就職戦線異状名無しさん:2010/05/09(日) 09:26:10
自分も C-large で死亡の 76点だが,提出後,>>77 と同じような考え方で,あらかじめ「そのグループが先頭のときに何人乗れて,何グループ分移動するか」みたいなデータを計算してから,Rループする方法に直した.
これだと,C-largeもあっさり動いて,practiceでもcorrectになった.


88 :就職戦線異状名無しさん:2010/05/09(日) 09:27:40
>>86

いや、そもそもメールが間違いだと思う。
to advance to Round 1 のはず。

89 :就職戦線異状名無しさん:2010/05/09(日) 09:28:21
去年のスレにも出てたけど、2010のStatisticsも準備中みたいな感じね。
http://www.go-hero.net/jam/

90 :就職戦線異状名無しさん:2010/05/09(日) 09:36:20
>>89
あ、ちょうど今2010のやつ公開されたみたいだ。

91 :就職戦線異状名無しさん:2010/05/09(日) 10:25:20
日本人前回よりもだいぶ増えたな。

でもこの統計見てると、中国とインドの人数の多さにビックリするな。
インドは去年は余り上位に残らないけど、中国やロシアは上位層が厚すぎる。

コレだけで判断するのはよくないけど、この分野は中国バカにできんよなぁ…


92 :就職戦線異状名無しさん:2010/05/09(日) 12:46:54
>>89
D言語がいて驚いた

93 :就職戦線異状名無しさん:2010/05/09(日) 12:53:28
予選だと色んな言語で遊ぶ人もいるよね。
アセンブラが1人いるけど、「Perlだと遅いからアセンブラで書く」
とかコメント書いてる。
A-largeにそこまで速度いらんだろうに…

94 :就職戦線異状名無しさん:2010/05/09(日) 13:28:45
>>77
俺はコースターを走らせる前のキューの状態(ハッシュ)を記録しながら動かして
同じ状態が出てくるまでやった。
走らせているときは、コースターに乗った人数と延べ人数も記録。
同じ状態が見つかったということは、コースター何回か走らせているうちに
定常状態におちてループするってことなんで
ループ前の人数(ループが始まった状態までに乗った人数)
+ループ中の人数(残り運行回数/ループ中コースター数 *ループ中の人数)
+ループ後の人数(残り運行回数%ループ中コースター数 分のループ中人数)
って感じでだした。
ループが見つかる前に運行が終わったとかも場合分けしたけど、
これなら、数秒程度でlargeクリアできたよ。

95 :就職戦線異状名無しさん:2010/05/09(日) 18:29:42
>>94
定常状態におとすやりかたいいね.参考になった.
自分でもやってみよう


96 :就職戦線異状名無しさん:2010/05/09(日) 19:14:03
codejamの予選通ったって面接でアピールして意味あるかな?


97 :就職戦線異状名無しさん:2010/05/09(日) 20:35:46
正直全然アピールにならんだろ。

98 :就職戦線異状名無しさん:2010/05/09(日) 21:30:12
会社によってはまったくプログラム書けないやつを採用するから
多少は役に立つかもな


99 :就職戦線異状名無しさん:2010/05/09(日) 21:51:17
そういうことに興味をもって取り組んだ・取り組める
というような感じのアピールならありなのでは?

結果云々はOnsiteでDublin行ってきたとかなら。

100 :就職戦線異状名無しさん:2010/05/09(日) 22:01:43
Onsiteとか無理…
予備のエピソードとして用意しとくくらいにしとくよ

52 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.02.02 2014/06/23 Mango Mangüé ★
FOX ★ DSO(Dynamic Shared Object)