abc219F Cleaning Robot

· · 题解

本文译自 atcoder official editorial，由于改文特别详细的讲解了做法，固本文只对一些地方做稍微修改，以便于理解。

我们用 (0, 0) \rightarrow (x_1, y_1) \rightarrow (x_2, y_2) \rightarrow \cdots \rightarrow (x_{|S|}, y_{|S|}) 来表示机器人的位置变换。令 a=x_{|S|},b=y_{|S|}。

观察到，对于机器人每轮走的第 i 步，它们都应该在同一条直线上，且该直线斜率为 \frac{a}{b}。

形式化地，我们让 V_i 为第 i 轮访问的方格的集合。比如，V_1 是一个由 (0, 0), (x_1, y_1), (x_2, y_2), \cdots, (x_{|S|}, y_{|S|}) 组成的集合，没有重复。我们对其中的元素任意编号。

V_1 = \lbrace (X_1, Y_1), (X_2, Y_2), \ldots, (X_N, Y_N) \rbrace

这里，N 是 V_1 的元素个数。

那么，将 V_1 中的每个元素移位 (a, b) 即可得到集合 V_2，即机器人在第二次执行过程中访问的方格集合：

V_2 = \lbrace (X_1 + a, Y_1 + b), (X_2 + a, Y_2 + b), \ldots, (X_N + a, Y_N + b) \rbrace

则我们可以推广到 V_k。

V_k = \lbrace (X_1 + (k-1)a, Y_1 + (k-1)b), (X_2 + (k-1)a, Y_2 + (k-1)b), \ldots, (X_N + (k-1)a, Y_N+ (k-1)b) \rbrace

则过程如下，对于 i = 1, 2, \ldots, N 来说，(X_i, Y_i) \in V_1 对应的是：

这里，对于 i = 1, 2, \ldots, N，让：

如果不存在这样的整数 j，则 d_i := \infty。

然后，像刚刚一样，关注 (X_i, Y_i) \in V_1：

然而，对于 (d_i+1) 次执行和之后的执行：

等等。

因此，在对于字符串 S 执行 K 次的时候，(X_i, Y_i) 将一个未访问过的方格变为访问过的方格 \min(d_i, K) 次。

因此，本题答案为：

\displaystyle\sum_{i = 1}^N \min(d_i, K)

所以，这个问题转化为如何找到数组 d_i，现在我们来解决这个问题。

如果 a = b = 0，我们可以看到 d_1 = d_2 = \cdots = d_N = 1。另外，如果 a = 0, b \neq 0，我们可以交换 X 坐标和 Y 坐标来假设 a \neq 0，因此我们在下文中假设 a \neq 0。

首先，对于每个 i = 1, 2, \ldots, N 我们计算：

q_i = \left\lfloor \displaystyle\frac{X_i}{a} \right\rfloor s_i = X_i - q_i a t_i = Y_i - q_i b

并根据 (s_i, t_i) 将 V_i 中的元素分组。(我们定义当且仅当 (s_i, t_i) = (s_j, t_j) 时，(X_i, Y_i) 和 (X_j, Y_j) 属于同一个组）。

对于任意 1 \leq i, j \leq N 、

(s_i, t_i) = (s_j, t_j) \Leftrightarrow (X_j, Y_j) = (X_i + (q_j-q_i)a, Y_i + (q_j-q_i)b)

因此，通过按 q_i 对每组元素进行排序，我们可以在总共花费 \mathrm{O}(|S|\log|S|) 的时间内，为每个 i = 1, 2, \ldots, N 找出 d_i 的值。

因此，我们总共可以用 \mathrm{O}(|S|\log|S|) 的时间来解决这个问题。

code