問題一覧 > 通常問題

No.2000 Distanced Characters

レベル : / AI推定難易度 : 775 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 108
作問者 : 👑 to-omer / テスター : 👑 qand ygussany
お気に入りにしたユーザー ProblemId : 8204 / 自分の提出
問題文最終更新日: 2022-07-05 22:13:27
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 351 (順位表) の他の問題:

Problem Statement

You are given a string $S$ consisting of lowercase English letters.
For each $2$-tuple $(\alpha,\beta)$ of lowercase English letters, determine whether the following condition is satisfied.

  • For any $1\le i<j\le N$ such that $S_i=\alpha$, $S_j=\beta$, it holds that $i+D_{\alpha,\beta}\le j$.

Constraints

  • $S$ is a string consisting of lowercase English letters
  • $1\le |S|\le 2\times 10^5$
  • $D_{\alpha,\beta}$ is an integer and $0\le D_{\alpha,\beta}\le 2\times 10^5\quad$ ( $\alpha,\beta$ are any lowercase English letters)

Input

$S$
$D_{\mathtt{a},\mathtt{a}}$ $D_{\mathtt{a},\mathtt{b}}$ $\dots$ $D_{\mathtt{a},\mathtt{z}}$
$D_{\mathtt{b},\mathtt{a}}$ $D_{\mathtt{b},\mathtt{b}}$ $\dots$ $D_{\mathtt{b},\mathtt{z}}$
$\vdots$
$D_{\mathtt{z},\mathtt{a}}$ $D_{\mathtt{z},\mathtt{b}}$ $\dots$ $D_{\mathtt{z},\mathtt{z}}$

Note: $D$ is arranged in alphabetical order for both indices.

Output

Let $X_{\alpha,\beta}$ be Y if $(\alpha,\beta)$ satisfies the condition, and N otherwise.

Print $X$ in 26 lines as follows, with values on each line separated by spaces.

$X_{\mathtt{a},\mathtt{a}}$ $X_{\mathtt{a},\mathtt{b}}$ $\dots$ $X_{\mathtt{a},\mathtt{z}}$
$X_{\mathtt{b},\mathtt{a}}$ $X_{\mathtt{b},\mathtt{b}}$ $\dots$ $X_{\mathtt{b},\mathtt{z}}$
$\vdots$
$X_{\mathtt{z},\mathtt{a}}$ $X_{\mathtt{z},\mathtt{b}}$ $\dots$ $X_{\mathtt{z},\mathtt{z}}$

Note: $X$ is arranged in alphabetical order for both indices.

Sample

Sample 1
Input
abab
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Output
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
N N Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
  • $(\mathtt{a},\mathtt{a})$ : $(i,j)=(1,3)$ satisfies $i+D_{\mathtt{a},\mathtt{a}}\le j$, so $X_{\mathtt{a},\mathtt{a}}=$ Y.
  • $(\mathtt{a},\mathtt{b})$ : $(i,j)=(1,2),(1,4),(3,4)$ all satisfy $i+D_{\mathtt{a},\mathtt{b}}\le j$, so $X_{\mathtt{a},\mathtt{b}}=$ Y.
  • $(\mathtt{b},\mathtt{a})$ : For $(i,j)=(2,3)$, we have $i+D_{\mathtt{b},\mathtt{a}}>j$, so $X_{\mathtt{b},\mathtt{a}}=$ N.
  • $(\mathtt{b},\mathtt{b})$ : For $(i,j)=(2,4)$, we have $i+D_{\mathtt{b},\mathtt{b}}>j$, so $X_{\mathtt{b},\mathtt{b}}=$ N.
  • Others: There is no $(i,j)$ such that $(S_i,S_j)=(\alpha,\beta)$, so the condition is always satisfied and $X_{\alpha,\beta}=$ Y.
Sample 2
Input
wueutgofgevlqopfponghekpoffsmovgronggelhijirpppfhdqftvtewtunxeupogfkikqqhneiikkvvwsfrffegjhkkeuuumggiirdxpffffesxrfuwffdttxqfmsggggerhffmgcqqvvsfffd
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3
8 3 2 7 9 5 0 2 8 8 4 1 9 7 1 6 9 3 9 9 3 7 5 1 0 5
8 2 0 9 7 4 9 4 4 5 9 2 3 0 7 8 1 6 4 0 6 2 8 6 2 0
8 9 9 8 6 2 8 0 3 4 8 2 5 3 4 2 1 1 7 0 6 7 9 8 2 1
4 8 0 8 6 5 1 3 2 8 2 3 0 6 6 4 7 0 9 3 8 4 4 6 0 9
5 5 0 5 8 2 2 3 1 7 2 5 3 5 9 4 0 8 1 2 8 4 8 1 1 1
7 4 5 0 2 8 4 1 0 2 7 0 1 9 3 8 5 2 1 1 0 5 5 5 9 6
4 4 6 2 2 9 4 8 9 5 4 9 3 0 3 8 1 9 6 4 4 2 8 8 1 0
9 7 5 6 6 5 9 3 3 4 4 6 1 2 8 4 7 5 6 4 8 2 3 3 7 8
6 7 8 3 1 6 5 2 7 1 2 0 1 9 0 9 1 4 5 6 4 8 5 6 6 9
2 3 4 6 0 3 4 8 6 1 0 4 5 4 3 2 6 6 4 8 2 1 3 3 9 3
6 0 7 2 6 0 2 4 9 1 4 1 2 7 3 7 2 4 5 8 7 0 0 6 6 0
6 3 1 5 5 8 8 1 7 4 8 8 1 5 2 0 9 2 0 9 6 2 8 2 9 2
5 4 0 9 1 7 1 5 3 6 4 3 6 7 8 9 2 5 9 0 3 6 0 0 1 1
3 3 0 5 3 0 5 4 8 8 2 0 4 6 6 5 2 1 3 8 4 1 4 6 9 5
1 9 4 1 5 1 1 6 0 9 4 3 3 0 5 7 2 7 0 3 6 5 7 5 9 5
9 1 9 5 3 0 9 2 1 8 6 1 1 7 3 8 1 9 3 2 6 1 1 7 9 3
1 0 5 1 1 8 5 4 8 0 7 4 4 6 2 3 7 9 9 6 2 7 4 9 5 6
7 3 5 1 8 8 5 7 5 2 7 2 4 8 9 1 2 2 7 9 3 8 1 8 3 0
1 1 9 4 9 1 2 9 8 3 3 6 7 3 3 6 2 4 4 0 6 5 6 6 4 3
0 8 6 0 2 1 3 9 4 9 4 6 3 9 5 2 2 4 7 3 7 1 9 0 7 0
2 1 7 9 8 6 0 9 4 3 7 0 2 7 7 0 5 3 9 2 1 7 1 7 6 2
9 3 1 7 6 7 5 2 3 8 4 6 7 4 8 1 8 4 6 7 6 6 9 4 0 5
1 3 2 0 0 0 5 6 8 1 2 7 1 4 5 2 6 3 5 6 0 8 2 7 7 8
5 7 7 1 3 4 2 7 5 7 7 8 9 6 0 9 1 7 3 6 3 7 1 7 8 7
2 1 4 6 8 4 4 0 9 0 1 2 2 4 9 5 3 4 3 0 1 4 6 5 4 9
Output
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y N N N Y Y
Y Y Y Y Y N Y N N N N N Y N N N N Y N N N N N N Y Y
Y Y Y N N N N N Y N N N N N N N Y N Y N N N N Y Y Y
Y Y N Y N N N Y Y N N Y Y N N N N N Y Y Y N Y Y Y Y
Y Y N N N N Y Y N N N Y Y Y Y N Y N Y Y Y Y Y Y Y Y
Y Y Y N Y Y Y Y N N N Y Y Y Y N N N Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y N N Y Y Y Y Y Y N Y N Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y N N Y Y Y Y Y N N N Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y N N Y Y Y Y Y N N N Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y N Y N Y Y Y Y Y N Y N Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y N N Y Y Y Y Y N N Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y N N N Y Y Y Y N N N Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y N Y Y Y Y Y Y N N Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y N N Y Y Y Y Y N N N Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y N N N Y Y Y Y Y N N N Y Y Y Y Y Y N N Y Y
Y Y Y Y N N N Y Y Y Y Y N N N Y Y Y Y Y Y N Y N Y Y
Y Y Y Y N Y N Y Y Y Y Y N N N Y Y Y Y Y N N N N Y Y
Y Y Y Y N Y N Y Y Y Y Y N N N N Y Y Y N N Y N Y Y Y
Y Y Y N N N Y Y Y Y Y Y Y N N Y N N N N Y N Y Y Y Y
Y Y Y N N N Y Y Y Y Y Y Y N N Y N N N N N Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y N N N N N Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y

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