公式
B - Replace to the Other 解説
by
B - Replace to the Other 解説
by
Forested
\(1\) 以上 \(N\) 以下の整数 \(i\) について、 \(i\) が偶数ならば \(S_i\) を反転させて、新たに文字列 \(S'\) を作ります。同様にして、文字列 \(T'\) も作ります。
すると、問題文中の操作は \(S'\) 上では以下のように見ることができます。
- \(S'_i \neq S'_{i+1}\) であるような整数 \(i \, (1 \leq i < N)\) を選び、 \(S'_i\) と \(S'_{i+1}\) を入れ替える。
さて、 \(S'\) の中で文字 A
が出現する回数を \(n\) とし、出現する場所が \(a_1, a_2, \ldots, a_n \, (a_1 < a_2 < \ldots < a_n)\) 文字目だとしましょう。同様に、 \(T'\) の中で文字 A
が出現する回数を \(m\) とし、出現する場所が \(b_1, b_2, \ldots, b_m \, (b_1 < b_2 < \ldots < b_m)\) 文字目だとしましょう。
操作を行っても文字 A
の出現回数は変わらないので、 \(n \neq m\) ならば \(S'\) と \(T'\) を一致させることはできません。逆に、 \(n = m\) ならば操作の最小回数は \(\sum_{i=1}^n |a_i - b_i|\) です。
よって、時間計算量 \(\Theta(N)\) でこの問題を解くことが可能です。
投稿日時:
最終更新: