実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 800 点
問題文
いくつかのプログラミング言語では,2つの文字列 s1 と s2 について,文字列の結合を表す演算子 + が定義されています。たとえば,s1=a,s2=b のとき,s1+s2=ab となります。 ところが,文字列の結合を表す演算子 + は,数の和を表す演算子 + とはちがって,交換法則は成立しません。たとえば,s1=a,s2=b のとき,s1+s2=ab であるのに対し,s2+s1=ba となるので,交換法則が成立していません。
ゆらふなくんは,2つの文字列に対する交換法則が成立する演算子として,以下のような演算子 @ を考えました。
- s1@s2=min(s1,s2)+max(s1,s2)
ここで,min, max は辞書順の比較,+ は文字列の結合を表します。たとえば,s1=a,s2=b のとき,s1@s2=min(a,b)+max(a,b)=a+b=ab となります。また,s2@s1=min(a,b)+max(a,b)=a+b=ab となるので,交換法則が成立しています。
ゆらふなくんは,演算子 @ がとても気に入っているので,いろいろな文字列を1文字ごとに分解したあとに,演算子 @ と優先順位を変える括弧のみを使って元の文字列に戻す遊びをしています。たとえば,apple
という文字列は ((a@(p@p))@l)@e や e@(((p@p)@a)@l) などの式によって apple
という文字列に戻すことができます。しかしながら,pen
という文字列は分解してしまうと元に戻すことができないことに気づきました。分解してから元に戻せない文字列では遊ぶことができないので,そのような文字列かどうか判定する必要があります。
文字列 S が与えられます。1文字ごとに分解したあと,演算子 @ と括弧のみを使って元の文字列に戻せるかどうか判定してください。
制約
- 1≦|S|≦3000 (|S| は文字列 S の長さ)
- S はアルファベット小文字のみからなる
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S を再構築できる場合は Yes
, できない場合は No
を1行で出力せよ。
入力例 1
abc
出力例 1
Yes
入力例 2
acb
出力例 2
Yes
入力例 3
bca
出力例 3
No
入力例 4
cba
出力例 4
No
入力例 5
aaba
出力例 5
No