Archive for the “gao” Category

前几天,秋叶拓哉(iwi)、岩田阳一(wata)和北川宜稔(kita_masa)所著,我(watashi)、庄俊元(navi)和李津羽(itsuhane)翻译的《挑战程序设计竞赛》,终于通过人民邮电出版社正式出版了。可喜可贺,可喜可贺。有关该书的简介,目录、试读和购买链接请通过传送门访问。这里我主要想说一下自己为什么要翻译和推荐本书,还有对程序设计竞赛学习资料的一些看法。也附带一些对译者序和第1章的补充说明。

Comments 71 Comments »

通常在Online Judge上的题目要求程序从标准输入流(standard input, stdin)读入输入数据,将答案输出到标准输出流(standard output, stdout),并通常会无视标准错误输出流(standard error, stderr)的输出。当然,过多的stderr输出必然会占用许多额外的时间,导致TLE,所以即使把debug信息输出到stderr,有时也要注意通过注释和条件编译去掉for循环中的debug语句。不过更多的时候,我们主要需要关心的还是stdin和stdout。

不过有时候,某些Online Judge的某些题目就会要求从给定文件读入测试数据,或将结果输出到给定文件中,或二者皆有。大多数编程语言在提供文件IO操作API的同时,都提供有许多直接操作标准输入输出的API。而很多初学者对这些API都要比对文件操作的API熟悉得多。所以如果在此时,能用标准输入输出的API来替代文件输入输出的API无疑是很方便的。在本地,这可以通过shell的重定向轻松办到

./p.exe < input.txt > output.txt 2> log.txt

不过在Online Judge上,这一点就行不通了。好在很多语言都提供有一些API,能实现类似的功能。

除了希望使用标准输入输出的API来实现文件输入输出外。在本地调试程序的时候,有时候通过终端(屏幕)进行交互会方便得多,即使要进行文件输入输出也可以借由shell轻松自如的选择文件。所以,程序在本地使用stdio,而在Online Judge上才使用指定的文件会方便不少。

当然,前面还漏了一点,用标准输入输出的API除了可以节省力气外,还有一个好处是:如果同样一道题,在多数OJ上要用标准输入输出,但有些OJ要求文件输入输出时,代码无需经过太多修改就能AC。嗯,其实我就是在做Codeforces上新加的Andrew Stankevich Contests想到可以做这么一个总结的。下面的代码都用Think Positive这道题测试过,可以AC的完整代码请通过github访问。

Comments 5 Comments »


Andrew Stankevich’s Contest #7
ZOJ2604 Little Brackets 25.07% (250/997)
ZOJ2605 Under Control 28.44% (93/327)
ZOJ2606 Holidays 8.54% (27/316)
ZOJ2607 Laboratory 25.00% (104/416)
ZOJ2608 Maps 27.02% (20/74)
ZOJ2609 Crazy Painter 23.23% (89/383)
ZOJ2610 Puzzle 28.92% (105/363)
ZOJ2611 Quest 21.27% (30/141)
ZOJ2612 Stable Sets 29.43% (88/299)

Codeforces也开始挂ASC了,这我才想起,ZOJ上11套ASC的解题报告我还差一份作业没交呢,于是在此补上。目前把ZOJ上的ASC打完了,期待Codeforces放出更多的ASC。代码除了通过解题报告中的链接访问外,也可以在github上watashi/AlgoSolution(README)找到。


—-剧透的分割线—-

Comments 6 Comments »

本次校赛省赛只担任了打酱油的出题工作,其它事情基本没怎么参与,比赛当天也都是睡到中午去蹭饭。原本只为校赛出了ZOJ3594 Sexagenary CycleZOJ3610 Yet Another Story of Rock-paper-scissors。结果其中一题还被毙掉了,放到了省赛。

校赛当天接下了伟大光荣的出水题任务,于是这周一一口气出了ABGHJ五道题,并且把C题的idea丢给navi出了。总的来说这次省赛的题目难度特别是在代码量上要比去年省赛低得多,毕竟出题的人也是很懒的= =||。ZOJ3610 Yet Another Story of Rock-paper-scissors属于逗你玩的秒杀题,输入三个字符串,输出中间那个。ZOJ3600 Taxi Fare属于if-else基础编程题,偶尔让人WA一下。ZOJ3609 Modular Inverse属于坑死你简单题。其实这些题就是拿来做ranklist的区分度用的,也让实力较弱的选手不会觉得整场太无聊。

ZOJ3607 Lazier Salesgirl也算是一个水题,枚举即可。其加强版ZOJ3606 Lazy Salesgirl需要利用线段树优化,不过这个线段树没有任何区间操作,只需要约10行的点的修改操作即可。ZOJ3602 Count the Trees不知道为什么很多人选择了hash,而且比较意外的是这题hash很容易WA的样子,出数据的时候似乎完全没有想到。ZOJ3601 Unrequited Love是唯一一道数据比较难出的题,比赛时卡住了大部分错误的算法,被一个队伍压TL水过了,然后有个Java提交算法应该是正确的,不过这题真不保证Java不会TLE。

最后附上省赛最终ranklist

Comments 37 Comments »

3月14日,天刚亮,我就从黄龙搭大巴去上海浦东机场。然后乘UA858去三藩,去年去美国也是这个航班。飞机早上8点半就到了SFO,然后打的到酒店checkin。问前台我和谁一个房间,结果回答是没有,走进房间一看,原来是个华丽的大床房。

下午在酒店睡了个午觉,然后晚上在liympanda和liaohongshu两位教主的掩护下,慕名去G社蹭了顿晚饭。饭后打桌球果断被完虐。

第二天早上去F社面试intern,连续45min*两面,主要就是coding或者algo的问题,大部分时间在黑板上写code。

Comments 39 Comments »