トップページ⇒tech
39コメント12KB

Google Code Jam 2004

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさんNGNG
今年も来たぜ
実況中
問題ネタばれOK
総力を結集して1000点問題を解こうぜ
0002デフォルトの名無しさんNGNG
まずは匿名アカウントで問題をここに貼り付けからだな。
0003デフォルトの名無しさんNGNG
http://www.google.co.jp/codejam/

0004デフォルトの名無しさんNGNG
http://d.hatena.ne.jp/kataho/20040911
0005デフォルトの名無しさんNGNG
↑ルールなど
0006デフォルトの名無しさんNGNG
もう解いたやついる？
ちょっと様子を見ているんだけど。
0007デフォルトの名無しさんNGNG
練習問題の1000点解けなかった
0008デフォルトの名無しさんNGNG
英語が・・・
0009デフォルトの名無しさんNGNG
残忍なコード化する問題。病気のデッドライン。

それはこれよりいくらかよくなりますか。
0010デフォルトの名無しさんNGNG
>>9
???
0011デフォルトの名無しさんNGNG
事前の問題とそれに答えた香具師らの回答をここに貼ってくれよ。
0012デフォルトの名無しさんNGNG
問題文を翻訳サイトにかけると
ワケワカメなにぽんごになって余計混乱する罠。
0013デフォルトの名無しさんNGNG
>>12
自分が訳しますんでそのまま張ってください
0014デフォルトの名無しさんNGNG
もしかして参加者ってほとんどいないのか？
0015デフォルトの名無しさんNGNG
日本人はレベル低いからな。
0016デフォルトの名無しさんNGNG
ちゅーより、アメリカとインドが特別なだけ。
0017デフォルトの名無しさんNGNG
まもなく終了
0018デフォルトの名無しさんNGNG
いつまで？
0019デフォルトの名無しさんNGNG
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
0020デフォルトの名無しさんNGNG
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
0021デフォルトの名無しさんNGNG
どうなった？？
どうなった？？
どうなった？？
どうなった？？
どうなった？？
どうなった？？
どうなった？？
どうなった？？
どうなった？？
どうなった？？
どうなった？？
どうなった？？
どうなった？？
どうなった？？
どうなった？？
どうなった？？
どうなった？？
どうなった？？
どうなった？？
0022デフォルトの名無しさんNGNG
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
0023デフォルトの名無しさんNGNG
明日の早朝1時．
0024デフォルトの名無しさんNGNG
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
0025デフォルトの名無しさんNGNG
>>13

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

超難問の誉れ高い，練習問題score1000．

ありがちなグラフの最短路かと思いきや，辺の重みが時刻に応じてランダムに変動するという．
誰かcoolな回答を考えてくれ．俺も考えたが，泥臭いのしか思いつかん．
0026デフォルトの名無しさんNGNG
練習問題じゃなくて本選の問題のほうが知りたい
0027デフォルトの名無しさんNGNG
Qualification Roundクリアしたとしても、Round 1の開始が日本時間の平日午前10時じゃ参加出来ねえよ
0028デフォルトの名無しさんNGNG
>>25
(頂点,時刻) のペアを頂点と思ってグラフをつくれば
ありがちなグラフの最短路問題だ。
0029デフォルトの名無しさんNGNG
1000点問題はDropRocksとTransmissionの2種類しかないとの噂。
DropRocks解けなかったよ。blute forceで組んだ人いる？
絶対そんなのムリだと思ってうんうん悩んでたら時間終わっちゃったよ。
0030デフォルトの名無しさんNGNG
DropRocks(波紋のやつ)は50分くらいかかったけど、
1000点問題にしては楽だったよ(予選だからかな)。
少なくとも練習問題の方が100倍むずry)

400点の方のエラー取りしてるうちにタイムアップ。もうだめぽ。
0031デフォルトの名無しさんNGNG
DropBrocks だったんだが、ripple が線でなく面で発生すると思い込んでしま
い、普通に組んだら駄目と思ってガリガリにチューンしながら組んだらタイム
アップ。

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

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

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

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

えー。練習問題の方が簡単だった気がする。
まあ、得手不得手の問題かも知れないけど。
0032デフォルトの名無しさんNGNG
2001*2001の配列作って1単位時間ごとに波紋を生成して評価して
を1000回くりかえすのでよかったのかな？
003331NGNG
>>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 解けなかった人に
も希望はあるっぽい。
0034デフォルトの名無しさんNGNG
微妙に希望もって待つことにする(´・ω・｀)
0035３２NGNG
そうか調べる範囲が0-2000なんじゃなくて石が落とされるのがその範囲で
0以下は調べなくてよいとだけしか書いてないのね。
問題読み間違えてたから作っても間違ってたね。漏れ。
0036デフォルトの名無しさんNGNG
98位でなんとか通過…（;´Д｀）
0037デフォルトの名無しさんNGNG
…と思ったけどもう一個の部屋と併せて上位100位だから確実に落ちてるぽ（´･ω･｀）
0038デフォルトの名無しさんNGNG
結果まだー？
0039デフォルトの名無しさんNGNG
>>38
http://www.topcoder.com/pl/?&module=Static&d1=google04&d2=advQual

なんとか通過しますた。
日本人ちらほら居るね。
■ このスレッドは過去ログ倉庫に格納されています