No.2102 [Cherry Alpha *] Conditional Reflection
レベル :
/ AI推定難易度 : 1600
/ 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 65
作問者 : 👑
Kazun
/ テスター :
butsurizuki
sapphire__15
タグ : / 解いたユーザー数 65
作問者 : 👑
Kazun
/ テスター :
butsurizuki
sapphire__15
問題文最終更新日: 2022-10-14 11:10:14
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
Problem Statement
Cherry looks at $N$ strings $S_1, \dots, S_N$ in this order.
Cherry reacts when she sees a string she has seen before, but she also reacts to a string she has never seen if it is similar to one she has seen.
Strictly speaking, for the $i$-th string $S_i$ she sees, Cherry reacts if there exists an integer $j$ satisfying the following.
- $1 \leq j \lt i$
- $S_j$ can be made equal to $S_i$ by performing the operation of swapping two adjacent characters at most once.
For each $i=1,2, \dots, N$, does Cherry react when she sees the $i$-th string $S_i$?
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $N$ is an integer.
- $S_i$ is a non-empty string consisting of lowercase English letters.
- $\left|S_1 \right|+\dots+\left|S_N \right| \leq 10^6$. Here, for a string $T$, $|T|$ denotes the length of $T$.
Input
$N$ $S_1$ $\vdots$ $S_N$
Output
The output consists of $N$ lines. On the $i~(1 \leq i \leq N)$-th line, print Yes if Cherry reacts when she sees $S_i$, and No if she does not.
Sample
Sample 1
Input
6 cherry zelkova zlekova cherry chreyr ginkgo
Sample Output
No No Yes Yes No No
- $i=1$: There is no integer $j$ satisfying $1 \leq j \lt 1$.
- $i=2$: The only integer $j$ satisfying $1 \leq j \lt 2$ is $j=1$, but $S_1$ cannot be made equal to $S_2$ by swapping adjacent characters at most once.
- $i=3$: Taking $j=2$ satisfies $1 \leq j \lt 3$, and swapping the $2$-nd and $3$-rd characters of $S_2$ makes it equal to $S_3$.
- $i=4$: Taking $j=1$ satisfies $1 \leq j \lt 4$, and moreover $S_1=S_4$. Note that "at most $1$ operation" includes performing no operation.
- $i=5$: At least $2$ operations are required to make $S_1 (=S_4)$ equal to $S_5$.
- $i=6$: None of $S_1, S_2, S_3, S_4, S_5$ contains
gin the first place. By the way, ginkgo is the English word for the イチョウ tree.
Sample 2
Input
10 fault ban bullet rain friction aflut bna bluelt rani frcition
Sample Output
No No No No No No Yes No Yes Yes
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。