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

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

Google Code Jam 2004

1 :デフォルトの名無しさん:04/09/16 12:31:13
今年も来たぜ
実況中
問題ネタばれOK
総力を結集して1000点問題を解こうぜ


2 :デフォルトの名無しさん:04/09/16 12:31:50
まずは匿名アカウントで問題をここに貼り付けからだな。

3 :デフォルトの名無しさん:04/09/16 12:32:56
http://www.google.co.jp/codejam/



4 :デフォルトの名無しさん:04/09/16 12:35:45
http://d.hatena.ne.jp/kataho/20040911

5 :デフォルトの名無しさん:04/09/16 12:36:07
↑ルールなど

6 :デフォルトの名無しさん:04/09/16 12:39:50
もう解いたやついる?
ちょっと様子を見ているんだけど。

7 :デフォルトの名無しさん:04/09/16 12:48:10
練習問題の1000点解けなかった

8 :デフォルトの名無しさん:04/09/16 13:21:26
英語が・・・

9 :デフォルトの名無しさん:04/09/16 13:48:14
残忍なコード化する問題。病気のデッドライン。

それはこれよりいくらかよくなりますか。

10 :デフォルトの名無しさん:04/09/16 13:55:24
>>9
???

11 :デフォルトの名無しさん:04/09/16 15:41:43
事前の問題とそれに答えた香具師らの回答をここに貼ってくれよ。

12 :デフォルトの名無しさん:04/09/16 15:48:31
問題文を翻訳サイトにかけると
ワケワカメなにぽんごになって余計混乱する罠。

13 :デフォルトの名無しさん:04/09/16 16:43:10
>>12
自分が訳しますんでそのまま張ってください

14 :デフォルトの名無しさん:04/09/16 16:53:10
もしかして参加者ってほとんどいないのか?

15 :デフォルトの名無しさん:04/09/16 16:58:15
日本人はレベル低いからな。

16 :デフォルトの名無しさん:04/09/16 17:30:31
ちゅーより、アメリカとインドが特別なだけ。

17 :デフォルトの名無しさん:04/09/16 19:00:08
まもなく終了

18 :デフォルトの名無しさん:04/09/16 19:12:35
いつまで?

19 :デフォルトの名無しさん:04/09/16 21:41:04
Problem Statement

Graph problems are a fairly well known area of computer science. A graph
is a set of nodes, and edges that connect one node to another. For
example, the following ASCII art represents a simple graph with 4 nodes
and 3 edges ('x's represent nodes):

x
|
|
x---x---x

20 :デフォルトの名無しさん:04/09/16 21:41:37
A common graph problem is to find the shortest path from one node, u, to
another node, v, in a graph whose edges have weights. A path in a graph
from u to v is a sequence of edges. The first edge in the sequence
starts at u, and the last edge in the sequence ends at v. For all pairs
of edges that are adjacent in the sequence, the ending node of the
earlier edge is the same as the starting node of the later edge. A
shortest path from u to v in a weighted graph is a path from u to v, the
sum of whose edge weights is minimized. In this problem, we will be
dealing with a randomly generated graph, whose edge weights mutate over
time. You will be given six ints as input: nodes, u, v, A, B, and M. You
are to use the following algorithm to generate a fully connected graph
(one where there is an edge from every node to every other node):

cur = 1
for i = 0 to nodes - 1
for j = 0 to nodes - 1
if(i does not equal j)
cur = ((cur * A) + B) % M
weight(i,j) = (cur % 1000) + 1
else
weight(i,j) = 1
end if
end for
end for


21 :デフォルトの名無しさん:04/09/16 21:41:50
どうなった??
どうなった??
どうなった??
どうなった??
どうなった??
どうなった??
どうなった??
どうなった??
どうなった??
どうなった??
どうなった??
どうなった??
どうなった??
どうなった??
どうなった??
どうなった??
どうなった??
どうなった??
どうなった??


22 :デフォルトの名無しさん:04/09/16 21:42:22
This will give you the initial weights on the graph. Whenever an edge is
followed, the following algorithm is applied a number of times equal to
the weight on the edge, immediately after it is followed (note that the
cur here is the same cur as above, and that we never reset its value):

for i = 0 to nodes - 1
for j = 0 to nodes - 1
if(i does not equal j)
cur = ((cur * A) + B) % M
weight(i,j) = weight(i,j) + (cur % 21) - 10
if(weight(i,j) < 1)
weight(i,j) = 1
end if
end if
end for
end for


23 :デフォルトの名無しさん:04/09/16 21:43:55
明日の早朝1時.

24 :デフォルトの名無しさん:04/09/16 21:45:02
Note that, in addition to the random edges generated by this algorithm,
there is also an edge from every node to itself of weight 1 that never
mutates. The simplest way to think about this is that the weight on an
edge represents the amount of time it takes to traverse that edge, and
while the edge is being traversed, the weights on all of the edges
between different nodes mutate once for each time unit. However, the
amount of time that it takes to traverse an edge is locked in as soon as
we start to traverse it. For example, lets say we wanted to traverse an
edge of weight 3. It would take 3 time units to traverse the edge, and
so we would apply the mutation algorithm given above 3 times. Even
though the weight of the edge being traversed may be changed by this
process, we use the weight of the edge at the moment that we began to
traverse it. Your task is to generate the graph using the random
algorithm given, and then return the length of the shortest path through
the graph from node u to node v. Definition


25 :デフォルトの名無しさん:04/09/16 21:48:16
>>13

そのまま貼った.
>>19
>>20
>>22
>>24

超難問の誉れ高い,練習問題score1000.

ありがちなグラフの最短路かと思いきや,辺の重みが時刻に応じてランダムに変動するという.
誰かcoolな回答を考えてくれ.俺も考えたが,泥臭いのしか思いつかん.

26 :デフォルトの名無しさん:04/09/16 22:11:05
練習問題じゃなくて本選の問題のほうが知りたい

27 :デフォルトの名無しさん:04/09/16 23:22:58
Qualification Roundクリアしたとしても、Round 1の開始が日本時間の平日午前10時じゃ参加出来ねえよ

28 :デフォルトの名無しさん:04/09/16 23:49:02
>>25
(頂点,時刻) のペアを頂点と思ってグラフをつくれば
ありがちなグラフの最短路問題だ。

29 :デフォルトの名無しさん:04/09/17 01:18:53
1000点問題はDropRocksとTransmissionの2種類しかないとの噂。
DropRocks解けなかったよ。blute forceで組んだ人いる?
絶対そんなのムリだと思ってうんうん悩んでたら時間終わっちゃったよ。

30 :デフォルトの名無しさん:04/09/17 02:13:12
DropRocks(波紋のやつ)は50分くらいかかったけど、
1000点問題にしては楽だったよ(予選だからかな)。
少なくとも練習問題の方が100倍むずry)

400点の方のエラー取りしてるうちにタイムアップ。もうだめぽ。

31 :デフォルトの名無しさん:04/09/17 02:26:39
DropBrocks だったんだが、ripple が線でなく面で発生すると思い込んでしま
い、普通に組んだら駄目と思ってガリガリにチューンしながら組んだらタイム
アップ。

結局組み直して1時間半かかったが、それなりに最適化させながら組めば、
brute force でもギリギリ8秒は切ることは分かった。(ほぼ最悪の入力時、
Java 環境で確認。)

brute force でないやり方を知りたければ、Summary 画面へ Go。
今ならいろんな人のソースが見える。(得点を右クリック -> Source を選択)

400点問題の方は秒殺しておいたんで、予戦は通過してると思うけど、この調
子ではダメダメだな。つうか、400点問題と1000点問題の難易度違いすぎ。

>>少なくとも練習問題の方が100倍むずry)

えー。練習問題の方が簡単だった気がする。
まあ、得手不得手の問題かも知れないけど。


32 :デフォルトの名無しさん:04/09/17 02:27:57
2001*2001の配列作って1単位時間ごとに波紋を生成して評価して
を1000回くりかえすのでよかったのかな?

33 :31:04/09/17 02:43:09
>>32

ごめん、やっぱり brute force は無理かも。

1250×1250 が最大と勘違いしてた。それなら 8 秒だけど、2250×2250 だと
18 秒かかってる。C++ でチューンすればギリギリ OK かも、というレベル。
たぶん、実際にやったらチューンしている間にタイムオーバー。
やっぱり、パラメータはかなり考えられているみたい。

ちなみに上の brute force アルゴリズムでは、2250×2250×1000 はさすがに
無謀なので、2250×2250 で各点ごとに、各 ripple の 到着時刻と波高を調べ、
到着時刻の同じ波高の総和を取って、最大値を求めている。

関係ないけど、DropRocks で 956 点という凄いスコアをとっている人がいた
ので、びっくりしてソースを覗いたらこんなんだった。

public class DropRocks {

public int maxWave(String[] rocks) {
return 0;
}
}

他にもかなり間違ったソースがあるようなので、DropRocks 解けなかった人に
も希望はあるっぽい。


34 :デフォルトの名無しさん:04/09/17 02:49:56
微妙に希望もって待つことにする(´・ω・`)

35 :32:04/09/17 02:53:31
そうか調べる範囲が0-2000なんじゃなくて石が落とされるのがその範囲で
0以下は調べなくてよいとだけしか書いてないのね。
問題読み間違えてたから作っても間違ってたね。漏れ。

36 :デフォルトの名無しさん:04/09/17 04:17:34
98位でなんとか通過…(;´Д`)

37 :デフォルトの名無しさん:04/09/17 04:26:12
…と思ったけどもう一個の部屋と併せて上位100位だから確実に落ちてるぽ(´・ω・`)

38 :デフォルトの名無しさん:04/09/17 20:13:43
結果まだー?

39 :デフォルトの名無しさん:04/09/18 02:44:38
>>38
http://www.topcoder.com/pl/?&module=Static&d1=google04&d2=advQual

なんとか通過しますた。
日本人ちらほら居るね。


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

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

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