Codingame本周谜题「折纸曲线」解
- 2019 年 11 月 30 日
- 筆記
Codingame.com Puzzle of the Week: Paper folding curve
题目简述
一张纸，一直保持向同一个方向对折，然后将折痕展成直角。从侧面看去，纸的折角会构成一个折线。 从纸的一端出发到另一端，每碰到一个折角，用1表示向左折，0表示向右折，则所有折角会构成一个1与0组成的序列，称为折叠序列。比如折一次是1，折两次是110，依次类推。 给定折叠次数，要求输出折叠序列中自s至e号元素（0-index，均包含）。
朴素解法
首先，不妨假定我们每次都向左对折，因为如果是向右，我们可以从另一侧观察，则还是向左对折。然后我们来研究下序列的特点。
- 对折$n$次将产生$2^n$小段的纸，$2^n-1$个折痕。也说是说序列长度为$2^n-1$，不妨在第1位补个1，序列变成1-index，共有$2^n$个元素。
- 考察对折点，对折点之前的纸和对折点之后的纸走向完全一致，即序列关于对折点对称，但由于先进方向相反，原来是向左的对称之后变成向右。所以准确说应该是序列关于对折点反向对称
- ** 序列与对折次数无关**。观察上图，折叠2次的折痕是①②③，而再折叠一次，序列①②③④⑤⑥⑦的前三项将与折叠两次的一致。就好像把纸延长了相同的长度，再把后续的折痕加在原序列后面。所以题目中「给定折叠次数」是用不上的。
由1及题设，第$2^n$个元素值恒为1。由1+2，序列的对折点所在是其实是第$2^{n-1}$个元素。又由2+3，序列关于$2^{n-1}$号元素对称，左半部分又关于$2^{n-2}$号元素对称，依次类推。转换成数学语言，用$f(i)$表示序列中第$i$号元素的值，则：
begin{equation} begin{split} f(2^n)&=1,,&n=0,1,ldots \ f(2^n+x)&=sim f(2^n-x),,&0<x<2^n,,n>1 end{split} end{equation}
其中"~"表示将值取反。所以如果我们已经得到了序列前$2^n$项的值，我们就能根据对称性得到$2^{n+1}$项的值，写成伪代码如下：
// 写出前7项 result = '1101100' while len(result) < e + 1 result += '1' + reverse_and_flip(result) end print(result[s:e])
时间复杂度为$8+16+cdots=O(N)$，其中$N=2^n$为全序列长度。提交运行，前面都能PASS，但当s, e都非常大时挂了，果然还是太朴素。
优化解法
我一直在思考：序列某个元素的值由前面的某个值得到，而前面的某个值又由更前面的某个值得到，最后的种子其实就是最开始的几个元素。我们浪费了很多时间在生成不需要输出的结果上。本能觉得，对某个特定元素，可能可以仅通过它的序号，在$O(1)$的复杂度上得到值。说干就干，继续找找规律。由上述的公式，我进一步发展，当$xneq2^{n-1}$时， begin{equation} begin{split} f(2^n+x)&=sim f(2^n-x) \ &=sim f(2^{n-1}+(2^{n-1}-x)) \ &=f(2^{n-1}-(2^{n-1}-x))=f(x) end{split} end{equation}
当$x=2^{n-1}$时，
$$f(2^n+x)=sim f(2^{n-1})=0$$
Exciting! 如果我们把元素序号用二进制表示的话，通过以上方法，我们就能使序号快速缩小（去掉首位的1）到一个很小的数，进而得到它的值。具体地：
- 数字除去末尾的0后，如果是以连续的1结尾，则值为0
- 否则，值为1
伪代码如下：
result = '' // 修正0 - index到1 - index for i in [s + 1:e + 1] // i是2的幂，快速返回 if i & (i - 1) == 0 result += '1' break end // 去掉末位的0 while i & 1 == 0 i >>= 1 end if i & 3 == 3 // 11结尾 result += '0' else // 01结尾 result += '1' end end print(result)
时间复杂度近似为$O(e-s)$。
一开始从一个实际问题出发，最后得出了一个简洁的数学表达，果然是代码令我愉快。完整代码(Python)见 https://github.com/frostming/Codingame/blob/master/Puzzle-of-the-Week/paper_folding_curve.py
