No.2000 Distanced Characters
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 103
作問者 :
to-omer
/ テスター :
遭難者
ygussany
タグ : / 解いたユーザー数 103
作問者 :
to-omer
/ テスター :
遭難者
ygussany
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。