問題一覧 > 通常問題

No.2102 [Cherry Alpha *] Conditional Reflection

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 67
作問者 : 👑 Kazun / テスター : butsurizuki sapphire__15
ProblemId : 5276 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-14 11:10:14
コンテストの他の問題:

問題文

チェリーちゃんは $N$ 個の文字列 $S_1, \dots, S_N$ をこの順に見ていく.

ここで, チェリーちゃんは過去に見たことがある文字列をみると反応するが, 過去には見たことなくても似ているような文字列であったとしても反応してしまう.

厳密には, チェリーちゃんは $i$ 番目に見た文字列 $S_i$ について, 以下を満たすような整数 $j$ が存在すると反応してしまう.

  • $1 \leq j \lt i$
  • $S_j$ に対して隣り合う2つの文字を入れ替える操作を高々1回行うことにより $S_i$ に一致させることができる.

各 $i=1,2, \dots, N$ に対して, チェリーちゃんは $i$ 番目の文字列 $S_i$ を見た時に反応するか?

制約

  • $1 \leq N \leq 2 \times 10^5$
  • $N$ は整数.
  • $S_i$ は英小文字からなる空でない文字列
  • $\left|S_1 \right|+\dots+\left|S_N \right| \leq 10^6$. ただし, 文字列 $T$ に対して, $|T|$ で $T$ の長さを表すとする.

入力

$N$
$S_1$
$\vdots$
$S_N$

出力

出力は $N$ 行からなる. 第 $i~(1 \leq i \leq N)$ 行目には $S_i$ を見た時に反応してしまうならば Yes, 反応しないのならば No と出力せよ.

サンプル

サンプル1
入力
6
cherry
zelkova
zlekova
cherry
chreyr
ginkgo
出力例
No
No
Yes
Yes
No
No

  • $i=1$: $1 \leq j \lt 1$ を満たす整数 $j$ は存在しない.
  • $i=2$: $1 \leq j \lt 2$ を満たす整数 $j$ は $j=1$ だけだが, $S_1$ の隣り合う文字の入れ替えを高々1回の操作では $S_2$ に一致できない.
  • $i=3$: $j=2$ とすると, $1 \leq j \lt 3$ を満たし, $S_2$ の $2$ 文字目と $3$ 文字目を入れ替えると $S_3$ に一致する.
  • $i=4$: $j=1$ とすると, $1 \leq j \lt 4$ を満たし, しかも $S_1=S_4$ である. 高々 $1$ 回の操作には操作しないことも許容することに注意.
  • $i=5$: $S_1 (=S_4)$ から $S_5$ へ一致させるためには少なくとも $2$ 回の操作が必要である.
  • $i=6$: $S_1, S_2, S_3, S_4, S_5$ の中にそもそも g を含む文字列が存在しない. ちなみに, ginkgo はイチョウを表す英単語である.

サンプル2
入力
10
fault
ban
bullet
rain
friction
aflut
bna
bluelt
rani
frcition
出力例
No
No
No
No
No
No
Yes
No
Yes
Yes

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。