問題一覧 > 通常問題

No.2000 Distanced Characters

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 76
作問者 : to-omerto-omer / テスター : 👑 ygussanyygussany sounansyasounansya
2 ProblemId : 8204 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-05 22:13:27

問題文

英小文字からなる文字列 $S$ が与えられます。
英小文字の $2$ つ組 $(\alpha,\beta)$ それぞれについて、次の条件を満たしているかどうか判定してください。

  • $S_i=\alpha$, $S_j=\beta$ を満たす任意の $1\le i<j\le N$ について、 $i+D_{\alpha,\beta}\le j$

制約

  • $S$ は英小文字からなる文字列
  • $1\le |S|\le 2\times 10^5$
  • $D_{\alpha,\beta}$ は整数かつ $0\le D_{\alpha,\beta}\le 2\times 10^5\quad$ ( $\alpha,\beta$ は任意の英小文字)

入力

$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}}$

注)$D$ はどちらの添え字もアルファベット順に並んでいる。

出力

$X_{\alpha,\beta}$ を $(\alpha,\beta)$ が条件を満たしている場合は Y 、満たしていない場合は N とします。

以下のように、$X$ を各行空白区切りで 26 行出力してください。

$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}}$

注)$X$ はどちらの添え字もアルファベット順に並んでいる。

サンプル

サンプル1
入力
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
出力
Y Y 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)$ は $i+D_{\mathtt{a},\mathtt{a}}\le j$ を満たすので、 $X_{\mathtt{a},\mathtt{a}}=$ Y です。
  • $(\mathtt{a},\mathtt{b})$ : $(i,j)=(1,2),(1,4),(3,4)$ はすべて $i+D_{\mathtt{a},\mathtt{b}}\le j$ を満たすので、 $X_{\mathtt{a},\mathtt{b}}=$ Y です。
  • $(\mathtt{b},\mathtt{a})$ : $(i,j)=(2,3)$ では $i+D_{\mathtt{b},\mathtt{a}}>j$ なので、 $X_{\mathtt{b},\mathtt{a}}=$ N です。
  • $(\mathtt{b},\mathtt{b})$ : $(i,j)=(2,4)$ では $i+D_{\mathtt{b},\mathtt{b}}>j$ なので、 $X_{\mathtt{b},\mathtt{b}}=$ N です。
  • その他: $(S_i,S_j)=(\alpha,\beta)$ となる $(i,j)$ が存在しないため常に条件を満たし、 $X_{\alpha,\beta}=$ Y です。
サンプル2
入力
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
出力
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y 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もしくは右上の雲マークをクリックしてアカウントを作成してください。