您好,欢迎来到景安网络!
加盟景安
主页 >服务器技术 >【划重点】我对TopCoder的一些看法

【划重点】我对TopCoder的一些看法


来源:景安网络发表日期:2018-07-23浏览次数:Tags:TopCoder
景安网络专业的数据中心服务商,长期提供数据中心托管服务,私有云,互联网解决方案,互联网增值服务。针对工信委大力实施“万企业上云”计划,景安以我所能,为你而+,推出千元云计算红包免费抽,核心云计算产品降幅达50%
以下是我做TopCoder(简称TC)的一些总结,希望对你有所帮助。
 
TopCoder
 
1、题目形式
 
TopCoder和大多数OJ的题不太一样,大多数OJ都是使用用标准输入输出,而TopCoder只需实现一个关键的类(class)中的一个函数即可。函数传入的参数和返回值取代了标准输入输出。
 
TC的输入输出规模比较小,大多数题的数据范围都在 5050 以内,这是因为太大的数据点超出了Arena的容纳范围。事实上数据范围只有 5050 的题仍然颇有难度,这一点在之后会提到。
 
大多数的题目和日常做的OI题还是很类似的,但侧重点不一样。TC的组合计数以及组合优化类问题比较多,大多数题的主要难点在于思维上(当然也不乏代码题),很多题都是“暴力是指数级复杂度,难点在于想出一个多项式算法”,例如SRM 577的500,只要想到DP状态如何设计,很高的复杂度都能通过。当然也有一些 O(n3)O(n3) 卡 O(n4)O(n4) 之类的题,通常需要用特殊的方式进行输入(如输入字符串解密数字,输入随机数种子递推出随机数)。
 
2、解题遇到的困难
 
TC题比较难(当然是对我而言,对于C_SUNSHINE、matthew99、immortalCO等神犇来说应该是比较容易的?),我在做的时候遇到了不少的困难。
 
有一类问题,一开始看到的时候毫无思路,经过长时间多种方向的尝试最后才解决。
 
SRM 562的1000是一道有结论的树形DP问题,这题我研究了很久,终于推出了两种不同情况下的结论。其中一种情况是:2k>n2k>n 时,排列 p0,p1,...,pn−1p0,p1,...,pn−1 合法当且仅当:①pn−k,pn−k+1,...,pk−1pn−k,pn−k+1,...,pk−1 这 2k−n2k−n 个点构成一个连通块;②将该连通块删掉后,如果 pi,pjpi,pj 位于同一连通块,那么或者 i,j<n−ki,j<n−k,或者 i,j≥ki,j≥k;③对任意 i<n−ki<n−k,pi,pi+1,...,pn−k−1pi,pi+1,...,pn−k−1 构成连通块,以及对任意 i≥ki≥k,pk,pk+1,...,pi−1pk,pk+1,...,pi−1 构成连通块。想到这个结论以后我开始尝试用树形DP求出有多少个连通块大小恰为 2k−n2k−n,用树形背包的经典算法容易把满足③的排列个数也算进来,但是,对于每种选连通块的方案,贡献为满足②的把点分成 i<n−ki<n−k 和 i≥ki≥k 两类的方案数,这个我并不会统计。绕了不少弯路才发现其实是不从“对每个 [n−k,k)[n−k,k) 求有多少个 [0,n−k)[0,n−k) 和 [k,n)[k,n) 以及它们的排列方案数”考虑而是从“对每个 [0,n−k)[0,n−k)、[n−k,k)[n−k,k)、[k,n)[k,n) 求有多少个排列方案数”,也就是DP时把位于中间和位于两边的点数都计入状态。这样问题就得以解决了。事实证明这样的求和的问题转化思路是相当有趣的,以后可以出这类的题。
 
SRM 568的1000是我掉坑掉得比较久的一道题。由于每个半圆可以放上面或者下面,并且半圆不相交,我很快把问题转化成了:给一个圆和 nn 个点,给出一些连接两个点的弦,问能否把剩下的点也连起来使得每个点属于一条弦,且把相交的弦连一条边之后图是二分图。但是这样转化并没有什么卵用,依然只会解决空的点数不超过 1212 的情况。后来把转化的想法扔了,脑洞大开:能不能枚举已有的半圆的二分图染色情况(也就是放上面还是下面),然后判断是否存在可行解呢?推了不久我就推出了一个结论:当且仅当存在一种把点分为上下两类的方案,使得对每一测,每条圆弧里面的点都是偶数个。这就可以用经典的前缀xor建图了。把这种算法和暴力结合起来就能通过了。这个问题也让我体会到“是否存在一对(A,B)”既可以转化为“是否存在一个A,使得存在一个B”(枚举A,高效判定B)也可以转化为“是否存在一个B,使得存在一个A”(枚举B,高效判定A)。
 
SRM 579的1000是一个策略问题,但是这题的特点是“对方以一定方式随机,我方可以根据之前的结果决定之后的策略”,这类问题的解决方法我之前没有思考过,因此想了很久。事实上这一类问题还是有解决方法的:我们需要构造一个决策树 TT,TT 是一个 nn 层的三叉Trie树,每个节点有三条出边,边 (u,v)(u,v) 上的字母 d(u,v)d(u,v) 为 R、P、S 中的一个,目标是对每个非叶节点 vv 分配 R、P、S 三个字母中的一个作为策略 d(v)d(v),边 (u,v)(u,v)(vv 为子节点)的权值定义为我方出 d(v)d(v),对方出 d(u,v)d(u,v) 时的得分,使得对方从根开始,每次出手时根据当前节点上的字母往下走,经过的路径权值期望最大。这样只需求出每条边被经过的概率就可以对每个节点选取最优决策。虽然节点数为 O(3n)O(3n) 级别,但通过数学推导可以发现一个节点 vv 被经过的概率只和根到 vv 的路径的边上 R、P、S 的个数有关,从而设计 O(n4)O(n4) 的DP去解决它。决策树的思想是我在WC2016时讲的IOI2015 scales的解法中学到的,知识不是死的而是活的,只有灵活运用才能解决更多的问题。
 
还有一些问题,难点在细节以及实现上,有些问题花费了我大量的时间才解决。
 
SRM 549的950是一道做法很暴力的枚举题,需要枚举所有 n(n≤6)n(n≤6) 个点的分层图,对每个分层图使用网络流和状压DP(或者直接枚举)来判断是否合法。思想很简单,但枚举分层图、网络流、状压DP每一步都有细节,因此如果全都写完再调试比较难调。遗憾的是我就是全都写完再调,调不出来。事实上分部调试程序的方法是比较高效的,因为可以针对每一部分找出问题,而不是主要花费时间在遇到问题以后查哪里错了。最后这题写了一下午,调过样例的时间比写的时间长。所幸调过样例以后AC了,不知道是样例足够强还是运气比较好。这题我写了3KB左右,对我来说算比较长的了。
 
SRM 574的1050是一道看起来很可怕的题。首先这个问题需要找性质,并且这个性质极!其!容!易!推!错!反正我一开始就想错了。immortalCO跟我说他第一次也把性质推错,写了错误算法WA了。正确的性质是,网格内和网格外的每个连通块是一条路径 u→vu→v,可以缩成一条边 (u,v)(u,v),要求在网格外加一些边,使得不会有 a<b<c<da<b<c<d 的边 (a,c),(b,d)(a,c),(b,d) 出现,且每条路径深度是递增的(对于网格内的路径 (u,v)(u,v),若 xu<xvxu<xv,则定向为 u→vu→v,反之亦然,若 xu=xvxu=xv 则不定向)。一条路径不相邻的点在网格中也不相邻,实际上是限制了部分格子不能连。问题转化后可以用一个 O(n3)O(n3) 的DP解决掉。但是前面部分把网格转化为连边的模型有有相当多的细节要讨论,一不小心就错了,并且这种题难以对拍(没有什么好写的暴力)。我调了很久的样例,终于调过以后交上去还是WA了。这题一共FST了两次,两次都是细节实现上的问题。这种细节多的题我暂时还没想到什么好的方法来应对。
 
3、学习的算法
 
做TC题的过程中遇到了一些知识盲点,学习了一些新的算法。
SRM 551的1000一开始看起来就是一个生成树计数问题,但是是带约束的,不能直接上prüfer编码解决。一种暴力做法是从点权非负的点集 SS 内枚举一个点权和不超过限制的子集 TT,然后强制 ∀v∈T,∃u∈T,(u,v)∈E∀v∈T,∃u∈T,(u,v)∈E 且 ∀v∈−T,u∈S,(u,v)∉E∀v∈S−T,u∈S,(u,v)∉E。注意到集合个数只和 SS 中的点数有关,用Meet-in-the-middle统计每种大小的集合个数即可,并且前面一个限制可以通过容斥原理去掉,这样问题就转化为统计一个图 G=(V,E)G=(V,E) 中有两个点集 S,TS,T,(u,v)∉E(u,v)∉E 当且仅当 v∈S−T,u∈Sv∈S−T,u∈S 或 u∈S−T,v∈Su∈S−T,v∈S。这是一个生成树计数问题,看似没有高效的解决方法。不过有一个很神的技巧“矩阵树定理”,可以很高效的解决这个问题。于是我学习了矩阵树定理在 O(n3)O(n3) 时间内通过求行列式进行生成树计数,之后便解决了这个问题。
 
SRM 584的900根据题目意思可以转化为这样一个问题:给定图 G=(V,E)G=(V,E) 和 r∈Vr∈V,要从 EE 中选出权值和最小的边集 E′E′ 使得图 G′=(V,E′)G′=(V,E′) 中 rr 能到达所有点。如果是无向图就是最小生成树,有向图呢?应该就是算法竞赛入门经典训练指南里面的“最小有向生成树”,即“最小树形图”。可惜当时我只是了解了它的概念,并不会求出一个图的最小树形图。为了完成这题,我学习了如何用朱刘算法求解最小树形图,当然由于第一次写的时候不熟练而FST了两次。
 
4、写错过的题
 
由于我的代码能力不足,有超过10%的题没有一次通过系统测试,即第一次提交时Failed System Test(FST)了。事实上我的TC用户名为WAonSystemTest就是因为我老是过了样例交上去WA
 
SRM 548的450,看错题目,以为不可以填0,于是就错了,主要是没有看清楚题意导致的。
 
SRM 548的1000,我把组合数预处理到 N2×KN2×K,然而在程序用到了 C2iCi2,于是 K<2K<2 的时候挂了。可见虽然从题目上看大多数时候 K≥2K≥2,但还是要注意一些边界情况。
 
SRM 549的600,写的是三进制状压,由于想偷懒而开了 STL 的 map,但是我并不知道 map 的每个元素有 24B24B 的空间(不知道是不是,反正很大),这样开两个 313313 大小的 map 内存就超过 64MB64MB 了。最后改成数组才过。不少 STL 容器的内存都会比数组大,使用的时候要小心。
 
SRM 550的300,调了很久的样例,发现是题目理解有误,最后终于调过了,然而提交以后发现一个 <= 打成了 <,FST了。对于简单题也不要一调过样例就交,要多检查几遍代码看有没犯低级错误。
 
SRM 550的850,问题转化完以后相当于有不超过 1111 个 {0,1,2}{0,1,2} 中的数,允许经过不超过 mm 次操作,每次可以选取一个 xx 把它变成 (x+1)mod3(x+1)mod3,求把所有数变成 00 的方案数(方案不同当且仅当操作次数不同或某次操作的结果不同)。状态中只要记录 0,1,20,1,2 的个数即可。然而我又犯了个错误,DP的时候写成了从所有的 00 开始变成某个给定状态的方案数,这样是有问题的,因为只满足最终状态每种数的个数不一定正确,比如 (0,0,0,0)(0,0,0,0) 一步变成 (0,0,0,1)(0,0,0,1) 只有 11 种方案,而 44 个 00 一步变成 33 个 00 和 11 个 11 有 44 种方案。从当前状态递推到所有数都是 00 是正确的,因为全 00 的状态是唯一的。出现这么大的错误只能说明我对这类DP的认识还不够深入。
 
SRM 551的250,写了Two-Pointers然后右指针移动了左指针忘记移动了,挂掉。基本算法一定要写熟练,比如说,如果邻接表写挂了,那么树的题就可能无论怎么对拍都拍不出错。
 
SRM 553的1000,我写的做法大概是这样:首先找环长的最小值,用差分约束系统建图跑SPFA判定,每条边是 MM 的一个一次函数,二分一个环长 MM,如果找出一个负权环,那么当负权环上 MM 的系数小于 00 时,说明需要 MM 太大,需要减小 MM,否则需要增大 MM。直接二分在有解的时候不会出问题,在无解的时候可能系数为正和负的环同时存在,那么返回 MM 太小或者 MM 太大是不确定的,就会导致二分出的结果不正确。我实现的时候WA在了很后面的一个大点,调了挺久。判掉这种情况才能过。
 
SRM 556的1000,这题我没想出来,看了题解才做的。然后写的时候忘了限制 a1,a2,b1,b2a1,a2,b1,b2 的容量为 2an2an 或者 2bn2bn,第一次交的时候FST了,调的时候发现答案的infinity溢出了,第二次再FST以后才意识到这个问题。
 
SRM 563的1000,判断 a,ba,b 属于不同状态的时候,只判了能否使 aa 仍在棋盘而 bb 移出棋盘,没判能否使 bb 仍在棋盘而 aa 移出棋盘。这个问题用几组小数据都能查出问题,但我过了样例直接交了,导致FST。
 
SRM 565的500,预处理质数应处理到 109+106−−−−−−−−√109+106 而我只处理到 109−−−√109,手出极限数据无法发现这个问题(因为无法验证答案正确性),需要写的时候注意边界。
 
SRM 567的500,一开始问题想简单了,以为就是求个集合的交,过了样例交上去挂了。在immortalCO的提醒下我才意识到我考虑不周到,没注意到若干轮之后原本非最优的会变成最优,最后的解决方法是多加几层循环。
 
SRM 574的1050是之前提到的细节题,我在这题上犯了不少错误,既因为分类讨论一种特殊情况判错FST一次,又因为一种情况把变量名打错FST一次。暂时不知道有什么比较好的解决方法。
SRM 578的250,写了个 O(R⋅C⋅(R+C))O(R⋅C⋅(R+C)) 的BFS做法,R,C≤50R,C≤50,然后犯了和SRM 565 500一样的错误,第一次数组只开了 50×50×5050×50×50,第二次数组只开了 50×50×10050×50×100,两次都挂了。实际上应该开 50×50×10150×50×101。
 
SRM 578的1000,树形DP有一步转移要用KM算法,我把KM算法过程写成了一个模块,然后这一部分数组忘记每次清空了……于是调了很久才调出来。
 
SRM 584的900,第一次写最小树形图,细节没有考虑清楚,找环的时候 vis[j] 表示编号最小的能到 j 的点编号,但一开始初始化时写 vis[0]=1 导致和1出发的点混淆于是WA了。
 
SRM 586的250,犯了一个相当低级的错误,把 yy 集合从 nn 个点扩充成 2n−12n−1 个点的时候忘记令 n=n*2-1 了,这个也是随便出几组数据就能发现的问题,然而我只测了一些特殊构造的数据,对于随机数据反而没有测,导致这种容易出问题的错误没有查出来。
 
5、未解决的题
 
有的题我花费了大量时间仍然没有想出做法,最后不得不借助题解来完成。当然有的题在看了题解之后完成了,也有少量的题最后依旧没有完成。
 
SRM 582的1000,我没有想出来。一开始看到题目觉得条件比较复杂,不是很好下手,于是打了个表找规律,发现形如 n=abcn=abc,其中整数 a,b,ca,b,c 满足 b>a≥1,c>1b>a≥1,c>1 的 nn 似乎都满足 2≤c≤32≤c≤3,于是发现 NN 以内满足 c=2c=2 和 c=3c=3 的 nn 的个数都不难在 O(N−−√3logN)O(N3log⁡N) 和 O(N−−√4logN)O(N4log⁡N) 的时间内求出,但是这样会算重复,因为有的 nn 满足存在整数 b1>a1≥1b1>a1≥1,b2>a2≥1b2>a2≥1 使得 n=a1b21=a2b32n=a1b12=a2b23。之后一直想找出这类数有何共同点,比如能表示成 ab6ab6 等等,但想了几个结论全是错的。同时又想能否不从推出简单结论入手,也不利用性质,强行求出满足两个约束的 nn 的个数,但式子一步也化简不下去。最后束手无策。
 
最后只好去看题解,发现题解是结合了两种方法:首先使用了一个性质,如果存在整数 b>a≥1b>a≥1 使得 n=ab3n=ab3,并且 bb 是所有满足条件的 a,ba,b 中最大的,那么 nn 不能被表示为 a′b′2a′b′2(整数 b′>a′≥1b′>a′≥1)的条件是:设 k2k2 为 abab 中最大的平方因子,则 abk2≥kbabk2≥kb。这样在求和的时候可以枚举一个 kk,然后就能转化成和 gcdgcd 有关的式子,用莫比乌斯反演解决。这个思想十分妙。
 
0(好文)
0(太水)
版权声明:部分文章源于网络,如侵权请联系我们删除
1元上云

专题页