Project Euler 328

发表于 分类于 阅读次数： 本文字数： 4.3k 阅读时长 ≈ 4 分钟

Project Euler 328

题目

We are trying to find a hidden number selected from the set of integers \(\{1, 2, \dots, n\}\) by asking questions. Each number (question) we ask, has a cost equal to the number asked and we get one of three possible answers:

  • “Your guess is lower than the hidden number”, or
  • “Yes, that’s it!”, or
  • “Your guess is higher than the hidden number”.

Given the value of n, an optimal strategy minimizes the total cost (i.e. the sum of all the questions asked) for the worst possible case. E.g.

If \(n=3\), the best we can do is obviously to ask the number “\(\mathbf{2}\)“. The answer will immediately lead us to find the hidden number (at a total cost = \(2\)).

If \(n=8\), we might decide to use a “binary search” type of strategy: Our first question would be “\(\mathbf{4}\)“ and if the hidden number is higher than \(4\) we will need one or two additional questions.

Let our second question be “\(\mathbf{6}\)“. If the hidden number is still higher than \(6\), we will need a third question in order to discriminate between \(7\) and \(8\).

Thus, our third question will be “\(\mathbf{7}\)“ and the total cost for this worst-case scenario will be \(4+6+7=\color{red}{\mathbf{17}}\).

We can improve considerably the worst-case cost for \(n=8\), by asking “\(\mathbf{5}\)“ as our first question.

If we are told that the hidden number is higher than \(5\), our second question will be “\(\mathbf{7}\)“, then we’ll know for certain what the hidden number is (for a total cost of \(5+7=\color{blue}{\mathbf{12}}\).

If we are told that the hidden number is lower than \(5\), our second question will be “\(\mathbf{3}\)“ and if the hidden number is lower than \(3\) our third question will be “\(\mathbf{1}\)“, giving a total cost of \(5+3+1=\color{blue}{\mathbf{9}}\).

Since \({\color{blue}{\mathbf{12}}}>\color{blue}{\mathbf{9}}\), the worst-case cost for this strategy is \({\color{red}{\mathbf{12}}}\). That’s better than what we achieved previously with the “binary search” strategy; it is also better than or equal to any other strategy.

So, in fact, we have just described an optimal strategy for \(n=8\).

Let \(C(n)\) be the worst-case cost achieved by an optimal strategy for \(n\), as described above.

Thus \(C(1) = 0, C(2) = 1, C(3) = 2\) and \(C(8) = 12\).

Similarly, \(C(100) = 400\) and \(\sum \limits_{n = 1}^{100} {C(n)} = 17575\).

Find \(\sum \limits_{n = 1}^{200000} {C(n)}\) .

解决方案

令\(N=200000\)。一次猜测相当于在集合 \({1,2,\dots,n}\) 上选一个关键字 \(k\)，并得到三种结果：

  • 命中：结束；
  • 更小：转入 \([1,k-1]\)；
  • 更大：转入 \([k+1,n]\)。

因此任何策略都等价于一棵二叉搜索树（BST）：节点是被询问的数，左右子树分别对应更小、更大。对某个隐藏数 \(x\)，实际支付的总代价是从根走到 \(x\) 的路径上所有节点值之和。

不难直接想到用DP求解。令区间最优最坏代价为\(F(l,r)\)，那么不难写出其状态转移方程：

\[F(l,r)= \left \{\begin{aligned} &0 & & \text{if}\quad l\ge r \\ &\min_{k\in[l,r]}\left\{ k+\max(F(l,k-1),\ F(k+1,r))\right\}. & & \text{otherwise}\quad \\ \end{aligned}\right.\]

其中，第一行是边界，第二行则是极小极大递推：哪怕是进入了较差的分支，损失也要最小。

题目所求\(\displaystyle{C(n)=F(1,n), \sum_{n=1}^{N}C(n)}.\)因此，\(F(l,r)\)不足及解决本题。

把根猜测记为 \(g\)。那么最坏代价一定是 \[ C(n)=\min_{1\le g\le n}\left(g+\max(C(g-1),\ F(g+1,n))\right). \] 关键难点在于如何快速计算上侧区间 \(F(g+1,n)\)。

设上侧区间长度\(k=n-g,\)则上侧就是长度为 \(k\) 的后缀区间\([n-k+1, n].\)

定义一个专门函数： \[ H(k,n)=F(n-k+1,\ n). \]

于是

\[ C(n)=\min_{k\in[1,n-1]}\left\{(n-k)+\max(C(n-k-1),\ H(k,n))\right\}. \]

也就是说，\(H(k,n)\)等价于：在键集合 \(\{n-k+1,\dots,n\}\) 上构造一棵“最优”的二叉搜索树，使得“根到某个键的路径和”的最大值最小；在选定的那棵树上，\(H(k,n)\)就是最大路径和。

在后缀区间 \({n-k+1,\dots,n}\) 中，数值整体偏大。路径上每多询问一次就会额外付出一个接近 \(n\) 的代价，因此对后缀子树的优化具有明显倾向：

  1. 优先最小化高度：在节点值整体很大时，增加一层深度通常比“稍微换一下根的位置”更昂贵。
  2. 在同高度下，深叶尽量靠左：因为越靠左的键越小，把更深的叶放在更小的键一侧会减小最坏路径和。

把这两点合并，可将后缀子树限制到一种形状：节点按层尽量填满，最后一层从左到右填（即完全二叉树），且更深的部分出现在左边。这样后缀子问题 \(H(k,n)\) 不需要真正建树，而可以沿着“最坏分支”用计数方式直接求路径和。

因此，\(H(k,n)\)确实就变成“在这棵完全二叉搜索树上找最坏分支路径和”。

对完全二叉树，我们不需要不需要建树，只要在计数意义上知道“本层能容纳的满子树大小”，就能决定最坏分支落到左还是右，并把根的数值加进答案。

设后缀规模为 \(k\)，右端点为 \(n\)。令\(\texttt{next}=2^h-1\)表示“下一个满树规模阈值”，使得当前 \(k<\texttt{next}\)。令\(b=\left\lfloor\dfrac{\texttt{next}}{2}\right\rfloor=2^{h-1}-1.\)

这里 \(b\) 可视作“上一层满树节点数”。若恰好 \(b=k\)，说明实际上高度应更小一档，因此令\(b\leftarrow \left\lfloor\dfrac{b}{2}\right\rfloor.\)

在 complete tree 中，最后一层最多还能额外容纳 \(b+1\) 个节点。根据填充位置，最坏分支会落在右侧或左侧，对应如下判定：$ k>b+.$

  • 若条件为真（最坏分支进入右侧更深部分），根值为\(\mathrm{root}=n-k+(b+1),\)并更新\(k\leftarrow k-(b+1), b\leftarrow\left\lfloor\dfrac{b}{2}\right\rfloor,\)且 \(n\) 不变。
  • 否则（最坏分支进入左侧），根值为\(\mathrm{root}=n-\left\lfloor\dfrac{b}{2}\right\rfloor,\)并更新\(s=\left\lfloor\dfrac{b}{2}\right\rfloor+1,k\leftarrow k-s,n\leftarrow n-s,b\leftarrow\left\lfloor\dfrac{b}{2}\right\rfloor.\)

把每一步的 \(\mathrm{root}\) 累加，直到 \(k=1\)（只剩一个数无需再问），即可得到 \(H(k,n)\)。

对固定 \(n\)，候选值为\((n-k)+\max(C(n-k-1),H(k,n)).\)

实践中（并与题目讨论区常见结论一致），最优后缀规模 \(k\) 随 \(n\) 单调不减，这是因为随着\(n\)的增大，如果\(k\)递减，左右两侧占用的代价会更加失衡；利用这一点，可以在线性推进 \(n\) 的同时维护当前最优 \(k\)，并只尝试少量“倍增步长”的候选更新，从而把整体复杂度压到近似 \(O(N\log N)\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
N = 2 * 10 ** 5


def suffix_cost(k: int, n: int, nxt: int) -> int:
    """
    计算 H(k, n) = F(n-k+1, n)：
    即“隐藏数一定落在后缀区间 [n-k+1, n] 内时，在某种（近似最优的）完全二叉搜索树形状下，
    根到目标节点的最坏路径（路径上询问值之和）的值”。

    这里的实现并不显式构造 BST，而是利用“完全树（complete）+ 深层尽量靠左”的结构，
    沿着“最坏分支”逐层往下走，并把每一层的根节点值累加起来。

    参数
    ----
    k   : 后缀区间长度（>=1），区间为 [n-k+1, n]
    n   : 区间右端点
    nxt : 一个梅森数阈值 2^h - 1，用于表示当前 complete 树的高度级别
          要求 k < nxt。（外层 DP 会维护这个 nxt）

    返回
    ----
    int : H(k, n) 的估计值（在该 complete-tree 策略下的最坏路径和）
    """
    # k==1 时后缀只有一个数，已经确定，无需再问，代价为 0
    if k == 1:
        return 0

    # b 表示“上一层满树”的规模（节点数），用于决定本层如何分裂
    # 若 nxt = 2^h - 1，则 b = 2^(h-1) - 1
    b = nxt // 2

    # 如果 b 恰好等于 k，说明 k 其实正好是一个满树规模，
    # 在这里我们希望把它视作更低一档高度来处理（避免边界退化）
    if b == k:
        b //= 2

    # ans：沿最坏分支累加得到的路径询问代价
    ans = 0

    # kk, nn 是“当前还需要处理的后缀规模”和“当前区间右端点”
    # 随着往下走，区间会被切掉一部分，因此 nn 可能会变小
    kk = k
    nn = n

    # 当 kk > 1 时，说明当前子问题里至少还有 2 个候选数，需要继续询问
    while kk > 1:
        # complete tree 的结构：在规模 kk 的集合上，根会把集合分裂成左右两部分
        # 这里用 b (上一层满树规模) 来判断“最坏分支”会落到哪一边。
        #
        # 条件 kk > b + (b+1)//2 的含义：
        # 最后一层额外节点如果超过一半，会导致右侧也出现更深的节点，
        # 由于右侧键值更大、且更深会增加路径和，最坏情况会跑到右侧更深部分。
        if kk > b + (b + 1) // 2:
            # 走“右侧更深部分”的最坏分支：
            # 根位置可以写成：left_size = b+1（切掉一个前缀），根键值 = nn-kk+(b+1)
            # 直观理解：后缀区间起点是 nn-kk+1，往右数 (b+1) 个位置作为当前根
            ans += nn - kk + b + 1

            # 进入右侧子问题：规模减少 (b+1)
            kk -= b + 1

            # 下一层的 b 对应高度减一，因此 b 右移一半
            b //= 2
        else:
            # 否则最坏分支走“左侧”（深叶靠左的那部分）：
            # 当前根取在靠近右端点的中位处：root = nn - b//2
            ans += nn - b // 2

            # 进入左侧子问题时，会切掉 (b//2 + 1) 个元素（含根及其右侧那部分结构）
            step = b // 2 + 1
            kk -= step

            # 区间右端点 nn 也相应左移 step（因为我们等价于在更小的后缀区间里继续）
            nn -= step

            # 同样进入下一层，高度减一
            b //= 2

    return ans


def solve(N) -> int:
    """
    计算 sum_{n=1..N} C(n)：
    C(n) 为在 1..n 上猜隐藏数、每次猜 k 付 k 的代价、要求最坏情况总代价最小的最优值。

    该实现的核心是：
    - 用一维数组 C[n] 递推，每次只维护一个“当前最优后缀规模” knots
    - 对每个 n，只尝试少量的 knots 增量（按 2 的幂次试探），利用 knots 的单调性与块增长性质
    """
    # C[n] 存储 C(n)
    C = [0] * (N + 1)
    C[1] = 0

    # knots 表示当前认为“最优的右侧后缀规模 k = n-g”
    # 即当前 first guess 取 g = n - knots
    knots = 1

    # nxt 是梅森数阈值 2^h - 1，用来表示 knots 所处的高度级别
    # 典型序列：3, 7, 15, 31, ...
    # 维护不变式：knots < nxt
    nxt = 3

    # maxadd 用于限制我们试探 knots 的增量范围（也是按 2 的幂增长）
    # 实际上相当于对“下一次 knots 可能增长到多大”做一个动态上界
    maxadd = 1

    # total 累加 sum_{n=1..N} C(n)
    total = 0

    for n in range(1, N + 1):
        if n == 1:
            # C(1)=0
            total += 0
            continue

        # 令 first guess 为 g，则右侧规模 k = n-g
        # 这里使用当前 knots 作为候选 k，因此 g = n - knots
        g = n - knots

        # “左侧最坏情况”代价：
        # 若隐藏数 < g，则本次询问支付 g，然后进入 [1..g-1]，
        # 该子问题的最优最坏代价为 C(g-1)
        best = g + C[g - 1]

        # “右侧最坏情况”代价：
        # 若隐藏数 > g，则进入后缀区间 [g+1..n]，长度为 knots
        # 在该后缀区间内的估计最坏代价为 suffix_cost(knots, n, nxt)
        up = g + suffix_cost(knots, n, nxt)

        # 整体最坏代价是左右两边的 max，因此取较大者作为当前策略的最坏代价
        if best < up:
            best = up

        # 尝试把 knots 增加一些（按 2 的幂次试探），看是否能进一步降低最坏代价
        add = 0

        # 经验/结构性结论：当 knots>=7 后，增长往往以 8,16,32,... 的块推进；
        # 否则从 2 开始尝试更合适
        a = 8 if knots >= 7 else 2

        # 约束：
        # - knots + a <= nxt：保证在当前高度级别里试探（nxt 是当前层可容纳的阈值）
        # - a <= maxadd * 2：限制试探深度，避免每次都扫太多
        while knots + a <= nxt and a <= maxadd * 2:
            # k 不能 >= n（否则 g<=0，不合法）
            if knots + a >= n:
                break

            # 新的后缀规模为 knots+a，对应 first guess gg = n - (knots+a)
            gg = n - (knots + a)

            # 在该 first guess 下，如果走右侧后缀，代价为 gg + H(knots+a, n)
            # （这里的实现只需要比较这一项就能更新 best，是因为该类试探主要影响右侧形状，
            # 结合 knots 的维护方式，整体比较仍然有效）
            cand = gg + suffix_cost(knots + a, n, nxt)

            # 如果 cand 更小，说明这种更大的后缀规模更好
            if cand < best:
                best = cand
                add = a

            # 继续按 2 倍增量试探
            a *= 2

        # 记录 C(n)，并累加
        C[n] = best
        total += best

        # 如果发现更优的增量 add，就更新 knots
        if add:
            knots += add

            # knots 达到当前阈值 nxt 时，说明高度级别需要提升：
            # nxt 从 (2^h-1) 更新到 (2^(h+1)-1) = 2*nxt + 1
            if knots == nxt:
                nxt = nxt * 2 + 1

        # 如果本次增长超过历史最大增长，则更新 maxadd（保持它也是按 2 的幂次增长）
        if add > maxadd:
            maxadd *= 2

    return total


ans = solve(N)
print(ans)