作者TonyQ (沉默是金)
看板Soft_Job
標題Re: [情報] 2008 Google Code Jam 程式設計挑戰賽
時間Sat Jul 26 08:40:39 2008
google code jam小組
前兩天有寄一篇說明Round 1 取人規則的信 ,
沒看的記得要看一下～
話說再過20分鐘就是小弟所參加的Round 1A了,
先上去踩踩點 , 各位同好們一起加油吧...:)
--
▄▅▆▇███▇▆▅▄▃ ╰┼╯─╮ ╮
◥███████████◣ ╰┼╯＝│=│
◥██████───────◣ ＊． ╯ ╯ ╯ の 物 語 ．＊
◥███████──────◣ ～ ◢◣ ◢◣
◥██████───────◤ ◥◤＊ 空白的世界．翼
＊◥◤
◥██▁▂▃▄▅▆▇███▆▅▄▃▂▂
～telnet://tony1223.twbbs.org
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.134.27.68
1F：推 redray:兩個小時...加油！ 07/26 08:41
2F：推 derekhsu:來了，感覺好難啊 07/26 08:59
3F：→ TonyQ:第三題感覺簡單一點 07/26 09:04
4F：→ TonyQ:馬的 看起來簡單 其實踩到雷 07/26 10:14
5F：→ TonyQ:xxx 放棄第三題回頭作第一題 才花十五分中.... 07/26 10:46
6F：推 derekhsu:第一題算送分.... 07/26 10:47
7F：推 windows2k:糟糕, 掛蛋 :( 07/26 10:50
8F：→ windows2k:準備參加補考吧 07/26 10:50
9F：→ TonyQ:還有五分鐘, 挑戰第二題 ＝ ＝a 第一題large沒考慮大樹 07/26 10:55
10F：→ TonyQ:錯了就算了 orz 07/26 10:55
11F：→ TonyQ:唉 下次應該要先看配分orz... 07/26 10:58
12F：推 windows2k:我是廢柴, 準備補考了 :( 07/26 11:01
13F：→ TonyQ:timeout ~_~ 07/26 11:01
14F：→ TonyQ:......總參加人數不是才六千多人 , 超過1/3的人在這場.. 07/26 11:02
15F：推 derekhsu:哭哭只有一題....T_T 07/26 11:02
16F：推 windows2k:工作太久腦袋不管用了, 連送分題都要送四次 07/26 11:03
17F：→ TonyQ:說真的 我是看到感覺好難 想說該不會第一題是難的..往後看 07/26 11:03
18F：→ windows2k:第三題我死在精準度, 哀 07/26 11:03
19F：→ TonyQ:不過第三題我真的寫的很怨 , 都用bigDeciaml處理了還是錯.. 07/26 11:04
20F：→ derekhsu:我送分題送了兩次...PHP排序要先settype...XD 07/26 11:04
21F：→ windows2k:時間就耗在一根三上面 ~"~ 07/26 11:04
22F：→ TonyQ:我也是死在精準度啊......其實想想應該要用算的 07/26 11:04
23F：→ derekhsu:第三題數字太大.... 07/26 11:04
24F：→ TonyQ:我送分題是一次過關啦...(對照第三題送了六次...orz) 07/26 11:04
25F：→ derekhsu:BigDecimal是Java常用的，但我覺得那不會這麼簡單出來 07/26 11:05
26F：→ TonyQ:第三題的難題應該是在於怎麼取得計算小數所須要的位數 07/26 11:05
27F：推 windows2k:只有五分 ~"~, 哭哭 07/26 11:05
28F：→ derekhsu:第一題依照向量正負排序乘完答案就出來.... 07/26 11:06
29F：推 redray:唉..我第一題應該要很快就算完才對...結果題意弄錯... 07/26 11:06
30F：→ TonyQ:差不多是這意思, 我是拿 Amin*bBax 跟 bMax*aMin 來比 07/26 11:07
31F：→ TonyQ:這樣比較省 07/26 11:07
32F：→ derekhsu:第一題好奸詐，居然用大數，我不知道我對錯了...T___T 07/26 11:07
33F：→ redray:我以為兩個向量會有不同 size...花了我 1 hr 才回過神.. 07/26 11:07
34F：→ TonyQ:反正只有極端值需要考慮 07/26 11:07
35F：→ TonyQ:(拍拍） 07/26 11:07
36F：→ redray:接著看第二題,光題目就看不太懂了,又花了很多時間..=.= 07/26 11:08
37F：→ derekhsu:第三題一定不能直接求的，因為他只要最後三個數字 07/26 11:08
38F：→ TonyQ:我在要題目時才想到大數 ,緊急改BigInteger...一直有問題 07/26 11:08
39F：→ redray:最後剩下十分鐘決定看第三題碰碰運氣，結果快做完的時候 07/26 11:08
40F：推 windows2k:二次分配吧 07/26 11:08
41F：→ derekhsu:第二題屬於動態規劃的題目吧？第三題感覺好像也是.... 07/26 11:08
42F：→ redray:時間就到了...Orz 明天補考吧.. 07/26 11:08
43F：→ TonyQ:不能說是最後三個數字 , 那應該算是「中間」的數字 07/26 11:08
44F：→ TonyQ:不是整數位取三位嗎？ 07/26 11:09
45F：→ TonyQ:第三題應該是DP , 第二題還沒看懂題目時間就到了 冏rz 07/26 11:09
46F：→ derekhsu:也對，一旦搞到這麼大以後精確度就難了 07/26 11:10
47F：→ derekhsu:預賽都考簡單的Greedy...複賽就玩大的DP了.... 07/26 11:11
48F：→ TonyQ:整數位的第一位 應該可以看作類似 int(k)* decimal(k) 乘積 07/26 11:11
49F：→ TonyQ:k = 1-> n 07/26 11:11
50F：→ TonyQ:我剛剛本來有打算朝這思路去想 , 不過還是依賴內建大數運算 07/26 11:11
51F：→ TonyQ:當我發現大數運算我沒辦法操作到精準 甚至看不出問題在哪 07/26 11:11
52F：→ TonyQ:我就知道這題我不可能解出來 orz 跑回去作第一題 07/26 11:12
53F：→ TonyQ:第一題應該需要考慮大數運算 , 我掰了 orz 07/26 11:12
54F：→ derekhsu:如果內建大數運算就可以出來那他們也不用做這題目了XD 07/26 11:12
55F：→ TonyQ:可能吧 XD 不過我還是很想知道問題卡在哪 ... 07/26 11:13
56F：→ derekhsu:PHP好像能內建處理大數，也許會對吧.... 07/26 11:14
57F：→ TonyQ:好吧 我下一場是今天午夜 , Saturday, July 26 - 4 pm UTC 07/26 11:14
58F：→ TonyQ:我不覺得php處理大數的能力會比Java好 =-=a 07/26 11:14
59F：→ derekhsu:我是明天下午...唉，去下載其他高手的解答來看吧 07/26 11:15
60F：→ TonyQ:但也不見得比較差就是了 XD 07/26 11:15
61F：→ derekhsu:幹幹幹，我1332名啊，做快點就有了.... 07/26 11:15
62F：→ TonyQ:uhch123整個猛...超早就解完了 07/26 11:15
63F：→ TonyQ:連15分都可以入圍... 07/26 11:16
64F：→ TonyQ:看了一下 如果挑戰最高等的 , 早一點解出來 ,應該有機會 07/26 11:17
65F：→ TonyQ:現在看得到程式碼下載區嗎？ 07/26 11:18
66F：推 derekhsu:送分題必須10分內做完.... 07/26 11:18
67F：→ derekhsu:可以，把Solution Download打開就有了 07/26 11:18
68F：→ TonyQ:thanks , 看到了. 07/26 11:19
69F：→ TonyQ:話說回來 這場進來了起碼1/3的參賽者...y 07/26 11:19
70F：→ TonyQ:如果能找到一場人數低於840的話就賺到了 =.=a 07/26 11:19
71F：推 redray:請問哪裡可以下載到程式？ 我想要看一下第三題的答案 07/26 11:20
72F：→ TonyQ:感覺人數應該是會普遍分在前面這兩場..唉 錯誤策略 orzorz 07/26 11:20
73F：→ TonyQ:評分版 , 上面有 check box 寫solution download 07/26 11:20
74F：推 derekhsu:第一名的高手...只用65行就解完了第三題...好厲害的C++ 07/26 11:21
75F：→ derekhsu:最扯的是只用了stdio.h跟stdlib.h兩個Lib.... 07/26 11:21
76F：→ redray:感恩 07/26 11:22
77F：→ TonyQ:..........真神人,他找出規律... 07/26 11:22
78F：推 derekhsu:還有只用39行的....我後來也知道要找規律，但來不及了... 07/26 11:23
79F：→ TonyQ:找規律是最一開始的想法吧 ? 跟找 2^n次方最後一位意思一樣 07/26 11:24
80F：→ TonyQ:只是規律實在是一看就讓人不想去想了... 07/26 11:24
81F：→ derekhsu:第三名只用2x分鐘解完，他只用39行，神 07/26 11:25
82F：推 derekhsu:a[i] = (6*a[i-1] - 4*a[i-2] + 40000)%1000; 07/26 11:28
83F：→ derekhsu:誰能告訴我這一行他怎麼想到的啊...orz 07/26 11:28
84F：→ TonyQ:他的寫法跟 1差不多 行恕不是重點 07/26 11:28
85F：→ derekhsu:重點是那個公式...不知道怎麼想出來的 07/26 11:29
86F：→ TonyQ:那個+40000 好像是為了扶正吧 ？ 不然%1000 照樣是消掉 07/26 11:30
87F：→ derekhsu:那個6,4,2不知道怎麼來的.... 07/26 11:31
88F：→ TonyQ:6 跟 -4 跟 第一名的一樣 , 可能要從 1-12的規律去看了 07/26 11:32
89F：→ TonyQ:總覺得1 用矩陣應該不會是巧合或運算方便. 07/26 11:35
90F：→ TonyQ:而是他們的思路如此 , 可能是數學上得座標對應. 07/26 11:35
91F：→ TonyQ:直覺猜測 XD 07/26 11:35
92F：→ TonyQ:A是 ]+ 1000000) % mod; 07/26 11:36
93F：→ TonyQ:這證明十萬跟四萬都不是重點 只是一個夠大的數來作對映而已 07/26 11:36
94F：→ TonyQ: 其實是百萬 07/26 11:36
95F：→ TonyQ:發現我誤解derekhsu的說法 , 內建應該說得是資料型態內建 XD 07/26 12:13
96F：→ TonyQ:那就跟java或php 哪個大數處理效率比較好沒關係了 orz 07/26 12:13