Codeforces 🎨 CF2183G. Snake Instructions

題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF2183G Snake Instructions

rating: 3238

Problem Statement

題目簡述

這是一道互動題。

數線上有 $n$ 條蛇，第 $i$ 條蛇位於 $a_i$，速度 $s_i \in \{0, 1, 2\}$ 未知。

你需要通過最多 3 次詢問來確定每條蛇的速度。

• 每次詢問給出一個由 L 和 R 組成的字串，蛇會根據字串代表的秒數移動。若指令為 L 則所有蛇向左移動 $s_i$ 單位，R 則向右移動 $s_i$ 單位。
• 若兩蛇在任意時刻位置重疊，速度較快者被移除。

詢問結束後，系統會回傳剩餘蛇的數量及位置（蛇會復活並回到初始位置進行下一次詢問）。

若無法確定某些蛇的速度，輸出 ! -1；否則輸出所有蛇的速度。

Constraints

約束條件

• $2 \le n \le 10^5$
• $1 \le a_1 < a_2 < \dots < a_n \le 4n$
• 所有 $a_i$ 皆為整數
• 查詢字串長度 $1 \le m \le 4n$

---

思路：利用 L, LR, R 三次詢問

題目的關鍵在於如何利用有限的 3 次詢問來區分出 $\{0, 1, 2\}$ 三種速度。
由於蛇的移動會導致碰撞消失，這既是資訊流失，也是資訊來源。

核心策略

只需使用三次詢問：L、LR、R，就可以確定所有蛇的速度。

令查詢 L、LR、R 得到的座標序列分別為 $v_l$、$v_{lr}$、$v_r$。

Step 1：查詢 L 與 LR 的關聯

• 查詢 L：所有蛇向左移動 1 秒。存活下來的蛇位置變為 $a_i - s_i$。
• 查詢 LR：先向左 1 秒，再向右 1 秒。

重要性質

由於 LR 等於「先往左 1 秒，再往右 1 秒」，所以經歷 LR 操作後存活下來的蛇：

• 其位置一定會回到自己的初始位置 $a_i$
• LR 的存活集合與 L 的存活集合完全相同

證明：L 後存活的任兩條蛇，在接下來 1 秒的 R 過程中不會相撞。

取 L 後仍存活的兩蛇 $i<j$。R 開始時位置分別為

$$x_i=a_i-s_i,\quad x_j=a_j-s_j.$$

若 $s_i\le s_j$，則右移時 $i$ 不可能追上 $j$。
若 $s_i>s_j$，則相對速度為 $s_i-s_j\in\{1,2\}$，兩蛇距離為

$$x_j-x_i=(a_j-a_i)+(s_i-s_j).$$

追擊所需時間 $t$ 為：

$$\begin{aligned} t &= \frac{x_j-x_i}{s_i-s_j} \\ &= \frac{(a_j-a_i)+(s_i-s_j)}{s_i-s_j} \\ &= \frac{a_j-a_i}{s_i-s_j}+1 \end{aligned}$$

其中 $a_j-a_i\ge 1$ 、 $1 \le s_i-s_j\le 2$，兩者皆為正整數，因此：

$$t=\frac{a_j-a_i}{s_i-s_j}+1>1$$

但 R 只持續 1 秒，故不可能在 R 期間發生碰撞。

因此，我們可以將 LR 回傳的座標與 L 回傳的座標一一對應。

設 $v_{lr}[j]$ 對應原始蛇索引 $i$（即 $a_i = v_{lr}[j]$），則該蛇的速度為：

$$s_i = a_i - v_l[j] \quad \text{for} \quad a_i = v_{lr}[j]$$

這樣就確定了所有在 L 操作下存活蛇的速度。

Step 2：推導在 L 中死亡的蛇

對於在 Step 1 後仍未確定速度的蛇 $i$，表示它們在 L 的 1 秒內追上了左側某條更慢的蛇而死亡（不一定是原本編號的 $i-1$，因為前面的蛇可能先被淘汰）。

由於最大相對速度是 2，所以它能在 1 秒內追上的距離最多是 2，這導致只有局部間距 $d \in \{1, 2\}$ 的情況需要討論（此處 $d = a_i - a_{i-1}$）。

情況 A：$d = 2$

條件：需滿足 $\Delta s \ge 2$

唯一可能是 $s_i = 2, s_{i-1} = 0$，故可直接確定 $s_i = 2$。

情況 B：$d = 1$

條件：需滿足 $\Delta s \ge 1$

• 若前方蛇 $s_{i-1} \neq 0$（包含「已知 $>0$」或「未知但已死」——後者必有 $s_{i-1} \ge 1$，因為速度 0 的蛇在 L 中必定存活）：
  • 因 $s_{i-1} \ge 1$，為滿足 $s_i > s_{i-1}$，唯一可能是 $s_{i-1}=1, s_i=2$，此時可確定 $s_i = 2$。
• 若前方蛇 $s_{i-1} = 0$：
  • 可能是 $(0, 1)$ 或 $(0, 2)$，保留至 Step 3 處理。

自此剩下 $a_i - a_{i-1} = 1 \land s_{i-1} = 0$ 的蛇未處理，且他們的速度只能是 1 或 2。

Step 3：查詢 R 與最終推導

• 查詢 R：所有蛇向右移動 1 秒，回傳所有存活者的最終位置 $v_r$（遞增）。
• 對於仍未確定的蛇 $i$，用二分搜尋在 $v_r$ 中找到第一個 $\ge a_i$ 的存活位置 $p$，並設：

  $$s_i = p - a_i$$

為何這樣反推是合理的

剩下未確定的，結構上只會是 $a_i - a_{i-1} = 1 \land s_{i-1} = 0$，而 $s_i \in \{1, 2\}$ 這種情況。
在 R（只跑 1 秒）裡，這條蛇如果是：

• 速度 1：它最多到 $a_i+1$。
• 速度 2：它最多到 $a_i+2$。

分類討論，考慮以下幾種情況：

• 若該蛇在 R 中存活，其終點即為 $a_i + s_i$
  • 由於 $s_{i-1} = 0$，所以 $a_{i-1} + s_{i-1} < a_i$，因此二分找到的位置 $p = a_i + s_i$。
• 若死亡且 $s_i = 1$，此時若發生碰撞，只可能是 $1$ 種情況
  1. $a_{i+1} - a_{i} = 1$ 且 $s_{i+1} = 0$
     • 此時碰撞後找到的位置 $p = a_{i+1}$，但因為 $a_{i+1} - a_i = s_i$，所以仍滿足 $p = a_i + s_i$。
• 若死亡且 $s_i = 2$，此時若發生碰撞，可能是以下 $3$ 種情況：
  1. $a_{i+1} - a_{i} = 2$ 且 $s_{i+1} = 0$
     • 此時碰撞後找到的位置 $p = a_{i+1}$，但因為 $a_{i+1} - a_i = s_i$，所以仍滿足 $p = a_i + s_i$。
  2. $a_{i+1} - a_{i} = 1$ 且 $s_{i+1} = 0$
     • 此時碰撞後找到的位置 $p = a_{i+1}$，然而此時的 $p = a_{i+1} = a_i + 1$，會 錯誤 推導出 $s_i = 1$。
  3. $a_{i+1} - a_{i} = 1$ 且 $s_{i+1} = 1$
     • 此時碰撞後找到的位置 $p = a_{i+1} + s_{i+1} = (a_i + 1) + 1 = a_i + 2 = a_i + s_i$。

根據以上幾種情況，可以在除了 $(s_i = 2) \land (a_{i+1} - a_{i} = 1) \land (s_{i+1} = 0)$ 的情況下，正確推導出 $s_i$。

Step 4：無解情況 (-1)

唯一例外

基於上述討論，例外發生在 $(a_i - a_{i-1} = 1) \land (s_{i-1} = 0) \land (s_i = 2) \land (a_{i+1} - a_{i} = 1) \land (s_{i+1} = 0)$ 的情況下，此時會錯誤地推導出 $s_i = 1$。

換句話說，對於 $(a_i - a_{i-1} = 1) \land (s_{i-1} = 0) \land (a_{i+1} - a_{i} = 1) \land (s_{i+1} = 0)$ 的情況，如果得到了 $s_i = 1$，實際上有可能是 $s_i = 1$ 或 $s_i = 2$ 兩種情況，我們無法區分。

因此我們需要檢查是否有三條蛇的位置分別是 $(x, x+1, x+2)$，且計算結果為 $(0, 1, 0)$——此時實際速度可能是 $(0, 1, 0)$ 或 $(0, 2, 0)$，無法區分。

複雜度分析

• 時間複雜度：$\mathcal{O}(n \log n)$，主要來自對回傳結果的二分搜尋。
• 空間複雜度：$\mathcal{O}(n)$，用於儲存蛇的位置與答案。

---

Code

from bisect import bisect_left

def query(s: str):
    print(f"? {s}", flush=True)
    k, *arr = list(map(int, input().split()))
    assert k == len(arr)
    return arr

def answer(*args):
    print("!", *args, flush=True)

def solve():
    n = int(input())
    A = list(map(int, input().split()))
    assert len(A) == n

    vl = query("L")
    vlr = query("LR")
    vr = query("R")
    assert len(vl) == len(vlr)

    k = len(vlr)
    ans = [-1] * n

    j = 0
    for i, x in enumerate(A):
        if j < k and vlr[j] == x:
            ans[i] = x - vl[j]
            j += 1

    for i in range(1, n):
        if ans[i] == -1:
            d = A[i] - A[i - 1]
            if d == 2 or (d == 1 and ans[i - 1] != 0):
                ans[i] = 2

    for i, x in enumerate(A):
        if ans[i] == -1:
            j = bisect_left(vr, x)
            ans[i] = vr[j] - x

    for i in range(n - 2):
        if A[i + 1] - A[i] == A[i + 2] - A[i + 1] == 1:
            if ans[i] == 0 and ans[i + 1] != 0 and ans[i + 2] == 0:
                answer(-1)
                return
    answer(*ans)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

---

寫在最後

PROMPT

masterpiece, best quality, high quality, good quality, 32K UHD, colorful, official art, illustration, in the style of fashion photography, dynamic, dynamic force picture, (Visual impact:1.2), impactful picture, extreme aesthetic, A shot with tension, sharp focus, The Ninth Art, depth of field, cinematic lighting, light particles, lens flare, movie perspective, (Tyndall Effect:1.4), light particles, light, shadow, scenery, temperate atmosphere, (artist:pigeon666:0.83), (Yomu:0.4), (remsrar:0.45), (quasarcake:0.3),

1girl, solo, Nijika Ijichi (ijichi nijika, bocchi the rock), brown eyes, blonde hair, long hair, very long hair, bangs, side ponytail, school uniform, white shirt, pleated skirt, long sleeves, bow, ahoge, sidelocks, outdoors, collared shirt, bowtie, black skirt, bag, red bow, red bowtie,

holding umbrella, transparent umbrella, rain, raining, night, wet street, puddle, reflection, glowing vending machine, backlighting, neon lights, urban scenery, wide shot, landscape, horizontal, looking at viewer, blush