CF1910G Pool Records记录

题目链接：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() }
}