注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

srm471ConstructPolyline的随机化做法  

2011-04-05 21:27:17|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
我最近在做Topcoder,发现Match Archive中竟然没有srm471的题目,原来,比赛时,服务器宕了,于是比赛取消。。。
DIV1的第3题ConstructPolyline很有意思。
题目大意是:有50个三维空间中的线段,要求通过平移把它们中的一些连接成一个折线,使得这个折线的起终点的欧几里得距离最大。
首先,可知我们不会不选某个线段,只不过是选它作正的还是负的的问题。
换句话说,就是求max(|sigma(A[i] or -A[i])|)。
标准做法是用离散化的方法枚举划分平面,所有指向平面同一侧的向量前的符号相同。这个可以通过枚举两个向量,用它们的叉积作法向量来搞定。解题的关键是处理共面情况。我的方法是把共面情况转化为二维的问题,再次枚举划分直线。通过一些trick,最大的点9ms也跑完了。
不过,我发现有人说随机化的方法也可以过。
于是,我打算试试。

问题是,随机化什么呢?
想法1:随机化哪些向量取正,哪些向量取负。重复100000次。
很好,114个case过了9个,差不多就是OI比赛中骗了10分。
想法2:随机三个整数构成向量A=(x,y,z),所有与A点积大于零的取正,否则取负。重复50000次
很好,114个case过了66个,差不多在OI中能骗一半的分了。

当前的想法都是纯随机化,显然,离能够过题还很远。能否加入调整的思想呢?

想法3:随机化哪些取哪些不取,之后从前往后依次扫描,如果能够把一个向量的符号反过来而使答案更大,就反过来。
。。。很好,114个case过了10个。。。跟纯随机化一个水平。
想法4:随机化哪些取哪些不取,之后计算和向量A,令所有于A点积大于0的取正,否则取负。重复50000次。
非常好!通过了System Test!这真是奇迹般的一个调整思路。
于是,重复次数减至10000次,依然通过。
于是,重复次数减至5000次,依然通过。
于是,重复次数减至1000次,依然通过。
于是,重复次数减至500次,依然通过!
现在,随机化已经秒杀标准做法的速度了。
我想计算一下,最佳的重复次数是多少呢?
我计算一次随机选取并调整得到答案的概率,经过测量之后发现,最差的case大约在0.001左右,绝大部分的case在0.01以上。
可别小瞧了这个千分之一,如果重复1000次,那么成功概率就是63.2%,人品好一点就能过了。
如果重复10000次,那么成功概率就是0.9999548,失败概率差不多和买彩票中奖(不是中大奖)一样了。
如果重复50000次,那么成功概率就是0.99999999999999999999981,可以连中好几回大奖了。
如果重复200000次(卡着时限),那么成功概率就是
0.999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
注意呦,目前人类能够接触的宇宙的原子的个数大约是
100000000000000000000000000000000000000000000000000000000000000000000000000000000
要是没有过SystemTest,那么,说明你的rand函数出问题了!

为什么这个随机化能够得到如此高的成功率?有没有精心构造的case能卡死它?
这是个好问题
等待我们去探索
  评论这张
 
阅读(1294)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017