HackerRank University CodeSprint 3

这是上周周末(9月29日~10月1日)的University CodeSprint 3。一共有7道题,但是只会做4道…其中第4道还是在网上搜索时搜出来的。

难度就用颜色表示:■■■■■■■■■■

  1. A Small Step Towards Calculators
    就是给定A{四则运算}B这么个字串,输出计算的结果。
    因为题目中不会有负数,所以可以用std::cin读入第一个数,再读运算符,再读第二个数,就完成了。
  2. Erupting Volcanoes
    就是格子中有若干火山,火山有随距离而减小的影响值,这值可互相叠加。那末要在给定所有火山时,求格子中最大的影响值。
    比较像LeetCode或是LintCode中的数邮局的题目。
    可以直接遍历每个格子,什么优化都不用加,也能完成。
  3. The Snake Vs The Wind
    贪吃蛇从格子的四角中的某角以某个方向出发,以贪婪的方式选定当前方向,直到遍历完所有格子,问蛇的轨迹。
    或者说,遇墙或遇到自己的身体就会往左或往右转,具体往哪里转依赖于当前风向:贪吃蛇偏向于顺风而行,垂直于风而行次之,逆风而行再次之。
    那就应该用模拟的方法,把蛇的方向模拟出来。用了一个Vec2 { int x, y; }来表示方向。在选定方向时以风向与方向的点积作为排序依据取最大者。
  4. Bob’s Game
    棋盘格上有墙和国王,国王可往左/上/左上移动,不可移至墙中;国王可以相互重叠。Bob与Alice依次行动,每次行动可以移动一个国王。两个玩家都是理性的。当前玩家若无法行动则输。求问给定棋盘Bob是否必胜,若必胜则第一步有多少种不同的走法。
    这篇文章所说,这个题目是一个「组合博弈」=「Combinational Game Theory」问题。是由「棋盘上仅有一个国王」这种简单的博弈问题重叠在一起而成的。只要对棋盘格求「S-G值」=「Sprague-Grundy」值,然后把所有国王所在的格子的S-G值进行XOR,就可知当前局势下,Bob是否能必胜。具体求取的方法是对所有出结点的S-G值的集合进行Mex=Minimum Excludant运算。在此题目中,该运算只可能得到0、1、2、3这四个值。
    题目中问的是Bob有多少种行动方式。那可以罗列不同的行动方式,再判定当前Alice是否必输。在罗列时欲求新的总体XOR的方法有点像快速求矩阵中「除了这个元素以外的所有元素的乘积」的方法。这样就能知道Bob的第一步有多少种行动方式了。
  5. Black White Tree 【事后知道了解法】
    无向树有黑色和白色结点。定义在某子树中白色结点数减去黑色结点数的差值的绝对值为「怪异指数」。求此树中最怪异的子树为何,并列出该子树中所有结点。
    如果从所有叶子结点开始向中心「爬山」,然后从最高处开始向外搜索,这样可以得到部分的分数…错误原因需要检查一下
    Update:解法类似打劫房屋;随意取某个点为树的根,然后罗列出从每个结点开始的子树中「怪异指数」最大者;取得之后再在回溯的过程中将解重建出来便是。在这里得到的收获就是「随意取一个结点作为根」并「罗列以每个结点开始的子树的情况」
  6. March of the King 【只得了部分分数】
    乍一看好似「Word Search」的变体。不过格子大小是固定的8×8,并且欲搜索的词也只有一个。
    直接做会有一半超时,如果将欲搜索的词的后四位存入std::vector中,则可以只有最后两个输入超时…(后4位是试出来的比较好的参数,太多或太少了都会更慢)还需要检查一下
  7. Simple Tree Counting 【只得了部分分数】
    无向树中的边有若干元素。为每个同样颜色的边组成的连通分量定义「Productivity」为N(N+1)/2,其中N为结点数。
    有许多Query,可能会改变边的颜色。需要频繁地求「某种颜色的所有连通分量的Productivity之和」与「包含某边的连通分量的Productivity」。直接做能拿到部分分数。
    猜想可能需要一些高级数据结构进行优化。

接下来…要对照一下正确解答,看一下后面三题怎么做。

话说在HackerRank上如果表现好是会有猎头来联系的!不过这回因为已经早早接了别家了所以就只能说「以后再保持联系」啦。

此条目发表在Programming分类目录。将固定链接加入收藏夹。