题目链接：https://codeforces.com/contest/1910/problem/G
题意简述
有两个运动员以未知的固定速度 \(v_1 \ne v_2\) 在一个长为 \(50\) 米的游泳池中游泳，一旦到边缘就立即掉头。现在有他们前 \(n\) 次相遇时间 \(t_i\)（递增，均为整数）的记录，问这个记录是否合法。\(n \le 2 \times 10^5\)。
题解
这题和之前一题 F 题有相当相似的背景，可以先去看看我对那一题的记录。
现在回过头来看，这题其实是个比较简单的贪心，但可能与放的位置（前面的题还是比较耗时间的）、参赛分布（因为是 Kotlin Heroes 场）有关，被评到了 *2700 的高分。由于我被 E、F 卡了太久，赛时也就根本没有看这一题。
由中学物理知识可知，他们相遇的时间符合表达式 $\dfrac{2kl} {v_1-v_2} $ 或 \(\dfrac {2kl} {v_1 + v_2}\)（\(k \in {\mathbb N}^+\)）。我们记 \(u = \dfrac{2l} {v_1-v_2}, v = \dfrac {2l} {v_1 + v_2}\)，则任意一对 \(u \ne v\) 和 \(v_1 \ne v_2\) 一一对应。问题转化为如下形式：
- 是否存在 \(u < v \in {\mathbb N^+}\)，使 \(t\) 是 \(u\) 或 \(v\) 的倍数集合中的前 \(n\) 个数？
若存在这样的 \((u, v)\)，容易得到如下结论：
-
\(u = t_1\)；
-
若 \(v\) 是 \(u\) 的倍数，\(t_i = i \cdot u\)；否则，\(v\) 就是 \(t_i\) 中第一个不为 \(u\) 的倍数的数。
也就是说，在排除 \(\forall i, u | t_i\) 的特殊情况后，我们已经唯一确定了 \(u, v\) 的值。那么，我们就知道数组 \(t\) 中理应包含哪些值（\(i \cdot u, j \cdot v \le t_n\)），一遍检查即可确定答案。
实际上，通过维护当前期待的两个倍数，可以在一遍遍历中完成上面的所有操作。时间复杂度 \(O(n)\)。
代码
fun readInt() = readln().toInt()
fun readLongs() = readln().split(' ').map { it.toLong() }.toLongArray()
fun solve() {
val n = readInt()
val a = readLongs()
var (x, y) = a[0] to 0L
var (i, j) = 1L to 1L
var ans = true
for (t in a) {
var vis = false
if (t == i * x) {
i++
vis = true
}
if (t == j * y) {
j++
vis = true
}
if (!vis) {
if (y != 0L || t % x == 0L) ans = false
y = t
j = 2
}
}
if (y != 0L) {
val mx = a.last()
val (expI, expJ) = (mx / x to mx / y)
ans = ans and (i == expI + 1) and (j == expJ + 1)
}
println(if (ans) "VALID" else "INVALID")
}
fun main() {
val tc = readInt()
repeat(tc) { solve() }
}