+ , -- чи ?#12270

+ , -- чи ? (Розбір)

Автор проблеми:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редаговано:	Хасан Салех (MathModel)

Рішення

Спочатку ми перетворюємо масив на рядок $t$ довжини $n - 1$ n-1 наступним чином:

t_{i} = ⎩ ⎨ ⎧ + - ? якщо a_{i} < a_{i + 1}, якщо a_{i} > a_{i + 1}, якщо a_{i} = a_{i + 1} .

t_i = \begin{cases} \texttt{+} & \text{якщо } a_i < a_{i+1},\\ \texttt{-} & \text{якщо } a_i > a_{i+1},\\ \texttt{?} & \text{якщо } a_i = a_{i+1}. \end{cases}

Тепер проблема полягає в тому, чи з'являється $s$ як підрядок $t$ за правилом відповідності

t_{i + j} = ? або s_{j} = ? або t_{i + j} = s_{j} .

t_{i+j} = \texttt{?} \;\;\text{або}\;\; s_j = \texttt{?} \;\;\text{або}\;\; t_{i+j} = s_j.

Оскільки обмеження невеликі, ми можемо просто спробувати кожну початкову позицію. Для кожного $i$ з $0 \leq i \leq (n - 1) - k$ 0 \le i \le (n-1)-k ми перевіряємо всі $j$ від $0$ до $k - 1$ k-1. Якщо для деякого $j$ вище зазначена умова не виконується, то це вікно є поганим. Якщо ми знаходимо вікно, для якого це виконується для всіх $j$ , ми відповідаємо YES. Якщо жодне з вікон не підходить, ми відповідаємо NO.

Формально, ми відповідаємо YES тоді і тільки тоді, коли

\exists i \forall j \in [0, k - 1] : (t_{i + j} = ? \lor s_{j} = ? \lor t_{i + j} = s_{j}) .

\exists i \;\; \forall j \in [0,k-1]: \bigl(t_{i+j} = \texttt{?} \lor s_j = \texttt{?} \lor t_{i+j} = s_j \bigr).

Складність на тест становить $O (nk)$ : побудова $t$ займає $O (n)$ , і ми перевіряємо максимум $n$ вікон, кожне за $O (k)$ . Це відповідає заданій межі на $\sum n \cdot k$ \sum n\cdot k. Прикладні тести безпосередньо випливають з цього правила: коли рядок різниць масиву може бути прочитаний як шаблон після інтерпретації деяких '?' як '+' або '-', відповідь буде YES; в іншому випадку відповідь буде NO.

Складність $O (nk)$ .

def solve():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    s=input().strip()
    t=[]
    for i in range(n-1):
        if a[i]<a[i+1]: t.append('+')
        elif a[i]>a[i+1]: t.append('-')
        else: t.append('?')
    ok=False
    for i in range(n-1-k+1):
        good=True
        for j in range(k):
            x=t[i+j]; y=s[j]
            if x=='?' or y=='?': continue
            if x!=y:
                good=False
                break
        if good:
            ok=True
            break
    print("YES" if ok else "NO")

for _ in range(int(input())):
    solve()

Python