Archive for the ‘比赛’ tag
SRM 445
赛前定下的目标就是, 保住黄色. 然后拖着疲惫的身躯打完整场比赛, 坚持到了 rating 更新再睡觉 (幸运的是 System Test 很快, 没让我等太久), 也见证了自己的 rating 第一次突破 1700. 可以说很令我满意了, 不过却一点也高兴不起来.
让我耿耿于怀的就是那个 250 (275?). 当时拍出了一个自己也不知道对不对的程序, 按照平常的习惯, 我是万万不敢 submit 的, 除非是比赛最后时刻. 但是当时翻了一下 Room Summary, 发现那道题还只有 zhuojie 一个人提交, 不知道怎么就点了 submit.
感觉那一刻的自己像极了灵山仙人洞里的景天, "只是想痛痛快快地打一场罢了".
当然了, 结果也很像. 不过如果每次都这样, 结果不像的那一天迟早会来临, 而且肯定不会迟…
其实之前并没有发现自己这么地依赖 ACM. 因为那种原因被 ACM 队踢掉真的十分不爽, 甚至不能用不爽来形容了 — 可惜我找不到更合适的词. 也只有这几天跟久违的同学们在一起的时候, 我才能稍微忘掉这些放松放松.
可是, 这样下去也不是办法. 现在已经痛痛快快打了一场了, 也该是回归正轨的时候了.
下次 SRM 是8月, 还有时间.
交大ACM队机试结束
题目很恶心,7水+2难.结果就是N多人都是7道题,7道题主流啊…qujun这种做了7道题结果因为全场最水的G题看错题而排名靠后的就悲剧了…
A题,给出C个字母,要求输出由这些字母所有满足下列条件的字符串:所有字母升序排列,每个字母只用一次,长度为L(L<=15),单词里至少有一个元音两个辅音.
这道题因为刚开始状态不太好卡了一会儿,不过最后还是比较顺利的搞出来了.
B题,给一个01矩阵,问有几个连通块(只有上下左右连通才算).
简单的BFS.
C题,给一个5*5的数字矩阵,从任意一点开始每一次向上下左右的任意一个方向走一步,可以走重复的格子,经过6个格子之后会得到一个六位数.问总共可能得到多少个不同的六位数.
纯搜索.
D题,题目描述比较恶心,反正就是给你一堆矩形叠在一起的影子,问最少多少个矩形能够叠出这样的影子.所有矩形都是放在地面上的.
用链表维护一下就行,题目稍微长一些,但是很简单.第一次写写错了,写的算法和想的算法不是一个…走神了啊.不过还好,后来改对了.
E题,有N头牛,每头牛都有一个强壮指数和重量.现在把它们按照某个顺序叠起来,每头牛计算一个上面所有牛的重量之和(不包括自己)减去它的强壮指数,问如何所有牛的这个值的最大值尽量小,输出这个最小的最大值.
刚开始还以为是二分答案,后来想到了贪心是把重量和强壮指数加起来,大的放在底下,但是没法证明,第一次submit还错了.后来发现第一头牛的这个值应该是负的自己的强壮指数,改了再交就过了.但是没完整地证明出来(只证明了三头牛是正确的).
F题,给定函数f(a),计算方法是:把a的最后一位挪到第一位前面,然后平方,再把结果的第一位挪到最后一位后面.问第N个满足条件f(a)=a^2的a是多少.
写个暴力找下规律,就可以发现是1,2,3,21,221,2221,22221…于是直接输出就可以了.
G题,全场最水的一道题.就是给定N个点,两个点之间有个某某概率为1/sqrt((x1-x2)^2+(y1-y2)^2+(z1-z2)^2+1),问最后一个点和前面所有点分别算这个概率,最大的一个概率是多少.
只需要把最后一个点和前面所有点的概率分别算出来然后找个最大的就行了…很可惜,因为是个人赛,所以没办法刚开始就看完所有题…基本上每个人都是最后才做出这道题的.还有很多看错题,求了所有点对之间的…那些人很悲剧…
然后是两道不可做题.
H题,要求求出一个序列{a_n},满足sigma(i=1~n)a_i=x,sigma(i=1~n)a_i^p=y,而且sigma(i=1~n)a_i^q尽量小.输出这个最小值.
数论题,我是直接放掉了…
G题,给一个有向无环图,给四个点abcd,四个点的编号都不同,从a到c和从b到d可以找到一对不相交路径(就是没有公共点),问这样的路径对有多少种.
这道题写了个暴力交上去,然后眼睁睁的看着前面的judge拿我的程序跑,大概在第三个点TLE了…然后给我return了一个TLE…于是就再也没想出来…
大概就是这样,题还是很水的了.最后排在所有人的第13名,比笔试退后了两名…不过据说这次又会有N多人晋级面试,唉…
ACM/ICPC World Final 2009 结束
真的好久没有更新了呢, 快一个月了吧.
这篇 blog 只说刚刚结束的 WF 的事情, 不会很长, 别的我要是不困再写一篇.
知道今天有 WF 也是下午回家之后的事, 然后立刻开 ranking 观战. 这时有人发来一个视频直播的链接, 打开看了, 很卡加上半懂不懂的英语解说, 我获得的信息基本还是来自 ranking 的.
当时一直关注着 SJTU 的尴尬的 2 题, 然后就发现 tsinghua 在前面也停滞不前了. 接下来就是眼睁睁的看着 tsinghua 被一次次的赶超.
然后 tsinghua 貌似出了一题, 但是很快就发现 ZJU 赶了上来… 这时 TJU 都跑到了 SJTU 的前面, 真的很尴尬. 直到 FROZEN 的时候, ZJU 是 rank 5, TSU 是 rank 6, 而 TJU 和 SJTU 都是 3 题 (似乎快封板了才搞出一题?), 排在好几十名, TJU 貌似更靠前.
然后 FROZEN, 接下来就是一边看亚冠一边期待…
刚刚看完亚冠回来的时候, 群里对比赛结果有 N 种说法… 最后在饮水思源上看到了 JinBin 的发言, 基本确定了 tsinghua 最后是第二, 似乎是最后时刻爆发了, 做出了9题 (封板的时候第一名是8题, 第二名6题, tsinghua 是第6), 不过还是因为罚时只拿到了第二… ACRush 教主竟然拿了两个第二, 真的不知道说什么好… 听说楼教主当时哭了, 其实我也想哭了…
可能记得不是很清楚, 有不对的地方, 但大致的进程就是这样…
ICPC 真的很刺激… 终于又一次发现了它的魅力… 团队协作的比赛, 还是比 TC 那种单打独斗更加令人痴迷, 令人陶醉.
就是这样. 最终圣彼得堡的一个什么学院拿了第一, 清华第二, 圣彼得堡大学第三. 浙大拿到了第六, 赞一个. 而交大最后是并列第13, 很无奈.
武汉大学百度杯比赛惨败
为了方便搜索引擎, 列出全名:
百度杯 第四节华中北区程序设计邀请赛
The 4th Baidu Cup Central China Invitational Programming Contest
比赛也算是比较圆满的结束了 (如果不考虑比赛过程中不断的 HTTP 503 / 500 的话), 挂的也是够惨.
据说除了校内队伍取 40 支, 然后我们总排名第 54. 还有一丝希望晋级吧. 已经被淘汰了. 也好, 轻松了.
不想再发泄什么因为我晚到半小时导致比赛结束 10 min 才出 I 题的事情… 昨天发泄够了也在校内被 bs 够了. 当然当时没 bs 够的还可以接着来这篇文章底下留言 bs… 我现在心情至少比那时候好.
正式比赛里, gnocuil 牛领衔的 E.W.F. 队没有如愿拿到第一, 第一被 jby 神牛的 Gold Kylin 抢去了… 第三竟然是 cqf 神牛, 不知道做题的时候神牛有没有用到 SBT 呢… 第四不认识, 第五是 xt 神牛, 果然中学队伍比较强大.
然后强力的 wh 拿到了第 16, orz一个. 啊, 忘了说, 然牛貌似是第 12 啊. And, rank 13 是姜里羊神牛. 能认出来的貌似就这些.
比赛刚开始, 我就迟到了… 等我到的时候, 比赛已经开始了半小时, 貌似有很多队伍都出两三道题了. 而 zmc 也过掉了 G (似乎是水题, 我没看题).
到了之后我就鬼使神差地开始写 E (一个不是太恶心的枚举), 还鬼使神差的读错题了. 于是贡献了 4 个 WA 以后才 A 掉, 这也就导致我们在出 4 题 5 题的时候, 排名一直是最靠后的.
在我 submit E 的同时, zmc 也在做 J (据说是弱智DP). 然后我在 E 多次 submit 都 WA 的情况下, 最终开始搞 H (纯水题, 排序), 在使用了大量 STL 的情况下 (map, set, vector, pair, algorithm, 基本上 1/2 的程序行都有这些东西), 终于 2Y 掉. 而在 Y 掉 H 之前, zmc 和 Nxun 找到了 E 的问题, 就是读题读错了 (关于该黑棋还是白棋走的问题). 于是 E 题也过掉. 紧接着, zmc 也过掉了 J.
然后, Nxun 就开始折腾那道不太该折腾的题, F (根据化学式计算相对分子质量, 需要高精度). 这道题直到最后也没搞对, 最终确定是高精度写错了. 而我正好发现了 D 题 (Cipher 加密法) 是我曾经给 FNOI 的小朋友们出过的一道题 (瀑布汗! 我当时出的是解密, 这里要求加密), 于是赶快写, 1Y 掉. 这道题本该早写的, 但是当时看 AC 人数比较少所以都没看题…
接下来的时间就是每人一道题慢慢磨的时间了, zmc 是 C (恶心计算几何貌似?), Nxun 还是 F, 而我是 I (SCDP). 最终三道题一道也没出, 比赛结束 10min 后搞出了 I. 错的原因也在校内说过了, 数组开小了 1. Shoot.
这次败得够惨, 顺便膜拜搞出 A (双向宽搜) 的牛们.
顺便提一句, TCO Round 1 我就被淘汰了, 最近状态 ttm 差了…
Time Limit Exceeded 结束 && Happy Valentine’s Day~
昨天搞完了 Time Limit Exceeded, 现在还有一道题TESTGEN没有测试, 其余题目我们 YaohuaFree 的 Rank 是 41, 得分很诡异地竟然是 1234 分 (Rank List). 还算可以接受吧, 不过很可惜最后还是没有达成超过 lonelycorn 和搞掉 CLASS 这两个目标.
简单的说一下题目.
- Key to C (KEY)
这道题是我们第一道出的题目, 也是搞得最久的一道题目, 不过事实证明这道题根本拉不开分差 — 最高的 154 分, 而我们 126 分就 20 多名了. 和其他的题目的 rank 1 动辄上千分比起来, 这道题做了基本相当于没做.
题目要求读入一些数, 判断它们的二进制表示是否回文. 评分标准和很多东西有关, 比如程序中关键字的个数 (这个权重最大), 比如空格个数, 比如代码长度… 总之这些东西都是越多得分越低. 然后代码回文会得到 extra bonus, 貌似是 4 倍多分数吧.
基本的做法就是?:操作符加main递归, 貌似 rank 1 那个也就这么做的. - Play with Code (SHORTEN)
给出一个代码要求缩短. 这道题最终也不知道那个代码到底啥意思, 只看懂了一段求素数. 而且那个代码在我们几个人的机器上跑貌似都 RE 掉了… 评分规则是代码长度越长分数越少.
最终的做法是物理缩短… 也就是 define 一个 for 啊, 改一点变量名啊… 就这样子… - Produce the Code (INPUT)
给出一个输入文件和一个输出文件, 要求写一个程序, 对于这个输入文件能够输出给出的输出文件. 当然可以不理睬输入文件直接把输出文件打出来 (我的第一个 code 的确是这么干的), 不过这样代码长度会很长, 而这道题的评分规则也是代码长度越长分数越少…
这道题由三个人合力完成… 先是来帮忙的 xhy 同学看出了替换规则 (我就是一直卡在这里), 然后我折腾出了乱序的规则, 最后是木木同学的 coding… 虽然 rank 不高不过做得很爽. - #ED (CODEHASH)
给出一段代码, 给一个 hash 函数, 要求代码输出自身的 hash 值.
貌似有人用 whitespace 来搞, 不过还是比较 orz 那个 rank 1 的, 就一句代码… 很强大.
这题我们一点没动. - COMPILE ERROR (CLASS)
我最想做出来的题, 但可惜最后也没做出来.
要求写一个类 multiply, 里面包括一个函数 mult(int a, int b), 函数的功能是输出 a * b 的结果, a, b 都小于 10000. 变态就变态在不允许用空白字符…
见到了两种解决方法, 一种是官方的 (之所以说官方因为这道题提示了要用 typedef, 如果认为题目描述的那个 "typedefine a class" 不足以说明问题, 那么自己去翻 forum), 另一种很诡异, 用一个不可见字符替代了空白字符还编译通过了… 据说那个字符是 \f, 从来没见过… - PRINT D PENGUIN (PENGUIN)
给一个字符画, 是 Linux 那个企鹅. 要求输出这个东西.
基本就是考压缩, 我因为怕编译器没法处理所以只压缩成了可见字符, 但是事实证明编译器是可以处理不可见字符的, 因为 rank 前几名的都用了不可见字符. 我很无奈, 不过可见字符范围的压缩我基本是搞到极限了, 还比较有成就感. - PRINT ME (PRINT)
这道题是前来帮忙的 xhy 写的, 题目要求很简单, 输入一个数, 如果是偶数那么输出代码本身, 否则反转代码输出.
xhy 写了一个回文的代码, 这样就不用管奇数偶数了, 而且根据题目还可以获得 200 pts 的加分.很不错.
最后一天用了很短的时间完成的 code, 得分还不低 (貌似是所有题里 rank 最高的一个), 或许是性价比最高的一个 code 了. - P=NP (NP)
这道题的题目描述讨论了半天也没明白, 最终放弃. 直接贴出英文题目描述, 做出来的神牛 (比如 oldherl) 来讲解一下…
"Given an directed graph, find out the minimal set of vertex such that all vertex not in the set have atleast one edge in the set." - P!=NP (TESTGEN)
这道题是为上一道题出测试数据 (想起 SRM 了), 以上一道题 submit 的代码跑的情况评分. 因为前一道题没看懂, 加上最后还有 10 分钟的时候才开写, 所以输出了一个基本是完全图的图草草了事. 这道题至今还没出成绩. - Arbit Code (ARBIT)
此题做的比较爽. 给一段会 TLE 的代码 (实际测试证明还会 RE), 要求改成能够 AC 的代码. 不知道代码是干什么的, 只有数据范围.
这道题我们的做法是, 把一个范围内 (刚开始是 1~20, 后来为了测试增加到了 1~50) 的所有输入全部打出来, 然后分析规律.
刚开始的成果是, 求 f(a, b)的时候, 把 b 从 1 到 a 列出表格, 发现每到 a 的约数才发生变化.
接下来我发现对于素数和素数的幂, 它们的 f 的变化规律是按照比它小的幂变化 (不太好描述, 想知道的话自己输出几个比如 a = 27 或者 16 就能发现了).
然后木木又发现了 f(a, 1) = phi(a) (这里 phi 是欧拉函数).
最后时刻木木大胆猜测:
当 b = 1 时, f(a, b) = phi(a);
当 b 不是 a 的约数 (a % b != 0) 时, f(a, b) = f(a, b – 1);
当 b 是 a 的约数时, f(a, b) = f(a, b – 1) + f(a / b, 1).
然后写了个 code submit 上去, 挂了.
差点就认为这个推测不对, 但是本地测试 100 以内的数据发现和给出的程序输出完全匹配.
最后偶然发现, 有一句要做 t * ((i – 1) / i) (不用说也知道是求欧拉函数时候写的), 我当初写的是 t * (i – 1) / i, 而 t * (i – 1) 会爆掉 int… 改成 t / i * (i – 1) 就 AC 了. - Give It a try (THINK)
这道题是最有意思的, 要求破解三个密码, 没有任何提示.
第一个密码很简单, 一篇文章, 把里面所有的大写字母挑出来拼在一起, 就是答案了.
第二个密码是一个 32 * 241的 01 矩阵, 最后也不知道是啥意思, 只知道答案是 2.
第三个密码, 刚开始一看就感觉是一个简单的 26 个字母的置换, 然后还推出了 p => e, 另外还找到了三个 p 连在一起的一个突破口. 但是无奈没有破解经验, 加上文章里竟然 26 个字母都是齐全的, 让我有点打退堂鼓, 所以没有一鼓作气破解出来, 很遗憾. 其实想想, 当初直接按照统计学的字母出现频率解密, 然后再做微调, 应该都可以把密码破出来了… 很无奈.
比赛基本就是这样, 最后的 1234 分真的不是有意为之… 运气比较好吧.
——————-我是爱情的分隔线——————-
今天情人节, 白天在家待了一天 (本来说要和 lxc, djs 去打台球, 一想今天人应该多就没去), 晚上去 FNOI (还迟到了), 就这么度过了情人节.
放一张图, 从 M67 那里看到的, 来源是 Abstruse Goose (来源页面).
祝各位情人节快乐, 估计我能在本科上完之前找到第一个 GF 就很不错咯… 光棍节还可以一直过下去, 很满足很满足…
p.s. 文章写完正好 0:00, 情人节过去了… 这篇文章的分类想了很久是 About Computer 还是 About
Life, 最终还是放在了前者里…