2013 ACM/ICPC 成都赛区现场赛解题报告汇总
十一月 16th, 2013 | Posted by in Blog | ICPC | ICPC 2013 亚洲区 | 信息聚合 | 算法竞赛 | 解题报告 - (14 Comments)针对2013 ACM/ICPC 成都赛区现场赛(10月20日),本日志汇总网上ACMer们发布的解题报告,方便大家互相学习。欢迎补充和完善本日志。
感谢所有及时发布解题报告,和大家分享知识的各位神牛。
(更多…)
针对2013 ACM/ICPC 成都赛区现场赛(10月20日),本日志汇总网上ACMer们发布的解题报告,方便大家互相学习。欢迎补充和完善本日志。
感谢所有及时发布解题报告,和大家分享知识的各位神牛。
(更多…)
针对2013 ACM/ICPC 杭州赛区现场赛(10月27日),本日志汇总网上ACMer们发布的解题报告,方便大家互相学习。欢迎补充和完善本日志。
感谢所有及时发布解题报告,和大家分享知识的各位神牛。
(更多…)
针对2013 ACM/ICPC 南京网络赛(9月21日),本日志汇总网上ACMer们发布的解题报告,方便大家互相学习。欢迎补充和完善本日志。
感谢所有及时发布解题报告,和大家分享知识的各位神牛。
(更多…)
针对2013 ACM/ICPC 通化邀请赛(6月2日),本日志汇总网上ACMer们发布的解题报告,方便大家互相学习。欢迎补充和完善本日志。
感谢所有及时发布解题报告,和大家分享知识的各位神牛。
(更多…)
比赛时间:北京时间2013年7月3日13:00-18:00 (更多…)
针对2013 ACM/ICPC 通化邀请赛(5月26日),本日志汇总网上ACMer们发布的解题报告,方便大家互相学习。欢迎补充和完善本日志。
感谢所有及时发布解题报告,和大家分享知识的各位神牛。
(更多…)
针对2013 ACM/ICPC 长沙邀请赛(5月26日),本日志汇总网上ACMer们发布的解题报告,方便大家互相学习。欢迎补充和完善本日志。
感谢所有及时发布解题报告,和大家分享知识的各位神牛。
(更多…)
针对2013 ACM/ICPC 南京邀请赛(5月12日),本日志汇总网上ACMer们发布的解题报告,方便大家互相学习。欢迎补充和完善本日志。
感谢所有及时发布解题报告,和大家分享知识的各位神牛。
(更多…)
地铁遍历规划挑战赛结果已揭晓
代码组中,@zaq1xsw2tk 荣获冠军,@LostMyBrain、@左迪洛斯、@-快乐小兵- 分获2至4名。
结果组中,@-快乐小兵-、@Martreen_L 分获北京地铁线路规划前两名;@老钱InMainland、@朽木轩主 获上海地铁线路规划前两名。
解题思路:@zaq1xsw2tk,http://t.cn/zjlhKLO ,@LostMyBrain,http://t.cn/zjljFPT
问题描述
怎样花尽可能短的时间去一遍北京所有的地铁站?要求:只在地铁内换乘,不出站。
本题中,一共有三种时间花费:车辆行驶时间、换乘时间、等车时间。
1. 车辆行驶时间为地铁从某站行驶到下一站所需的时间。
2. 换乘时间为乘客从地铁X线的某站走到地铁Y线的同名站所需的时间。
3. 等车时间在本问题中为固定值,会在三种情况下发生:
a. 刚开始坐车前;
b. 换乘之后,坐上下一趟列车前;
c. 原地换乘同线反方向的列车前(比如在一号线上东单到王府井,再回到东单,中间要等一次车)。特别的,在很多地铁线的终点站处,需要调头,这时候也需要等一次车。
现在给出相邻站之间的行驶时间,以及各换乘站之间的换乘时间。请给出一条线路,去一遍所有的站(不同地铁线的同名站认为是同一个站)。详细输入输出格式参考详细说明文档:http://bnuoj.com/hackathon/public_data/probdesc.pdf
比赛时间
持续一周,从即日起至12月23日晚24:00。
比赛形式
本次比赛分两组进行,代码组和结果组。
对于每组数据,我们会对选手给出的结果进行模拟(代码组的程序输出、结果组提交的结果),以选手规划路线的模拟耗时作为主要评价指标。
代码组
选手需要提交代码完成这一任务,输入输出使用标准输入和标准输出。单文件提交,不允许网络编程、多线程、多进程、文件读写。
内存限制:2G;时间限制:1分钟(每组数据)。
评分规则:测试数据有若干组。满分1000分,平均分配到各组数据上。测试数据有若干组。对于每组数据的得分为: 这组数据的满分*所有选手的最优时间/你的时间 。总分为各组数据的得分和。总分高的名次排前。
比赛时使用的数据为若干城市的实际地铁线路图。赛后会使用若干组新的数据重新评测,作为最后得分。选手可以反复提交,以最后一次提交的程序为准。
参赛地址:http://bnuoj.com/hackathon/contest_show.php?cid=2
比赛平台
http://bnuoj.com/hackathon/
评测机配置:
Ubuntu 12.10 64bit (Linux 3.5.0-17-generic)
Intel Core i7 CPU 950 @ 3.07GHz
GNU C/C++ 4.7.2 (Ubuntu/Linaro 4.7.2-2ubuntu1)
Free Pascal Compiler version 2.6.0-6 [2012/10/05] for x86_64
Java(TM) SE Runtime Environment (build 1.7.0_10-b18), Java HotSpot(TM) 64-Bit Server VM (build 23.6-b04, mixed mode)
Python 2.7.3
结果组
数据公开,可以通过人工规划和本地程序运算,提交路线。分为北京和上海两题,数据分别为北京地铁线路图和、上海地铁线路图。
对于人工规划的选手,我们提供了一个小工具(北京地铁 , 上海地铁),可以在网页上点击鼠标,直接生成结果。
评分规则:题目满分1000分。提交路线的得分为1000*所有选手的最优时间/提交线路的时间。得分高的靠前。相同得分以提交时间先后排序。根据选手提交路线的耗时排名。当路线耗时一样时,提交时间越早的排名越靠前。选手可以反复提交,以最优结果最后一次提交为准。提交的输出路线不能超过320KB。
参赛地址: 北京 http://bnuoj.com/hackathon/contest_show.php?cid=3
上海 http://bnuoj.com/hackathon/contest_show.php?cid=4
比赛奖励
如果获得公司或者个人赞助奖金,在赞助人没有特殊要求的情况下,均奖励给各组总分排名靠前的选手。若有要求,则根据赞助商的要求分配奖项。
欢迎热心的公司或者个人提供更多的奖励赞助。
现有奖金奖励
@卢亿雷 赞助现金500元
@图灵谢工 赞助图灵社区银子350两
@传说中的冬瓜头 赞助了2本《大话存储2》和3本《大话存储1》, (如果参赛人数多,会增加)
奖池的具体分配方案会根据新的赞助做调整,请见BNUOJ比赛平台( http://bnuoj.com/hackathon/ ) 上prize pool里面的最新消息。
本题原为Carbonite China的面试题,可以到这里查看一些相关讨论。http://weibo.com/1974533700/z9ByHAWs3
2012年我们曾在北京航空航天大学和北京邮电大学共举办了两次北京地区ACMer线下聚会,两次活动累计有将近150人次参加。参与者覆盖了北京地区的绝大部分高校和IT公司。活动内容采取主讲和自由交流结合的方式。其中包括Kinect开发经验分享,学习、实习、工作和创业经验分享,围观ACM/ICPC世界总决赛等。两次聚会的成功举办,很多人在相关方面有了新的想法,让我们意识到经验分享的宝贵。
主题:梦想在现实中起舞——ACMer求职工作经验分享会
地点:北京理工大学
时间:11月25日下午 (具体时间再通知)
赞助商:Topcoder & Face++
活动预计人数:120人
活动内容:
现场将邀请到手握大把牛offer的大神,还有已经工作或创业的ACMer。他们将会分享求职、工作、创业方面的经验,开拓大家职业规划、工作选择的思路。
赞助商Face++将会派代表参与聚会。这将是一个同这家有ACMer参与主导的创业公司零距离接触的机会。
我们希望通过此次聚会为ACMer以后找工作、规划职业走向提供一些想法,增进北京地区ACMer相互之间的交流。
聚会中将提供:
专为此次北京ACMer聚会订做的限量版纪念品;
聚会中积极活跃的参会者将有机会获得精美礼品;
除了主讲,还将有茶话会形式的自由交流,现场会提供零食;
认识其他ACMer和让其他ACMer认识你的机会。
报名方式:
请发送报名信息至内容包括:
1,OJ常用ID;
2,真实姓名;
3,学校(含年级)or 公司;
4,Email地址;
5,手机号码;
6,竞赛经历(可选);
备注:
报名信息仅用于确定参加聚会的资格,接收聚会相关信息等,在未经您允许的情况下不会提供给任何公司用于其他目的。
活动会有人数限制,如果报名人数过多,将权衡人数、年级、报名先后等因素筛选。报名邮件一般不会回复,如果报名成功,你将在聚会前1~2天收到邮件、短信通知。
活动回顾:
第一次北京ACMer线下聚会:http://page.renren.com/600940098/album/591927028
第二次北京ACMer线下聚会:http://page.renren.com/600940098/album/625896881
赞助商介绍:
Topcoder是ACMer熟知的专门组织竞赛形式的公司。TopCoder在线举办各种算法比赛、开发比赛、设计比赛。其中SRM是最为ACMer所喜欢的比赛。
Face++(http://www.faceplusplus.com)是一个人脸识别云服务平台, 通过它提供的开放API,用户可以方便地在实现若干面部识别功能,包括从图片中定位人脸,提取性别、年龄、情绪信息,人脸相似性匹配(http://faceplusplus.com/en/demo)。
该创业团队成员来自清华大学、哥伦比亚大学、牛津大学、南加州大学。其中有著名的2008年代表清华参加World Final的唐文斌和2007年IOI金牌得主杨沐。他们曾经开发过一个ios上的游戏crows coming,使用面部识别的技术控制游戏,曾经在appstore上高居中国榜首。最近他们开发的另一款游戏Free Skate Xtreme,正在appstore上被推荐。