作者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