問題一覧 > 通常問題

No.2018 X-Y-X

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 54
作問者 : milkcoffeemilkcoffee / テスター : Kiri8128Kiri8128
16 ProblemId : 8006 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-06 16:19:30

問題文

A と B からなる長さ $N$ の文字列 $S$ 及び $T$ が与えられます。あなたは、文字列 $S$ に対して以下の操作を $0$ 回以上何度でも行えます。

  • $S_i = S_{i+2}$ であるような $1 \leq i \leq N-2$ を選ぶ。そして、 $S_{i+1}$ の文字を変更する(AならばBに、BならばAにする)。

$S$ を $T$ に一致させることはできますか。できる場合は必要な最小の操作回数を求めてください。

入力

$N$
$S$
$T$

  • $3 \leq N \leq 2 \times 10^5$
  • $N$ は整数
  • $S,T$ は A,B からなる長さ $N$ の文字列

出力

$S$ を $T$ に一致させることができる場合、必要な最小の操作回数を出力してください。
一致させることが不可能な場合は -1 を出力してください。

サンプル

サンプル1
入力
4
ABAA
AABA
出力
2

まず、 $i=1$ として操作をすると、 $S$ は AAAA となります。
次に、 $i=2$ として操作をすると、 $S$ は AABA となります。

サンプル2
入力
4
BBAA
BABA
出力
-1

$S$ に対して操作をすることができないため、 $S$ を $T$ に一致させることはできません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。