Codewars C++练习:Insane Coloured Triangles

题目

题目链接:

This Kata is an insane step-up from Avanta’s Kata, so I recommend to solve it first before trying this one.

A coloured triangle is created from a row of colours, each of which is red, green or blue. Successive rows, each containing one fewer colour than the last, are generated by considering the two touching colours in the previous row. If these colours are identical, the same colour is used in the new row. If they are different, the missing colour is used in the new row. This is continued until the final row, with only a single colour, is generated.

For example, different possibilities are:

With a bigger example:

You will be given the first row of the triangle as a string and its your job to return the final colour which would appear in the bottom row as a string. In the case of the example above, you would be given ‘RRGBRGBB’, and you should return ‘G’.

1 <= length(row) <= 10 ** 5

题解

核心规律

找到所有递推方程的共性:“所有递推小三角形,都满足RGB的个数在模3意义下相同”。

单独考虑任意一个大三角形的第一行和第二行,倘若我们知道了第一行RGB分别有多少个,我们也可以通过“RGB的个数在模3意义下相同”这个性质,计算出第二行分别有多少个RGB。这个是一个很有启发作用的思路,虽然这个思路无法解决更多的行,但是从该思路出发,我们可以得到如下的算法——

用三元组S_{x,y}=(r,g,b)表示一个位置的颜色。一方面,我们定义映射f来求任意三元组对应的颜色.

f = \{(r,g,b) r,g,b \in \mathbb{Z}\} \rightarrow \{\boldsymbol{R},\boldsymbol{G},\boldsymbol{B}\}

另一方面,不同的三元组有很多,但是颜色的种类总共就3种,所以我们需要对于该三元组建立若干“等价类”,规则如下:

  1. (1,0,0)\rightarrow \boldsymbol{R}(0,1,0) \rightarrow  \boldsymbol{G}(0,0,1)\rightarrow \boldsymbol{B}
  2. f((r,g,b)) = f((r \bmod 3, g \bmod 3, b \bmod 3))
  3. f((r,g,b)) = f((r-v,g-v,b-v))

规则1定义了三元组到颜色的映射,而规则2和规则3将所有三元组分为了3类。

仔细理解一下这三条规则,我们很容易求出一个三元组对应的颜色,例如f((123,123,400)) = f((0,0,277))=f((0,0,1)) \rightarrow \boldsymbol{B}。当然,并不是所有三元组都可以通过这种方法计算出值,倘若一个三元组无法求出值,如(0,0,0),那么在本题中,它就是不合法的。

但看三元组的定义或许会莫名其妙,但是我们可以将本题的规则引入,得到一个暴力的迭代方式——

对于整个三角形的第一行,可以直接按照定义式生成:

S_{0,y} = ([row[0]==\boldsymbol{R}],[row[0]==\boldsymbol{G}],[row[0]==\boldsymbol{B}])

例如,一个\boldsymbol{G}颜色可以用三元组(0,1,0)表示。

对于后续的行,我们可以按照递推式生成——

S_{x,y} = -S_{x-1,y} - S_{x-1,y+1}

例如,倘若S_{x-1,y} = (1,0,0) \rightarrow \boldsymbol{R}S_{x-1,y+1} = (0,1,0) \rightarrow \boldsymbol{G},那么S_{x,y} = (-1,-1,0) \equiv (0,0,1) \rightarrow \boldsymbol{B}

读者到这里应该就可以发现,实际上我们的三元组完全是为了反映递推方程中的等价信息而设计的。这里,我们已经可以设计出时间复杂度O(N^2)的算法了。

既然我们已经借助三元组的加减运算,定义出了一个新的数域来解决这个问题,并且该数域很容易证明满足封闭性。反映到代码上,就是我们成功定义出了一个支持加操作和相反数操作的“数”status,那么我们完全可以不再考虑status类的实现细节。

所有细节略去之后,我们的代码实际上就是上面的65-69这5行。有一些编程基础的读者已经发现这里非常像一个组合数的递推方程(或者说是杨辉三角形的生成代码)。

对于一个稍微简单一些的例子,我们对于第一行的所有值赋予一个标号,看看最终结果长什么样的:

上表中,a,b,c,d,e分别是我们读入的第一行的三元组表示,而最后一行就是答案!因此,假设读入三元组列表为s_i那么答案就是

ans =(-1)^{n-1}\sum_{i=0}^{n-1} C(n-1,i) \cdot S_i

最后一步比较tricky,需要一些较深的数论知识,最后一步我们需要求出C(n-1,i)在模3意义下的值。这一步有两个做法——

  • 有现成的Lucas定理专门用来计算这个问题。
  • 可以手工迭代求出C(n-1,0),\dots,C(n-1,n-1)的值,可以用递推式C(n-1,i+1) = C(n-1,i) \cdot (i+1) / (n-1-i)求,这其中又有两个要点
    • 在迭代的乘法需要将所有的因子3提出来
    • 在迭代的除法中需要计算除数在模3同余系下的逆元

在标程中使用了第二种做法。

 

原创文章地址:【Codewars C++练习:Insane Coloured Triangles】,转载时请注明出处mhy12345.xyz

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.