A - Replace C or Swap AB Editorial by maspy
ヒント → https://atcoder.jp/contests/arc166/editorial/7181
[1] 文字 A
, B
のみの場合
まずは,文字が A
, B
のみの場合について解説します.
この場合考えるべき操作は操作 (3) のみです.
この操作は,A
のみに注目してその位置がどのように変化するかに考えると,「ひとつの A
を右に \(1\) つ移動させる」という操作であると見ることができて,次のことが証明できます:
\(X\), \(Y\) がどちらも
A
,B
のみからなる文字列であるとする.\(X\) の \(i\) 文字目が
A
であるような \(i\) 全体を \(i_1 < i_2 < \cdots < i_x\) とする. \(Y\) の \(i\) 文字目がA
であるような \(i\) 全体を \(j_1 < j_2 < \cdots < j_y\) とする.このとき \(X\) を操作 (3) によって \(Y\) にできるための必要十分条件は, \(x=y\) かつ任意の \(k\) に対して \(i_k\leq j_k\) となることである.
必要性は,操作が \(1\) 回の場合に示せばよく,簡単です.十分性は,大きな \(k\) から順に,\(X\) における \(k\) 番目の A
を適切な位置に移動させることを考えればよいです.
[2] 本問の解法
まず,操作によって新たに文字 C
が作られることはありません.よって次が成り立つことが必要です:
- \(Y\) の \(i\) 文字目が
C
ならば,\(X\) の \(i\) 文字目もC
である.
この必要条件が成り立たないならば答は No
です.
この条件が成り立つとき,本文は \(Y\) の C
の位置で区切ってそれぞれの部分文字列について判定すればよいです.
このように区切ると,\(Y\) が A
, B
のみからなる場合の問題に帰着できます.
\(Y\) が A
, B
のみからなるとします.\(X\) の C
に対してどのように操作 (1), (2) を行うべきかを考えます.
まず文字列における A
, B
の個数を数えれば,\(X\) の C
のうちいくつを A
, B
に変換するべきかが求まります.さらになるべく左にある C
を A
,右にある C
を B
に変換する方が [1] の条件が単純に成り立ちやすくなるので,そのように変換した上で [1] の条件を確かめることで本問を解くことができます.
posted:
last update: