問題一覧 > 通常問題

No.2102 [Cherry Alpha *] Conditional Reflection

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 65
作問者 : 👑 Kazun / テスター : butsurizuki sapphire__15
お気に入りにしたユーザー ProblemId : 5276 / 自分の提出
問題文最終更新日: 2022-10-14 11:10:14
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
yukicoder contest 364 (Do you know Cherry Contest?) (順位表) の他の問題:

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 g in 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もしくは右上の雲マークをクリックしてアカウントを作成してください。