問題一覧 > 通常問題

No.2000 Distanced Characters

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

問題文

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

  • Si=αS_i=\alpha, Sj=βS_j=\beta を満たす任意の 1≤i<j≤N1\le i<j\le N について、 i+Dα,β≤ji+D_{\alpha,\beta}\le j

制約

  • SS は英小文字からなる文字列
  • 1≤∣S∣≤2×1051\le |S|\le 2\times 10^5
  • Dα,βD_{\alpha,\beta} は整数かつ 0≤Dα,β≤2×1050\le D_{\alpha,\beta}\le 2\times 10^5\quad （ α,β\alpha,\beta は任意の英小文字）

入力

SS
Da,aD_{\mathtt{a},\mathtt{a}} Da,bD_{\mathtt{a},\mathtt{b}} …\dots Da,zD_{\mathtt{a},\mathtt{z}}
Db,aD_{\mathtt{b},\mathtt{a}} Db,bD_{\mathtt{b},\mathtt{b}} …\dots Db,zD_{\mathtt{b},\mathtt{z}}
⋮\vdots
Dz,aD_{\mathtt{z},\mathtt{a}} Dz,bD_{\mathtt{z},\mathtt{b}} …\dots Dz,zD_{\mathtt{z},\mathtt{z}}

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

出力

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

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

Xa,aX_{\mathtt{a},\mathtt{a}} Xa,bX_{\mathtt{a},\mathtt{b}} …\dots Xa,zX_{\mathtt{a},\mathtt{z}}
Xb,aX_{\mathtt{b},\mathtt{a}} Xb,bX_{\mathtt{b},\mathtt{b}} …\dots Xb,zX_{\mathtt{b},\mathtt{z}}
⋮\vdots
Xz,aX_{\mathtt{z},\mathtt{a}} Xz,bX_{\mathtt{z},\mathtt{b}} …\dots Xz,zX_{\mathtt{z},\mathtt{z}}

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

サンプル

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