Project Euler 275

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

Project Euler 275

题目

Balanced Sculptures

Let us define a balanced sculpture of order n as follows:

  • A polyomino made up of \(n+1\) tiles known as the blocks (\(n\) tiles) and the plinth (remaining tile);
  • the plinth has its centre at position \((x=0, y=0)\);
  • the blocks have \(y\)-coordinates greater than zero (so the plinth is the unique lowest tile);
  • the centre of mass of all the blocks, combined, has \(x\)-coordinate equal to zero.

When counting the sculptures, any arrangements which are simply reflections about the \(y\)-axis, are not counted as distinct. For example, the \(18\) balanced sculptures of order \(6\) are shown below; note that each pair of mirror images (about the \(y\)-axis) is counted as one sculpture:

There are \(964\) balanced sculptures of order \(10\) and \(360505\) of order \(15\). How many balanced sculptures are there of order \(18\)?

解决方案

由于因为每个方格质量相同，所以质心的 \(x\) 坐标等于 blocks 的 \(x\) 坐标平均值为 \(0\)。此外，关于 \(y\) 轴的镜像视为同一个，这启发我们可以镜像地进行操作拼接。

本题基本思路是搜索，但是使用了如下思想进行剪枝：

Redelmeier 思想

朴素做法是：每次在形状边界上加一个格子，靠“形状哈希/判重”去掉重复。但 polyomino 的分支数非常大，判重也很贵。Redelmeier 方法的关键是：通过“候选格子的编号顺序 + 单调选择规则”，从构造过程上保证每个 fixed polyomino 只生成一次，从而避免大规模判重。

具体来说，我们维护两个集合概念：

  • 当前形状（已放入的格子）。
  • frontier（候选边界列表）：所有与当前形状边相邻、且尚未加入形状、也合法的空格子。frontier 的插入顺序就是它的“编号”。

那么递归步骤如下：

  1. 选择一个 frontier 中的格子加入形状；
  2. 把它的四邻域（上下左右）中符合规则且未出现过的格子加入 frontier（会得到更大的编号）；
  3. 下一次递归时，只允许选择“编号不小于本次所选编号”的候选格（也就是从 frontier 的某个起点往后选）。

这条“编号单调”规则就是 Redelmeier 的去重核心：同一个形状可能有很多加入顺序，但只有一种顺序会满足“每一步都从允许的编号区间中挑选”，因此不会重复生成。

镜像去重

如果先生成所有形状再做镜像归并，会多一倍左右的工作；更好的做法是把“镜像不区分”变成搜索约束。

维护一个状态：当前部分形状是否仍关于 \(y\) 轴对称（记为 symmetric）。

  • 若 symmetric 为真：

    • 当考虑加入一个候选格 \((x,y)\) 且 \(x\neq 0\) 时，它的镜像 \((-x,y)\) 也会同时出现在候选集中（可以视作“成对候选”）。

    • 此时分两条分支：

      1. 保持对称：一次性把这对格子都加入（消耗 \(2\) 个 blocks），symmetric 仍为真；
      2. 打破对称：只加入其中一侧（消耗 \(1\) 个 block），然后进入 symmetric 为假的状态。

    • 关键点：只允许在“成对候选”的一个代表侧执行“打破对称”，这样不会生成镜像等价的重复分支。

  • 若 symmetric 为假： 对称已经破坏，不再需要特殊处理（正常枚举即可），最终计数时也不再需要“镜像归并”。

这种策略的本质是：把“镜像等价类”中的一个代表在搜索树里唯一化，从源头避免重复。

平衡条件与剪枝

若一直保持对称：每个 \(x\neq 0\) 的格子都成对出现、互相抵消，且 \(x=0\) 的格子贡献为 \(0\)，因此 blocks 的 \(\sum x\) 必为 \(0\)，无需再算。 只有当 symmetric 被打破后，才需要维护：

当已经不对称时，仍需放置 \(r\) 个 blocks。设当前 blocks 的 \(x\) 取值范围大致落在 \([x_{\min}, x_{\max}]\)。

由于 polyomino 是通过“贴边加格”生长的，每放一个格子，极端情况下 \(x_{\min}\) 最多向左扩 \(1\)、\(x_{\max}\) 最多向右扩 \(1\)。于是剩余 \(r\) 步中：

  • 最“偏左”的 \(x\) 贡献可以粗略下界为：\(r\cdot x_{\min} - \dfrac{r(r+1)}{2}\)
  • 最“偏右”的贡献上界为：\(r\cdot x_{\max} + \dfrac{r(r+1)}{2}\)

如果把下一步要加的格子的 \(x\) 也计入（得到新和 \(S'\)），那么最终可能达到的总和范围必落在：

\[ \left[S' + rx_{\min} - \dfrac{r(r+1)}{2}, S' + r x_{\max} + \dfrac{r(r+1)}{2}\right] \]

代码

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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
#include <bits/stdc++.h>
using namespace std;

/*
  Project Euler 275: Balanced Sculptures (order n)

  目标：统计由 n 个 blocks + 1 个 plinth 组成的 polyomino（连通方格图形）数量，满足：
    1) plinth 固定在 (0,0)，且它是唯一 y=0 的方格（所以 blocks 必须 y>0）
    2) 只看 blocks（不含 plinth），其质心 x=0
       等价于：所有 blocks 的 x 坐标之和为 0
    3) 关于 y 轴的镜像视作同一个（不重复计数）

  主要思想（对应到实现）：
    A) Redelmeier 法枚举 fixed polyomino：用“候选边界列表 frontier + 只从起点往后选”避免同形重复
    B) 镜像去重：搜索过程中维护 symmetry 状态（是否仍保持 y 轴对称）
       - symmetry==true 时：对 x!=0 的添加点，分两条路：
          1) 保持对称：一次性加入 (x,y) 与 (-x,y) 两块（消耗 2 个 block）
          2) 打破对称：只加入一侧（消耗 1 个 block），之后 symmetry=false
       - “打破对称”只从镜像对中的一个代表侧发生，避免左右两侧重复生成镜像等价解
    C) 平衡剪枝：当 symmetry 已被打破后，维护 blocks 的 x 和 balance_sum；
       利用“剩余 r 步能到达的 x 和区间”判断是否仍可能回到 0，不可能则剪枝。
*/

// 题目要解 n=18；这里把坐标范围、数组大小按 N=18 预留。
// 经验上：x 在 [-N, N] 足够（更大也不会在最优搜索中出现），y 在 [0, N] 足够（最多叠 N 层）。
const int N = 18;        // order: number of blocks
const int SHIFT = N;     // 将 x 平移到非负下标
const int W = 2 * N + 1; // x 维度：[-N..N] 共 37
const int H = N + 1;     // y 维度：[0..N] 共 19

// 将 (x,y) 映射到 used 数组下标
int idx(int x, int y)
{
    return (x + SHIFT) + y * W;
}

struct Pos
{
    int x, y;
    Pos(int xx = 0, int yy = 0) : x(xx), y(yy) {}
};

int total_sculptures;

// balance_sum 的定义非常关键：
//   当 symmetry==false 时，我们需要追踪 blocks 的 x 坐标和最终是否为 0。
//   在递归函数 dfs(pos, rem, ...) 中：
//     - balance_sum 存的是“已经放置的 blocks 的 x 和（不包含当前参数 pos 这一块）”
//     - 因此：
//         * 剪枝时用 balance_sum + pos.x 来表示“放下 pos 之后的新和”
//         * 递归展开时会在进入后执行 balance_sum += pos.x（但注意叶子 rem==0 会提前返回）
//         * 叶子处用 balance_sum + pos.x 判断是否为 0
int balance_sum;

// used 的语义：在当前递归分支里，某个格子是否已经“被占用（已在形状里）或已进入候选列表 frontier”。
// 目的：避免同一个位置被重复加入 frontier（即避免 frontier 出现重复点）。
vector<unsigned char> used;

// frontier（候选边界列表）：Redelmeier 法的核心数据结构。
// 它保存“当前形状周围所有可添加的空格子”，并且每个格子在第一次出现时被加入，形成隐式编号顺序。
// 递归时用 from 下标来保证“只能选择编号不小于上一次选择的候选格”，从而让每个 fixed polyomino 只生成一次。
vector<Pos> frontier;

/*
  平衡可达剪枝（只在 symmetry==false 时使用）

  当前准备添加一个 block，其 x 为 x；当前已放置 blocks 的 x 和为 balance_sum（不含这块 x）；
  还剩 r 个 block（在放下这块之后，还要放 r 个）——注意 r 的含义是 dfs 里的 rem。

  设放下这块后新和 new_balance = balance_sum + x。

  我们还需要判断：在剩余 r 个块内，是否存在某种摆放使得最终 x 和能变为 0？

  关键上界/下界推导：
    - 设当前 blocks 的最左 x 为 minx，最右 x 为 maxx（这是已经放置 + 即将放置这块后的边界）
    - 每加 1 块，边界最多向外扩 1（因为只能贴边扩展）
    - 因此未来 r 块最极端情况下：
        最左可能出现 minx, (minx-1), ..., (minx-r) 的贡献，总和 >= r*minx - (1+2+...+r)
        最右可能出现 maxx, (maxx+1), ..., (maxx+r) 的贡献，总和 <= r*maxx + (1+2+...+r)

  若 0 不落在 [min_possible, max_possible] 内，则无论如何都无法平衡，直接剪枝。
*/
bool balanceable_after_adding(int x, int minx, int maxx, int r)
{
    int new_balance = balance_sum + x;

    // 把“即将放置的这块”也纳入边界
    int new_minx = min(minx, x);
    int new_maxx = max(maxx, x);

    int tri = 1LL * r * (r + 1) / 2; // 1+2+...+r

    // 极端向左时未来 r 块的最小总贡献
    int min_possible = new_balance + 1LL * r * new_minx - tri;
    // 极端向右时未来 r 块的最大总贡献
    int max_possible = new_balance + 1LL * r * new_maxx + tri;

    return min_possible <= 0 && max_possible >= 0;
}

/*
  将某个候选空格 (x,y) 加入 frontier（如果尚未加入过）

  约束：
    - blocks 必须满足 y>0；只有 plinth 是 (0,0)
      => 禁止任何 (x!=0, y==0) 的加入

  symmetry==true 时的特殊处理：
    - 若加入了 (x,y) 且 x!=0，则必须同时加入其镜像 (-x,y)，并保证它们在 frontier 中相邻
      这样遍历时就能“一次处理一对镜像点”，并在保持对称分支里跳过镜像点，确保不会重复。
*/
static inline void enqueue_cell(int x, int y, bool symmetry)
{
    // blocks 必须 y>0；y==0 只能是 (0,0) 的 plinth
    if (y == 0 && x != 0)
    {
        return;
    }

    int id = idx(x, y);
    if (used[id])
        return; // 已经在当前分支中入过 frontier（或已占用），无需重复加入

    used[id] = 1;
    frontier.emplace_back(x, y);

    if (symmetry && x != 0)
    {
        // 在对称模式下，镜像点必须同步进入 frontier，且紧跟在原点之后，方便后续成对处理
        int mid = idx(-x, y);
        used[mid] = 1;
        frontier.emplace_back(-x, y);
    }
}

/*
  核心 DFS：在当前分支里，把参数 pos 当作“这一步要放下的方格”，然后继续放剩下的 rem 个 block。

  参数含义：
    - pos：当前要放置的位置（注意：symmetry==true 且 pos.x!=0 时，它代表“放置 (pos) 和它的镜像”这一对）
    - rem：放下 pos（或 pos+镜像对）之后，仍需放置的 blocks 数量
    - from：Redelmeier 去重关键：后续只能从 frontier 的 [from, end) 里选择下一个格子
            这等价于“候选点按入队顺序编号，并强制编号递增选择”
    - symmetry：当前形状是否仍关于 y 轴对称
    - minx, maxx：当前 blocks 的 x 边界，用于平衡剪枝（对称时也维护 maxx 方便后续）
*/
static void dfs(const Pos &pos,
                int rem,
                int from,
                bool symmetry,
                int minx,
                int maxx)
{
    // 叶子：已经没有 block 需要放了
    // 注意：这里还没把 pos.x 加进 balance_sum（因为 balance_sum 的维护发生在后面），
    // 所以 symmetry==false 时必须用 balance_sum + pos.x 来判定最终是否平衡。
    if (rem == 0)
    {
        if (symmetry || balance_sum + pos.x == 0)
        {
            // 仍然对称 => blocks 的 x 和必为 0（非轴成对抵消，轴上 x=0）
            ++total_sculptures;
        }
        return;
    }

    // 平衡可达剪枝：只在 symmetry==false 才有意义（对称时天然平衡），并且只在后期 rem 较小时启用
    if (!symmetry && !balanceable_after_adding(pos.x, minx, maxx, rem))
    {
        return;
    }

    // symmetry==false 时，真正把当前这块 pos 计入 balance_sum
    // （但注意：叶子 rem==0 已提前 return，因此叶子处不会执行这句）
    if (!symmetry)
        balance_sum += pos.x;

    // 记录 frontier 旧大小，回溯时把本层新增的候选点全部弹出并清 used 标记
    size_t old_frontier_size = frontier.size();

    // 把 pos 的四邻域空格加入 frontier（维护候选边界）
    // 这个调用顺序会影响 frontier 内镜像对的相对顺序，
    // 这里的顺序安排是为了让 (x>0) 更倾向先进入，再紧跟 (-x)。
    enqueue_cell(pos.x + 1, pos.y, symmetry);
    enqueue_cell(pos.x - 1, pos.y, symmetry);
    enqueue_cell(pos.x, pos.y + 1, symmetry);
    if (pos.y > 0)
        enqueue_cell(pos.x, pos.y - 1, symmetry);

    // 遍历可选的候选点：只从 from 到 end（Redelmeier 去重：编号递增选择）
    for (int i = from; i < (int)frontier.size();)
    {
        Pos nxt = frontier[i];

        if (symmetry && nxt.x != 0)
        {
            /*
              对称模式下，nxt 与其镜像点必然在 frontier 中相邻出现：
                ... (x,y), (-x,y), ...

              对于这一对镜像候选，我们分两种扩展：
                1) 保持对称：同时放下这对（消耗 2 个 block），symmetry 继续为 true
                2) 打破对称：只放下一侧（消耗 1 个 block），symmetry 变为 false

              为避免镜像重复：
                - “打破对称”只从这对中的一个代表位置发生（这里就是 nxt），
                  并在遍历时跳过镜像点，从而不会再从另一侧产生镜像等价的分支。
            */
            int new_max = max(maxx, abs(nxt.x));

            // i 指向 (x,y)，i+1 应当是 (-x,y) 的镜像点；遍历时直接跳过镜像点
            int next_i = i + 2;

            // 分支 1：保持对称（一次放下两块）
            if (rem >= 2)
            {
                dfs(nxt, rem - 2, next_i, true, -new_max, new_max);
            }

            // 分支 2：打破对称（只放下一侧），从此需要维护 balance_sum
            dfs(nxt, rem - 1, next_i, false, min(minx, nxt.x), max(maxx, nxt.x));

            i = next_i;
        }
        else
        {
            /*
              非对称模式（或 nxt 在对称轴 x=0 上）：
                - 一次只放下一块
                - symmetry 状态保持不变
            */
            int next_i = i + 1;
            dfs(nxt, rem - 1, next_i, symmetry, min(minx, nxt.x), max(maxx, nxt.x));
            i = next_i;
        }
    }

    // 回溯：撤销本层对 balance_sum 的影响
    if (!symmetry)
        balance_sum -= pos.x;

    // 回溯：撤销本层 add_neighbours 引入的新候选点
    // 只需要弹出到 old_frontier_size，并把对应 used 标记清掉即可。
    while (frontier.size() > old_frontier_size)
    {
        Pos p = frontier.back();
        used[idx(p.x, p.y)] = 0;
        frontier.pop_back();
    }
}

/*
  求解给定 order = n_blocks 的答案。
  初始化：
    - plinth 固定在 (0,0)，并标记 used（相当于形状初始已有一个方格）
    - 从 plinth 开始 DFS 生长 blocks
    - 初始 symmetry=true（只有一个点一定对称）
*/
int solve_order(int n_blocks)
{
    total_sculptures = 0;
    balance_sum = 0;

    used.assign(W * H, 0);
    frontier.clear();

    // reserve 是为了减少扩容带来的常数开销（扩容会导致迭代器失效，且更慢）
    frontier.reserve((n_blocks + 1) * 10);

    // plinth at (0,0)
    used[idx(0, 0)] = 1;

    // 从 plinth 出发；rem=n_blocks 表示还需要放 n_blocks 个 blocks
    // minx=maxx=0 初始边界
    // from=0 表示从 frontier[0] 开始遍历候选（此时 frontier 还为空，进入 dfs 后会先扩张邻居）
    dfs(Pos(0, 0), n_blocks, 0, true, 0, 0);

    return total_sculptures;
}

int main()
{
    int num = solve_order(N);
    cout << num << endl;
}