Project Euler 334

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

Project Euler 334

题目

Spilling the beans

In Plato’s heaven, there exist an infinite number of bowls in a straight line.

Each bowl either contains some or none of a finite number of beans.

A child plays a game, which allows only one kind of move: removing two beans from any bowl, and putting one in each of the two adjacent bowls.

The game ends when each bowl contains either one or no beans.

For example, consider two adjacent bowls containing \(2\) and \(3\) beans respectively, all other bowls being empty. The following eight moves will finish the game:

You are given the following sequences:

\[\begin{aligned} &t_0=123456,\\ &t_i=\left\{\begin{aligned} &\dfrac{t_{i-1}}{2}, & &\text{if }t_{i-1}\text{ is even} \\ &\left\lfloor\frac{t_{i-1}}{2}\right\rfloor\oplus 926252, & &\text{if }t_{i-1}\text{ is odd} \end{aligned}\right. \\ &\qquad\text{where }\lfloor x\rfloor\text{ is the floor function }\\ &\qquad\text{and }\oplus\text{is the bitwise XOR operator.}\\ &b_i=(t_i\bmod2^{11}) + 1 \end{aligned}\]

The first two terms of the last sequence are \(b_1 = 289\) and \(b_2 = 145\).

If we start with \(b_1\) and \(b_2\) beans in two adjacent bowls, \(3419100\) moves would be required to finish the game.

Consider now \(1500\) adjacent bowls containing \(b_1, b_2,\dots, b_{1500}\) beans respectively, all other bowls being empty. Find how many moves it takes before the game ends.

解决方案

这题最早出自Google Code Jam 2010 R3 的 C题。

把每个碗看成整数直线上的一个格点。第 \(i\) 个碗放在位置 \(i\)（从 \(0\) 开始），碗里豆子数就是该点上的数 \(c_x\)。

一次合法操作（题目唯一允许的 move）是：在某个位置 \(x\) 上取走 \(2\) 颗豆子，并分别放到相邻的 \(x-1\) 与 \(x+1\) 上。也就是\((c_{x-1},c_x,c_{x+1})\mapsto(c_{x-1}+1,c_x-2,c_{x+1}+1).\)当所有位置都满足 \(c_x\in\{0,1\}\) 时游戏结束（达到稳定态）。

设所有豆子的位置（带重数）为集合 \({p_1,p_2,\dots,p_n}\)，其中 \(\displaystyle{n=\sum_x c_x}\) 为总豆子数。

一次操作把两个豆子从 \(x,x\) 变成 \(x-1,x+1\)，而\((x-1)+(x+1)=x+x.\)因此\(\displaystyle{\sum_{k=1}^{n} p_k }\)在所有操作中保持不变。记这个不变量为

\[ S=\sum_{k=1}^{n} p_k=\sum_x c_xx. \]

同理，\((x-1)^2+(x+1)^2 = x^2+x^2+2.\)因此

\[ Q=\sum_{k=1}^{n} p_k^2=\sum_x c_x,x^2 \]

在每一步操作中都恰好增加 \(2\)。于是若总步数为 \(M\)，则必有\(Q_{\text{final}}=Q_{\text{init}}+2M\Longrightarrow M=\dfrac{Q_{\text{final}}-Q_{\text{init}}}{2}.\)

所以问题被转化为：构造最终稳定态并算出其 \(Q_{\text{final}}\)；步数立刻由上式给出。

接下来考虑一堆豌豆的稳定态。

先看只有一个位置 \(x\) 上有 \(k\) 颗豆子，其它全空。

由于规则对左右对称，最终稳定态必是“尽量对称地摊开”：

  • 若 \(k\) 为奇数：最终是一个连续段，长度为 \(k\)，以 \(x\) 为中心：\(\left\{x-\dfrac{k-1}{2},\dots,x+\dfrac{k-1}{2}\right\}.\)
  • 若 \(k\) 为偶数：最终是长度为 \(k+1\) 的连续区间里恰好空一个中心点：\(\left\{x-\dfrac{k}{2},\dots,x+\dfrac{k}{2}\right\}\setminus\{x\}.\)

这启发我们用带一个洞的连续段来表示一般的稳定块。

定义一个 H-segment 由三元组 \((x,y,z)\) 表示，其中满足\(x<y\le z,\)并表示在区间 \([x,z]\) 上除了 \(y\) 这一点为空外，其余点都各放一颗豆子，即占据集合 \(\{x,x+1,\dots,z\}\setminus\{y\}.\)

这类块有两个好处：

  1. 它恰好覆盖了上面“偶数堆有一个洞”的形态；
  2. “没有洞的连续段”也能纳入：把洞放在最右端 \(y=z\)，那么占据集合就是 \([x,z-1]\) 这一整段（右端点空出来）。

对 \((x,y,z)\) 这块：

  • 豆子总数为\(K=(z-x+1)-1=z-x.\)
  • 位置和为\(\displaystyle{S=\sum_{p=x}^{z}p-y.}\)
  • 平方和为\(\displaystyle{Q=\sum_{p=x}^{z}p^2-y^2.}\)

将两个稳定块叠加（把豆子数相加）后，如果它们的占据范围相交或相邻，就会在交界处产生位置上豆子数 \(\ge2\)，需要进一步进行操作消解冲突。

在一维直线上，这种冲突沿着区间传播，但最终连通块仍只会留下至多一个洞：直观上，你可以把“多出来的一颗豆子”看成在连续段中推动洞的位置，洞不会凭空变成两个。于是这整个连通块稳定后仍是一个 H-segment。

因此当两个块需要合并时，只要知道合并后的：

  • 豆子总数 \(K\)（显然相加）；
  • 位置和 \(S\)（由观察 1，不变，因此也相加）；

就能唯一确定新的 \((x,y,z)\)。

对任意给定的 \(x\) 与 \(K\)（注意 \(z=x+K\)），满区间 \([x,x+K]\) 的和是\(\displaystyle{\sum_{p=x}^{x+K}p=\frac{(K+1)(2x+K)}{2}.}\)而真实占据要减去洞 \(y\)，其中洞满足 \(y\in{x+1,x+2,\dots,x+K}\)，所以 \(S\) 的可能范围为：

  • 当洞取最大 \(y=x+K\) 时，\(S\) 最小：\(\displaystyle{S_{\min}=\frac{(K+1)(2x+K)}{2}-(x+K)=\frac{K(2x+K-1)}{2}.}\)
  • 当洞取最小 \(y=x+1\) 时，\(S\) 最大：\(\displaystyle{S_{\max}=\frac{(K+1)(2x+K)}{2}-(x+1)=\frac{K(2x+K+1)}{2}-1.}\)

因此 \(x\) 必须且只需满足\(\dfrac{K(2x+K-1)}{2}\le S<\dfrac{K(2x+K+1)}{2}.\)

这个不等式对整数 \(x\) 有唯一解（区间长度为 \(K\)，随着 \(x\) 增大整体平移），所以可以用整数除法先算一个候选，再做 \(1\) 次左右微调就能落到正确的 \(x\)。

一旦 \(x\) 确定，令\(\displaystyle{F=\sum_{p=x}^{x+K}p=\frac{(K+1)(2x+K)}{2},}\)则洞的位置就是\(y=F-S.\)再令\(z=x+K,\)便得到新的 H-segment \((x,y,z)\)。

因此，题目里只有 \(C=1500\) 个非空碗（其余全空）。与其一颗一颗加豆子，不如“一堆一堆”处理：

  1. 第 \(i\) 个碗在位置 \(p=i-1\)，有 \(b_i\) 颗豆子。
  2. 先把这堆单独稳定成一个 H-segment。
  3. 用一个栈从左到右存放当前已经处理完的、互不接触的 H-segment。
  4. 新段如果与栈顶段“接触或重叠”（右端占据点 \(+1\ge\) 新段左端占据点），就弹出栈顶并合并成一个更大的 H-segment，继续与新的栈顶检查，直到完全分离为止；然后把新段压栈。

最终所有段加起来就构成最终稳定态。于是：

  • 初始平方和\(\displaystyle{Q_{\text{init}}=\sum_{i=1}^{C} b_i(i-1)^2.}\)
  • 终态平方和 \(Q_{\text{final}}\) 为所有 H-segment 的 \(Q\) 之和。
  • 答案步数\(M=\dfrac{Q_{\text{final}}-Q_{\text{init}}}{2}.\)

代码

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
from dataclasses import dataclass
C = 1500

# ----------------------------
# 生成题目给定的 b_i 序列
# ----------------------------

def gen_bs(C: int) -> list[int]:
    t = 123456
    bs = []
    mask = (1 << 11) - 1
    for _ in range(C):
        if (t & 1) == 0:
            t //= 2
        else:
            t = (t // 2) ^ 926252
        bs.append((t & mask) + 1)
    return bs


# ----------------------------
# 等差求和与平方和（全整数）
# ----------------------------

def sum_arith(a: int, m: int) -> int:
    # sum_{i=0..m} (a+i)
    return (m + 1) * (2 * a + m) // 2

def sum_squares_arith(a: int, m: int) -> int:
    # sum_{i=0..m} (a+i)^2
    s1 = m * (m + 1) // 2
    s2 = m * (m + 1) * (2 * m + 1) // 6
    return (m + 1) * a * a + 2 * a * s1 + s2


# ----------------------------
# H-segment（精简版）
# ----------------------------

@dataclass(slots=True)
class HSeg:
    # 占据集合 {x, x+1, ..., x+K} \ {y}，满足 x < y <= x+K
    x: int
    y: int
    K: int
    S: int  # 位置和
    Q: int  # 平方和

def seg_z(seg: HSeg) -> int:
    return seg.x + seg.K

def seg_right_occ(seg: HSeg) -> int:
    z = seg.x + seg.K
    return z if seg.y != z else z - 1

def make_seg_from_x_y_K(x: int, y: int, K: int) -> HSeg:
    z = x + K
    # 满 span [x..z] 的和/平方和，再扣掉洞 y
    full_S = sum_arith(x, K)
    full_Q = sum_squares_arith(x, K)
    return HSeg(x=x, y=y, K=K, S=full_S - y, Q=full_Q - y * y)

def pile_to_seg(p: int, k: int) -> HSeg:
    # 单点 p 上有 k 个豆子，单独稳定成一个 H-segment
    if k & 1:
        # 奇数：连续段长度 k，中心 p。用“洞在最右端”表示连续段
        h = k // 2
        x = p - h
        K = k
        y = x + K  # y=z，洞在最右端
        return make_seg_from_x_y_K(x, y, K)
    else:
        # 偶数：span [p-h .. p+h]，洞在中心 p
        h = k // 2
        x = p - h
        y = p
        K = k
        return make_seg_from_x_y_K(x, y, K)

def solve_x_from_S_K(S: int, K: int) -> int:
    # K(2x+K-1)/2 <= S < K(2x+K+1)/2
    num = 2 * S - K * (K - 1)
    x = num // (2 * K)
    while True:
        lo = K * (2 * x + K - 1) // 2
        hi = K * (2 * x + K + 1) // 2
        if lo <= S < hi:
            return x
        if S < lo:
            x -= 1
        else:
            x += 1

def merge_two(a: HSeg, b: HSeg) -> HSeg:
    K = a.K + b.K
    S = a.S + b.S
    x = solve_x_from_S_K(S, K)
    y = sum_arith(x, K) - S
    return make_seg_from_x_y_K(x, y, K)


# ----------------------------
# 主过程：栈式合并 + 用平方和差求步数
# ----------------------------

def count_moves(bs: list[int]) -> int:
    # 初始平方和 Q_init：第 i 个碗上有 k：贡献 k*i^2
    Q_init = 0
    for i, k in enumerate(bs):
        Q_init += k * (i * i)

    stack: list[HSeg] = []
    for i, k in enumerate(bs):
        seg = pile_to_seg(i, k)

        # 与栈顶接触/重叠：seg.x <= right_occ(top)+1
        while stack and seg.x <= seg_right_occ(stack[-1]) + 1:
            seg = merge_two(stack.pop(), seg)

        stack.append(seg)

    Q_final = 0
    for s in stack:
        Q_final += s.Q

    return (Q_final - Q_init) // 2



bs = gen_bs(C)
ans = count_moves(bs)
print(ans)